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

17

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

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

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

Вот код:

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

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

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

    
задан Charlie Flowers 07.05.2009 в 07:20
источник
  • Назойливая вещь заключается в том, что для отключения предупреждения вы часто оказываете менее полезное сообщение об ошибке во время выполнения. Я хотел бы просто подтвердить отсутствующий случай, но разрешить использовать текст ошибки времени выполнения по умолчанию (который указывает на номер файла / строки), который будет использоваться. –  Ganesh Sittampalam 07.05.2009 в 09:47
  • Это отличный момент. Думаю, в настоящее время нет способа сделать это. Очень жаль. –  Charlie Flowers 07.05.2009 в 09:59
  • см. также stackoverflow.com/questions/1882334 –  sdcvvc 21.02.2012 в 14:05

6 ответов

20

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

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

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

    
ответ дан bdonlan 07.05.2009 в 07:23
источник
  • Я согласен с этим подходом. Это помогает указать, что вы намеренно не справлялись с другими случаями, потому что считаете, что это невозможно, а не просто забываете или не осознаете. –  newacct 07.05.2009 в 07:31
  • Всегда весело, когда ваша программа внезапно заканчивается этим описательным сообщением: *** Исключение: Произошло невозможное! –  Tom Lokhorst 07.05.2009 в 07:39
  • Да, мне напоминает, когда я был очень новичком в программировании, и у меня бы были комментарии вроде «Вы никогда не должны доходить до этой строки». :) –  Charlie Flowers 07.05.2009 в 09:59
  • Недостатком этого подхода является добавление большего количества случаев в ваш тип данных сумм, тогда компилятор не будет напоминать вам об обновлении соответствующих функций. –  Justin Raymond 04.08.2016 в 17:33
11

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

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 дает пару списков, в которых первый состоит из (последовательных ) элементы из главы списка, все удовлетворяющие предикату, а вторая - остальная часть списка. Он также реализован для работы с бесконечными списками.

    
ответ дан Christoph 07.05.2009 в 12:34
источник
  • +1, проницательный. –  Alexandre C. 02.02.2011 в 20:06
  • > Это то, что вы не можете сделать на строго оцененном языке. Это может быть сделано на любом языке Turing-complete ... И иногда даже не слишком сложно. Например, вы можете легко моделировать «бесконечные» списки даже в Java. –  Sarge Borsch 12.09.2013 в 19:33
  • Расчет Тьюринга относится к тому, какие вычисления вы можете сделать, а не как указать его, причем последнее является очевидной областью моего ответа. Конечно, вы можете сглаживать что-то вместе, скажем, с утилитами коллекции Guava на Java или, что более элегантно, создавать что-то, используя LINQ в .NET. Но для этого требуются коллекции, которые не просто реализуют Iterable или IEnumerable, но явно разрешают ленивое вычисление, например. путем реализации абстрактного объекта Guava или ключевого слова yield в C #. В Haskell все, возвращающее коллекцию, можно использовать лениво, без дальнейших церемоний. –  Christoph 17.09.2013 в 20:55
8

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

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

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

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

    
ответ дан Norman Ramsey 07.05.2009 в 23:24
источник
  • Мне очень нравится это в качестве ориентира. При программировании на C # я часто хотел что-то вроде «проверки полноты». Например, если у меня есть перечисление и оператор case для обработки каждого члена перечисления, я хотел бы сообщить компилятору «убедитесь, что я рассмотрел все случаи». Я понятия не имел, что такое понятие будет частью фундамента Haskell и других функциональных языков. –  Charlie Flowers 08.05.2009 в 03:03
  • О да, я всегда чувствую себя виноватым при использовании перечислений и переключения. Но это гораздо более кратким, чем создание целостной иерархии классов и разделение одного серьезного метода на множество мелких виртуальных методов. –  Christian Klauser 27.01.2010 в 19:29
  • Да. Я очень верю в полиморфизм, но даже в стороне от этого есть случаи, когда вы хотите «разветвить» значение, разбив его на подкатегории (менее 3, 3 или выше, но нечетные и 3 или выше, но даже). Если вы выразите это неправильно, у вас есть «граничные» ошибки. Но компилятор мог легко поймать это для вас, если бы знал, что вы пытаетесь охватить все возможные диапазоны. И это одно из того, что соответствует шаблону во многих функциональных языках. –  Charlie Flowers 24.03.2010 в 00:41
  • Ничего себе, Норман, это почти год спустя, и только сейчас я получаю ваш каламбур. Думаю, в первый раз, когда я его прочитал, я не сделал этого или не сделал этого :) –  Charlie Flowers 29.04.2010 в 00:17
4

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

источник
  • Ницца. Спасибо за продолжение. –  Charlie Flowers 07.05.2009 в 20:18
2

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

Рассмотрим определение 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
    
ответ дан Greg Bacon 27.01.2010 в 19:11
источник
1

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

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

_ -> undefined

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

    
ответ дан MasterMastic 22.04.2014 в 12:56
источник