Рекомендуется ли всегда иметь исчерпывающие совпадения шаблонов в Haskell, даже для "невозможных" случаев?

Например, в следующем коде я сопоставляю шаблоны на "аккумуляторе" foldr. Я полностью контролирую содержимое аккумулятора, потому что я его создаю (он не передается мне как вход, а скорее встроен в мою функцию). Поэтому я знаю, что некоторые шаблоны никогда не должны совпадать. Если я попытаюсь никогда не получить "Match Match (es) - не исчерпывающая" ошибка, то я бы поставил для него шаблонное совпадение, которое просто ошибкой с сообщением "Этот шаблон никогда не должен происходить". Очень похоже на утверждение в С#. Я не могу придумать что-нибудь еще.

Какую практику вы бы порекомендовали в этой ситуации и почему?

Здесь код:

gb_groupBy p input = foldr step [] input
   where
      step item acc = case acc of
           []                           -> [[item]]
           ((x:xs):ys)                  -> if p x item
                                           then (item:x:xs):ys
                                           else [item]:acc

Образец, не совпадающий (как сообщает интерпретатор):

Предупреждение: совпадение шаблонов не является исчерпывающим В случае альтернативы: шаблоны не совпадают: []: _

Ответ 1

Это, скорее всего, вопрос стиля, чем что-либо еще. Лично я бы поставил

_ -> error "Impossible! Empty list in step"

если только отключить предупреждение:)

Ответ 2

Вы можете разрешить предупреждение в этом специальном случае, выполнив следующее:

gb_groupBy p input = foldr step [] input
   where
     step item acc = case acc of
        []                           -> [[item]]
        (xs:xss)                      -> if p (head xs) item
                                         then  (item:xs):xss
                                         else [item]:acc

Последовательность шаблонов завершается, а "невозможное" условие пустого списка в голове аккумулятора вызывает ошибку времени выполнения, но не предупреждение.

Еще один способ взглянуть на более общую проблему неполных сопоставлений шаблонов - увидеть их как "запах кода", то есть указание на то, что мы пытаемся решить проблему в субоптимальном или не-Haskellish, и попробуйте переписать наши функции.

Реализация groupBy с помощью foldr делает невозможным применение его к бесконечному списку, что является целью дизайна, которую функции списка Haskell пытаются достичь везде, где это семантически разумно. Рассмотрим

take 5 $ groupBy (==) someFunctionDerivingAnInfiniteList

Если первые 5 групп w.r.t. равенство конечное, ленивая оценка прекратится. Это то, что вы не можете сделать на строго оцененном языке. Даже если вы не работаете с бесконечными списками, такие функции записи будут обеспечивать более высокую производительность в длинных списках или избежать, которое возникает при оценке выражений типа

take 5 $ gb_groupBy (==) [1..1000000]

В List.hs, groupBy реализуется следующим образом:

groupBy         :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []       =  []
groupBy eq (x:xs)   =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

Это позволяет интерпретатору/компилятору оценивать только те части вычислений, которые необходимы для результата. span дает пару списков, в которых первый состоит из (последовательных) элементов из главы списка, всех удовлетворяющих предикату, и второй - остальная часть списка. Он также реализован для работы с бесконечными списками.

Ответ 3

Я считаю, что проверка полноты на случайных шаблонах незаменима. Я стараюсь никогда не использовать _ в случае на верхнем уровне, потому что _ соответствует всем, и, используя его, вы теряете ценность проверки полноты. Это менее важно в списках, но важно важно с определяемыми пользователем алгебраическими типами данных, потому что я хочу иметь возможность добавлять новый конструктор и иметь барьер компилятора во всех недостающих случаях. По этой причине я всегда скомпилирован с включенным -Werror, поэтому я не могу исключить случай.

Как уже отмечалось, ваш код может быть расширен с помощью этого случая

[] : _ -> error "this can't happen"

Внутри GHC имеет функцию panic, которая в отличие от error будет давать исходные координаты, но я смотрел на реализацию и не мог сделать ее головой или хвостом.

Ответ 4

Чтобы следить за моим предыдущим комментарием, я понял, что есть способ признать недостающий случай, но все же получить полезную ошибку с номером файла/строки. Это не идеально, поскольку оно появится только в неоптимизированных сборках (см. здесь).

...
[]:xs -> assert False (error "unreachable because I know everything")

Ответ 5

Система типов - ваш друг, и предупреждение дает вам знать, что ваша функция имеет трещины. Самый лучший подход - пойти на более чистую, более элегантную форму между типами.

Рассмотрим определение ghc groupBy:

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

Ответ 6

Моя точка зрения заключается в том, что невозможным случаем является undefined.
Если это undefined, у нас есть функция для этого: хитро названное undefined.

Завершите свое соответствие с:

_ -> undefined

И вот он у вас есть!