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 ellast
. Esto se puede escribir a lareverse . drop 1 . reverse
reverse . drop 1 . reverse
reverse . drop 1 . reverse
, lo que sugiere una generalización obvia. Podríamos introducir una contraparte similar paratake
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 conNothing
.
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.