haskell - online - Coincidencia de patrones perezosos en Data.List

haskell online

Question

¿Cuáles son los beneficios de rendimiento de usar ~ (coincidencia de patrones diferida) en la partición de Data.List? Los ejemplos combinados de coincidencia 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 (seleccione, a continuación), las listas ts, fs se usan siempre (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 un patrón estricto?

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 ! No responde la pregunta anterior)

Answer 1

El punto es que con la coincidencia estricta de patrones, el ensamblaje del resultado solo puede comenzar cuando se llega al final de la lista para particionar, en particular, la partition no funcionaría en absoluto para las listas infinitas.

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

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 inmediatamente, con x como el primer elemento del componente apropiado, y el resto de las dos listas se evaluarán más adelante, cuando sea necesario.