Почему "голова" Хаскелла падает на пустой список (или почему *не* он возвращает пустой список)? (Философия языка )

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

чтобы быть ясным: я не ищу "безопасный" head, и это не выбор head в частности, исключительно значимой. Мясо вопроса следует за обсуждением head и head', которые служат для обеспечения контекста.

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

для этого примера, я говорю о head.

как я полагаю, вы будете знать,

Prelude> head []    
*** Exception: Prelude.head: empty list

это следует из head :: [a] -> a. Справедливо. Очевидно, что нельзя вернуть элемент (махнув рукой) без типа. Но в то же время, это просто (если не тривиально) определить 

head' :: [a] -> Maybe a
head' []     = Nothing
head' (x:xs) = Just x

Я видел небольшое обсуждение этого здесь в разделе комментариев некоторых утверждений. Примечательно, что один Алекс Штангл говорит

'есть веские причины не делать все "безопасный" и бросать исключения, когда нарушаются условия.-

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

кроме того, Пол Джонсон говорит:

'например, вы можете определить" safeHead:: [a] -> Maybe a", но теперь вместо того, чтобы обрабатывать пустой список или доказывать, что это не может произойти, вам нужно обработать "ничего" или доказать, что это не может произойти.-

в тон, который я прочитал из этого комментария, предполагает, что это заметное увеличение сложности/сложности/чего-то, но я не уверен, что понимаю, что он там ставит.

один Стивен пружина говорит (в 2011 году, не меньше),

есть более глубокая причина, по которой, например, "голова" не может быть устойчива к краху. Чтобы быть полиморфным, но обрабатывать пустой список, 'head' всегда должен возвращать переменную типа, который отсутствует в любом конкретном пустом списке. Это было бы Дельфийским, если бы Хаскелл мог сделать это...".

полиморфизм теряется, позволяя обрабатывать пустой список? Если так, как же так, и почему? Есть ли конкретные случаи, которые сделали бы это очевидным? на этот раздел подробно ответил @Russell O'Connor. любые дальнейшие мысли, конечно, оценили.

Я буду редактировать это как ясность и диктует предложение. Любые мысли, документы и т. д., вы можете предоставить будет наиболее ценится.

6 68
haskell class-design polymorphism parametric-polymorphism

6 ответов:

полиморфизм теряется, позволяя пустой обработка списка? Если так, как же так, и почему? Есть ли конкретные случаи, которые бы сделать это очевидным?

свободная теорема для head утверждает, что

f . head = head . $map f

применение этой теоремы к [] означает, что

f (head []) = head (map f []) = head []

эта теорема должна выполняться для каждого f, так что в частности он должен держать для const True и const False. Это подразумевает

True = const True (head []) = head [] = const False (head []) = False

таким образом, если head правильно полиморфный и head [] общее значение, то True будет равна False.

PS. У меня есть некоторые другие комментарии о предыстории вашего вопроса о том, что если у вас есть предварительное условие, что ваш список непустой, то вы должны применить его, используя непустой тип списка в вашей сигнатуре функции вместо использования списка.

93

почему кто-то использовать head :: [a] -> a вместо сопоставления с образцом? Одна из причин заключается в том, что вы знаете, что аргумент не может быть пустым и не хотите писать код для обработки случая, когда аргумент пуст.

конечно, ваш head' типа [a] -> Maybe a определен в стандартной библиотеке как Data.Maybe.listToMaybe. Но если вы замените использование head С listToMaybe, вы должны написать код для обработки пустого случая, который побеждает эту цель использования head.

Я не говорю, что с помощью head хороший стиль. Он скрывает тот факт, что это может привести к исключению, и в этом смысле это не хорошо. Но иногда это удобно. Дело в том, что head служит некоторым целям, которым не может служить listToMaybe.

последняя цитата в вопросе (о полиморфизме) просто означает, что невозможно определить функцию типа [a] -> a который возвращает значение в пустом списке (как Рассел О'Коннор пояснил, что в ответ).

22

вполне естественно ожидать, что следующее удержится:xs === head xs : tail xs - список идентичен своему первому элементу, за которым следуют остальные. Кажется логичным, не так ли?

теперь давайте подсчитаем количество минусов (приложений :), игнорируя фактические элементы, применяя предполагаемый "закон" к []:[] должно быть идентично foo : bar, но первый имеет 0 минусов, в то время как последний имеет (по крайней мере) один. Ой, что-то здесь не так!

Хаскелл тип системы, при всех ее сильных сторонах, не дотягивает до выражения того, что нужно только вызвать head в непустом списке (и что "закон" действителен только для непустых списков). Используя head переносит бремя доказательства на программиста, который должен убедиться, что он не используется в пустых списках. Я считаю, что зависимо типизированные языки, такие как Agda, могут помочь здесь.

наконец, чуть более операционально-философское описание: как должно head ([] :: [a]) :: a будет осуществляться? Колдовать значение типа a из воздуха невозможно (подумайте о необитаемых типах, таких как data Falsum), и было бы равносильно доказательству чего-либо (через изоморфизм Карри-Говарда).

8

есть несколько различных способов, чтобы думать об этом. Так что я буду спорить и за, и против head':

против head':

нет необходимости иметь head': поскольку списки являются конкретным типом данных, все, что вы можете сделать с head' вы можете сделать по шаблону.

кроме того, с head' вы просто меняете один функтор на другой. В какой-то момент Вы хотите ближе к делу и поработать на Базовый элемент списка.

в защиту head':

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

кроме того, думая о [] и Maybe функторы, head' позволяет перемещаться вперед и назад между ними (в частности,Applicative экземпляр [] С pure = replicate.)

3

Если в вашем случае использования пустой список не имеет никакого смысла, вы всегда можете использовать NonEmpty, где neHead безопасен в использовании. Если вы видите его под этим углом, это не head функция, которая небезопасна, это вся структура данных списка (опять же, для этого случая использования).

2

Я думаю, это вопрос простоты и красоты. Что, конечно, в глазах смотрящего.

если исходить из фона Lisp, вы можете знать, что списки построены из ячеек cons, каждая ячейка имеет элемент данных и указатель на следующую ячейку. Пустой список-это не список как таковой, а особым символом. И Хаскелл идет с этим рассуждением.

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

...Я могу добавить - если вы беспокоитесь о том, что голова небезопасна - не используйте ее, вместо этого используйте сопоставление шаблонов:

sum     [] = 0
sum (x:xs) = x + sum xs
1