haskell - tipos - ¿Por qué es init una función parcial?

tipos de datos haskell (5)

De acuerdo con el informe de Haskell 2010 , init se define como lo siguiente:

init :: [a] -> [a] init [x] = [] init (x:xs) = x : init xs init [] = error "Prelude.init: empty list"

base-4.4.1.0 define de manera similar. Para mí, parece que sería perfectamente aceptable e intuitivo tener:

init [] = []

lo que haría de init una función total. Dado que esta definición se incluyó en el informe de haskell 2010, supongo que existen argumentos para ello. ¿Es ese el caso o está definido de esa manera debido a la tradición y la compatibilidad con versiones anteriores?

Como la pregunta me parece interesante, decidí escribir mis pensamientos sobre el tema:

Lógico

Digamos que definimos init xs como "la lista, que, si coloca las last xs en su extremo, es igual a xs . Esto es equivalente a: init xs es la lista sin su último elemento. Para xs == [] , existe ningún último elemento, por lo que init [] tiene que estar indefinido.

Podría agregar un caso especial para esto, como en "si xs es la lista vacía, init xs es la lista vacía, de lo contrario init xs es la lista, que, si coloca las last xs en su extremo, es igual a xs " . Observe cómo esto es mucho más detallado y menos limpio. Introducimos complejidad adicional, pero ¿para qué?

Intuitivo

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

Observe cómo la longitud de las listas en el lado derecho de las ecuaciones disminuye junto con la longitud del lado izquierdo. Para mí, esta serie no se puede continuar de una manera sensata, ¡porque la lista del lado derecho tendría que tener un tamaño negativo!

Práctico

Como han señalado otros, definir un manejo de casos especiales para init o tail para la lista vacía como un argumento, puede introducir errores difíciles de detectar en situaciones donde las funciones no pueden tener un resultado sensible para la lista vacía, pero aún así no lo hacen. producir una excepción para ello!

Además, no se me ocurre ningún algoritmo en el que sería realmente ventajoso que init [] evalúe a [] , así que, ¿por qué introducir esa complejidad adicional? La programación tiene que ver con la simplicidad y, especialmente, con Haskell, con la pureza, ¿no estás de acuerdo?

El problema real aquí es que init , como se define, no puede funcionar; Es una función inherentemente parcial, al igual que la head y la tail . No estoy entusiasmado con la cantidad de funciones parciales deliberadas que existen en las bibliotecas estándar, pero eso es otra cuestión.

Dado que init como dado no se puede salvar, tenemos dos opciones:

Tome la interpretación de que es un filtro en la lista dada, manteniendo todos los elementos que no son el último elemento y abandonando a los invariantes con respecto a la length y el last . Esto se puede escribir a la reverse . drop 1 . reverse reverse . drop 1 . reverse reverse . drop 1 . reverse , lo que sugiere una generalización obvia. Podríamos introducir una contraparte similar para take si así lo desea, también.
Reconozca que init define una función parcial, y asigne el tipo correcto, [a] -> Maybe [a] . El error puede ser reemplazado correctamente con Nothing .

Es tradicional En ese momento, hicieron una elección arbitraria, y ahora la gente está acostumbrada.

Hicieron un init similar al last , de modo que ambos fallan en listas vacías. ( tail y head son otro par así).

Pero podrían haber elegido lo contrario, como sugieres. Prelude podría contener fácilmente una función tail'' = drop 1 , así como una función de init'' coincidente, permitiendo listas vacías. No creo que esto sea un problema, no estoy convencido por todo lo que se habla de invariantes y teoremas libres. Solo significaría que init'' era un poco diferente a su compañero last ; eso es todo.

(La last y la head son otra historia: su firma es [a] -> a , por lo que deben devolver un elemento, y no pueden hacer una con el aire. Por el contrario, el tipo de init y la tail son, por supuesto, [a] -> [a] , lo que significa que pueden y, de hecho, producen listas vacías.)

La misma razón por la que la tail [] no es [] ; Rompe las invariantes que definen estas funciones. Podemos definir head y tail diciendo que si la head y la tail están definidas para un valor xs , entonces xs ≡ head xs : tail xs .

Como señaló Niklas, el invariante que queremos definir es init y el last es xs ≡ init xs ++ [last xs] . Es cierto que la last no está definida en listas vacías, pero ¿por qué debería definirse la last vez si init no puede ser? Al igual que sería incorrecto si uno de head o tail se definiera en una entrada, mientras que el otro no, init y last son dos caras de la misma moneda, dividiendo una lista en dos valores que juntos son equivalentes a la original.

Para una vista más "práctica" (¡aunque es capaz de razonar sobre los programas en términos de invariantes útiles sobre las operaciones que utilizan tiene un beneficio muy práctico!), Un algoritmo que usa init probablemente no se comportará correctamente en una lista vacía, y si init Trabajado de esa manera, funcionaría para ocultar los errores producidos. Es mejor que init sea conservador con respecto a sus entradas, por lo que se debe tener en cuenta los casos límite como la lista vacía cuando se utiliza, especialmente cuando no está claro en absoluto que el valor propuesto para que se devuelva en esos casos es razonable.

Aquí hay una pregunta anterior sobre el desbordamiento de pila sobre la head y la tail , que incluye por qué la tail [] no solo devuelve [] ; Las respuestas allí deberían ayudar a explicar por qué estas invariantes son tan importantes.

Sería terrible tener init [] = [] , especialmente rompería invariantes importantes como xs == init xs ++ [last xs] y length xs == 1 + length (init xs) , y por lo tanto ocultará los errores.