Coincidencia de patrón diferido en Data.List

Question

¿Cuáles son los beneficios de rendimiento de usar ~ (coincidencia de patrón diferido) en la partición de Data.List? Los ejemplos de adaptación de patrones perezosos sugieren que es útil cuando los valores dentro del constructor de tuplas nunca se usan (f (x, y) = 1). En la partición (seleccionar, abajo), las listas ts, fs siempre se usan (si el predicado p aplicado a x es verdadero o no). Estoy seguro de que esta es una decisión muy bien informada para usar ~, pero ¿cuál es el punto? ¿Por qué no emparejar patrones estrictos?

partition    :: (a -> Bool) -> [a] -> ([a],[a]) 
{-# INLINE partition #-} 
partition p xs = foldr (select p) ([],[]) xs 

select :: (a -> Bool) -> a -> ([a], [a]) -> ([a], [a]) 
select p x ~(ts,fs) | p x  = (x:ts,fs) 
        | otherwise = (ts, x:fs) 

(Nota: Ya he mirado here que no responde a la pregunta anterior!)

Answer 1

El punto es que con estricta concordancia con el modelo, el montaje del resultado sólo podría comenzar cuando el fin de se ha llegado a la lista para ser particionada, en particular, partition no funcionaría en absoluto para listas infinitas.

Con una concordancia de patrón estricta, el argumento debe evaluarse a WHNF. Eso significa que el foldr completo de la cola debe haber terminado antes de que se decida si x se coloca en el primer o el segundo componente.

select p x (foldr (select p) ([],[]) (y:z:ws)) 
~> select p x (select p y (select p z (foldr (select p) ([],[]) ws))) 

Con una coincidencia de patrón perezoso, un par se construye de inmediato, con x como el primer elemento de la función apropiada del componente, y el resto de las dos listas para ser evaluados después, cuando sea necesario.