haskell - recupera - ¿Por qué la función de ciclo no puede funcionar con una lista vacía?

ordenar lista haskell

Question

Utilicé el cycle funciones en algunos de mis proyectos y hoy descubrí que no es una función total, como se muestra en este ejemplo de GHCI:

λ> Data.List.cycle []
*** Exception: Prelude.cycle: empty list

Sé que Haskells intenta usar funciones totales (excepto las funciones fundamentales head y tail ) y no estoy completamente seguro de por qué el cycle no es una de ellas. En mi opinión, el cycle de la lista vacía es la lista vacía y no veo problemas con esto. ¿Por qué cycle para listas vacías produce un error?

EDITAR : Basado en las primeras respuestas, creo que mi idea no está completamente clara: no quiero que el cycle [] sea ​​un cálculo que nunca termina. Por el contrario, creo que el cycle [] debería ser el:

cycle :: [a] -> [a]
cycle [] = []
cycle xs = xs ++ cycle xs

El [] es el cycle [] porque todas las operaciones hacen exactamente lo que yo exijo. Por ejemplo, take 3 [] es [] y, por lo tanto, take 3 (cycle []) podría ser [] . ¿Cuál es el problema con esta solución?

Answer 1

El problema surge cuando se trata de acceder a elementos en la lista. Una función de ciclo autodefinida que opera en una lista no vacía no tiene problemas cuando se accede, pero al intentar obtener, por ejemplo, los primeros 3 elementos de la lista vacía ciclada dan como resultado un bucle infinito:

cycle'' xs = xs ++ cycle'' xs

take 3 (cycle'' [1,2]) -- returns [1,2,1]
take 3 (cycle'' [])    -- still looping

Answer 2

La intención del cycle como se describe en la documentación es:

import Data.List.Nonempty
import Data.Stream.Infinite

cycle :: NonEmpty a -> Stream a

Los autores de Prelude utilizan una función parcial para pasar en una lista vacía, que es conceptualmente un error de tipo, similar a la head y la tail .

Si desea un ciclo que devuelve [] es tan fácil como:

myCycle :: [a] -> [a]
myCycle xs = if null xs then xs else cycle xs

Consulte: semigroups para la definición de No NonEmpty y streams para la definición de Stream y una definición total de cycle .

Answer 3

No tengo una visión especial de la (s) mente (s) de las personas que implementaron la función del cycle .

El cycle :

el ciclo une una lista finita en una circular, o de manera equivalente, la repetición infinita de la lista original. Es la identidad en listas infinitas.

Tradicionalmente, cuando piensas en una lista enlazada circularmente, en una entrada de wiki tienes:

¿Cómo expresaría una lista vacía circular? ¿Un puntero va a sí mismo? Pero incluso eso no encaja.

Mi mejor explicación es que las listas circulares no son listas normales. Son diferentes bestias con diferentes semánticas. Al igual que head realidad solo se define por completo en una lista vacía no vacía porque no hay un primer elemento de una lista vacía, el cycle solo se define completamente en listas no vacías porque no hay una lista enlazada circular vacía.

Answer 4

Tenga en cuenta que tal como está definido actualmente, es consistente con la tail .

tail [] = error ...

cycle está relacionado conceptualmente con la tail . Cuando realiza un cycle una lista, eso significa que puede mirar repetidamente su tail y nunca llegar al "final" ( [] ), porque es un ciclo. (Vea la imagen de Davorak). En otras palabras, siempre es seguro usar tail en una lista de cycle , asumiendo, por supuesto, que era seguro usar un cycle en esa lista en primer lugar.

Yo, por mi parte, creo que es una cosa perfectamente razonable de definir.

tail [] = []
cycle [] = []

Pero debes redefinir tanto el cycle como la tail para tail consistencia.

Answer 5

cycle realmente se define como devolver una lista infinita para todas las entradas. Si intentara hacerlo ingenuamente con una entrada vacía, se sentaría en un bucle infinito. La condición de error es ligeramente más informativa con la misma semántica denotacional.

Editar:

Como la gente no parece entender lo que quiero decir cuando digo que la salida en blanco es mala, considere esta simple función:

labelElements :: [a] -> [b] -> [(a, b)]
labelElements labels elements = zip (cycle labels) elements

Es agradable y simple, con una condición de error evidente cuando la lista de etiquetas está vacía. Si el ciclo devolvía una lista vacía en una entrada vacía, haría que labelElements silenciosamente ese error a su salida. En este momento, grita y grita que te equivocaste. Uno de estos es mucho mejor que el otro.