uso múltiple de ++: ¿más eficiente si forzo la evaluación de derecha a izquierda?

Question

Quiero agregar 3 listas o más a la vez en una sola expresión.

a ++ b ++ c 

¿El operador ++ se evaluará de izquierda a derecha o de derecha a izquierda?

1. (a ++ b) ++ c 
2. a ++ (b ++ c) 

yo diría que la opción 2, porque si ++ era una función de prefijo, escribiríamos ++ a ++ b c que conduce naturalmente a la evaluación de ++ b c primero. No estoy seguro si estoy en lo correcto.

Pero si se trata de la opción 1, me parece que explícitamente cambiar el orden de evaluación de derecha a izquierda es más eficiente:

a ++ (b ++ c) 

He aquí por qué: a ++ b ++ c primero evaluar a ab ++ c en n pasos (donde n es la longitud de a y ab es, por supuesto, la concatenación de ayb) y luego a abc en n + m más pasos (m es la longitud de b, así n + m es la longitud de ab), que hace un total de 2n + m pasos. Mientras que a ++ (b ++ c) primero evaluará a a ++ bc en m pasos, y luego a abc en n pasos más, que es un total de n + m solamente.

Soy nuevo en haskell y no estoy seguro de lo que estoy diciendo, me gustaría obtener alguna confirmación.

Answer 1

a ++ b ++ c 

se analiza como

a ++ (b ++ c) 

exactamente por las razones que usted describe: tenía (++) sido asociativos por la izquierda, luego a ++ b ++ c copiariamos a dos veces. Esto se puede comprobar en GHCi con

Prelude> :i (++) 

que responderá con

infixr 5 ++ 

donde infixr significa "infija, asociativo por la derecha".

Answer 2

De ghci, hacer un :i:

Prelude> :i (++) 
(++) :: [a] -> [a] -> [a] -- Defined in GHC.Base 
infixr 5 ++ 

lo que demuestra que es ++ (infija y) asociativo por la derecha, y serán evaluados de derecha a izquierda. No lo sé, pero estaría dispuesto a apostar que quien lo implementó tenía su pregunta en mente cuando lo hizo correctamente asociativo.

Answer 3

También hay concat función que concatena cualquier número de listas:

Prelude> :t concat 
concat :: [[a]] -> [a] 
Prelude> concat [[1], [2,3], [42,911]] 
[1,2,3,42,911]