Почему Haskell `head` разбивается на пустой список (или почему * не * возвращает пустой список)? (Философия языка)

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

Чтобы быть ясным: я не ищу "безопасный" 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", но вместо того, чтобы обрабатывать пустой список или доказывать, что этого не может быть, вам нужно обработать "Nothing" или доказать, что он может "Слушай".

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

Один Стивен Прузина говорит (в 2011 году, не менее),

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

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

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

Ответы

Ответ 1

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

В свободной теореме для 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. У меня есть другие комментарии о предыстории вашего вопроса, если у вас есть предварительное условие, что ваш список не пуст, тогда вы должны обеспечить его соблюдение, используя непустой тип списка в вашей сигнатуре функции, а не используя список.

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

Есть несколько способов думать об этом. Поэтому я буду спорить и против, и против head':

Против head':

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

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

В защиту head':

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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