Lista Haskell concatenación frente (cabeza: la cola) Formato

Question

Siempre escribió mi lista productoras de funciones recursivas en este formato:

recursiveFunc :: [a] -> [b] 
recursiveFunc (x:xs) = [change x] ++ resursiveFunc xs where 
    change :: a -> b 
    change x = ... 

Soy consciente de cualquier función como el arriba puede ser escrito para el caso a -> b y luego simplemente map ed sobre un conjunto [a], pero tome esta situación diluida como un ejemplo.

HLint sugiere reemplazar [change x] ++ recursiveFunc xs con change x : recursiveFunc xs.

¿Es esta sugerencia puramente estética, o hay algún efecto sobre cómo Haskell ejecuta la función?

Answer 1

Al utilizar [change x] ++ recursiveFunc xs crea una lista de elementos superfluos, que luego se deshace con la función ++. Usando : eso no sucede.

Plus ++ es una función que utilizará el constructor :. Cuando usa : directamente, no hay necesidad de invocar una función.

Por lo tanto, usar : es más eficiente en teoría (aunque el compilador podría optimizar esas diferencias).

Answer 2

La principal ventaja es que change x : blah es más claro - (:) es precisamente lo que está intentando hacer (agregar un elemento a una lista). ¿Por qué llamar a dos funciones cuando una hará?

La manera sugerida es también marginalmente más eficiente: su camino crea una lista de 1 elemento y luego lo descarta y lo reemplaza con un enlace de lista diferente. La otra forma solo crea un enlace de lista. Dicho esto, la diferencia es lo suficientemente pequeña como para ser irrelevante el 99% del tiempo.

Answer 3

La línea

recursiveFunc (x:xs) = [change x] ++ resursiveFunc xs 

es un poco confuso, ya que no está en normalform. Eso significa que ++ puede ser sustituido directamente con un lado de la derecha de su definición:

(++) (a:as) bs = a:((++) as bs) 
(++) [] bs = bs 

-- => 

recursiveFunc (x:xs) = (change x):((++) [] resursiveFunc xs) 

-- => 

recursiveFunc (x:xs) = (change x):(resursiveFunc xs) 

Un compilador de Haskell aplica automáticamente dicha transformación.

Pero como es tan trivial hace que su código sea más difícil de leer. Uno lo mira y pregunta 'espera ... ¿qué?'