Почему init выполняет частичную функцию?

Ответ 1

По той же причине tail [] не []; он разбивает инварианты, определяющие эти функции. Мы можем определить head и tail, говоря, что если head и tail определены для значения xs, тогда xs ≡ head xs : tail xs.

Как указал Никлас, инвариантом, который мы хотим определить init и last, является xs ≡ init xs ++ [last xs]. Это правда, что last также не определяется в пустых списках, но почему last следует определять, если init не может быть? Точно так же, как было бы неправильно, если бы один из head или tail был определен на входе, а другой - нет, init и last - две стороны одной и той же монеты, разделив список на два значения, которые вместе эквивалентны оригиналу.

Для более "практического" представления (хотя возможность рассуждать о программах с точки зрения полезных инвариантов относительно используемых ими операций имеет очень практическую выгоду!), алгоритм, который использует init, вероятно, не будет корректно вести себя на пустом список, и если init работал таким образом, это сработало бы, чтобы скрыть возникшие ошибки. Это лучше для init быть консервативным в отношении своих входных данных, поэтому необходимо учитывать соображения для крайних случаев, таких как пустой список, когда он используется, особенно если не совсем ясно, что предлагаемое значение для него должно возвращаться в тех случаев разумно.

Здесь предыдущий вопрос о переполнении стека о head и tail, включая почему tail [] не просто возвращает []; ответы там должны помочь объяснить, почему эти инварианты настолько важны.

Ответ 2

Поскольку я нахожу вопрос интересным, я решил записать свои мысли по этому вопросу:

Логическое

Скажем, мы определяем init xs как "список, который, если вы положите last xs на его конец, равен xs. Это эквивалентно: init xs - это список без его последний элемент. Для xs == [] не существует последнего элемента, поэтому init [] должен быть undefined.

Вы можете добавить для этого специальный случай, например, если " xs является пустым списком, то init xs - это пустой список, иначе init xs - это список, который, если вы put last xs на его конце, равен xs". Обратите внимание, что это гораздо более подробный и менее чистый. Введем дополнительную сложность, но что для?

Интуитивный

init [1,2,3,4] == [1,2,3]
init [1,2,3]   == [1,2]
init [1,2]     == [1]
init [1]       == []
init []        == ??

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

Практическая

Как указывали другие, определение обработки специального случая для init или tail для пустого списка в качестве аргумента может привести к ошибкам с ошибками в ситуациях, когда функции могут не иметь разумного результата для пустого список, но по-прежнему не создает для него исключения!

Кроме того, я не могу придумать никакого алгоритма, было бы полезно иметь init [] для оценки [], так зачем вводить эту дополнительную сложность? Программирование - все о простоте, и особенно Haskell - все о чистоте, не согласны ли вы?

Ответ 3

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

Поскольку init как заданный не может быть спасен, у нас есть два варианта:

• Возьмем интерпретацию, что это фильтр в данном списке, сохраняя все элементы, которые не являются последним элементом, и отказываясь от инвариантов относительно length и last. Это можно записать как reverse . drop 1 . reverse, что предполагает очевидное обобщение. При желании мы могли бы ввести аналогичный аналог для take.

• Признайте, что init определяет частичную функцию и задает правильный тип [a] -> Maybe [a]. Затем ошибку можно корректно заменить на Nothing.

Ответ 4

Было бы ужасно иметь init [] = [], особенно он разбивал бы важные инварианты, такие как xs == init xs ++ [last xs] и length xs == 1 + length (init xs), и, следовательно, скрывал ошибки.

Ответ 5

Это традиционный. В то время они сделали произвольный выбор, и теперь к нему привыкли люди.

Они сделали init похожим на last, так что они оба сбой в пустых списках. (tail и head - это еще одна пара.)

Но они, возможно, выбрали бы противоположное. Prelude может легко содержать функцию tail' = drop 1, а также подходящую функцию init', позволяющую пустые списки. Я не думаю, что это было бы проблемой, - я не убежден в разговоре об инвариантах и ​​свободных теоремах. Это означало бы, что init' немного отличался от своего компаньона last; что все.

(last и head - это еще одна история: их подпись [a] -> a, поэтому они должны вернуть элемент, и они не могут сделать один из воздуха. Напротив, тип init и tail, конечно, [a] -> [a], что означает, что они могут и дают пустые списки.)