Leniwe dopasowywanie wzorca w Data.List

Question

Jakie są zalety wydajności związane z użyciem ~ (leniwego dopasowywania wzorca) w partycji Data.List. Wymyślone przykłady leniwego dopasowania wzorców sugerują, że jest to przydatne, gdy wartości wewnątrz konstruktora krotek nie są nigdy używane (f (x, y) = 1). W partycji (wybierz, poniżej), listy ts, fs są zawsze używane (jeśli predykat p zastosowany do x jest prawdziwy, czy nie). Jestem pewien, że jest to bardzo dobrze poinformowana decyzja, aby użyć ~, ale o co chodzi? Dlaczego nie ścisłe dopasowywanie wzorców?

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) 

(Uwaga: Ja już wyglądał here to nie jest odpowiedź na powyższe pytanie!)

Answer 1

Chodzi o to, że przy ścisłym dopasowaniu wzorca, montaż wyniku można uruchomić tylko wtedy, gdy koniec osiągnięta zostanie lista partycjonowana, w szczególności: partition nie będzie działać dla nieskończonych list.

Przy ścisłym dopasowaniu do wzorca argument musi zostać oceniony na WHNF. Oznacza to, że cały foldr ogona musi się zakończyć, zanim zdecyduje się, czy x zostanie umieszczony w pierwszym czy drugim komponencie.

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

Z lazy dopasowania wzorca, para jest wykonana bezpośrednio z x jako pierwszy element odpowiedniego składnika, a pozostałe dwa wykazach oceniano następnie w razie potrzeby.