Почему `foldl1` исчерпывает память, а` foldr1` работает нормально?

Question

Я написал last функцию с помощью foldl1 и foldr1.

lastr :: [a] -> a 
lastr = foldr1 (flip const) 

lastl :: [a] -> a 
lastl = foldl1 (flip const) 

Они просто отлично работают для коротких списков. Но когда я пробовал с очень длинным списком, [1..10^8], lastr возвращает решение в 6,94 секунды, а у последнего не хватало памяти.

Определения foldr1 и foldl1 являются (в мое понимание)

foldr1 f [x] = x 
foldr1 f (x:xs) = f x $ foldr1 f xs 

и

foldl1 f [x] = x 
foldl1 f (x:y:ys)=foldl1 f $ f x y : ys 

виден из этих, foldl1, кажется, используют меньше памяти, чем foldr1, потому что foldr1 нужно держать такое выражение f x1 $ f x2 $ f x3 $ f x4 $..., в то время как foldl1 может просто вычислить f x y каждый раз и сохранить его как элемент главы списка вместо того, чтобы удерживать его, пока он не достигнет 10^8.

Может ли кто-нибудь сказать мне, что не так с моим аргументом?

Answer 1

Правая складка может начать производить немедленно, если функция объединения является ленивой во втором аргументе. Упрощенный пример:

foldr1 (++) ["one", "two", "three", ...] 
    ~> "one" ++ foldr1 (++) ["two", "three", ...] 

и первая часть результата сразу же доступны без дальнейшей оценки второго аргумента (++). Это нужно оценивать только тогда, когда потребляется первая часть. Часто первая часть может быть уже собрана в мусор.

В примере с f = flip const как функции комбинирования, мы имеем другую ситуацию, то есть строгое ⁽¹⁾ во втором аргументе, но не требует, чтобы оценить его вообще. И он игнорирует его первый. Это также хорошо для правильных складок. Вот он идет

foldr1 f [x1, x2, x3, ... ] 
    ~> f x1 (foldr1 f [x2, x3, ... ]) 

и теперь внешний f может сразу же оценили

~> foldr1 f [x2, x3, ... ] 
    ~> f x2 (foldr1 f [x3, ... ]) 
    ~> foldr1 f [x3, ... ] 

и на каждом шаге, внешний f всегда можно сразу оценили (полностью), и один элемент списка выбрасываются.

Если список задается генератором, который может создать его в постоянном пространстве, когда последовательно потребляются,

last = foldr1 (flip const) 

может работать в постоянном пространстве.

С левой складкой все меняется. Так как это хвостовая рекурсия

foldl1 f (x:y:zs) = foldl f x (y:zs) = foldl f (f x y) zs 

он ничего не может вернуть до того, как сгиб достигнет конца списка. В частности, левая складка никогда не может заканчиваться бесконечным списком.

Теперь, глядя на нашем случае f = flip const мы находим

foldl1 f [x1, x2, x3, x4, ...] 
    ~> foldl f x1 [x2, x3, x4, ... ] 
    ~> foldl f (f x1 x2) [x3, x4, ... ] 
    ~> foldl f (f (f x1 x2) x3) [x4, ... ] 

Конечно можно было бы немедленно оценить f x1 x2 к x2, а затем f x2 x3 = x3, но это возможно только для этого специального f.

С foldl является общей функцией более высокого порядка, он не может оценивать промежуточные результаты до того, как они понадобятся, поскольку возможно, что промежуточные результаты никогда не нужны - и на самом деле они никогда не нужны здесь, в конце список, один получает выражение

f (f (f (f ...y3) y2) y1) y0 
    ~> y0 

, а затем внешний f можно оценить, не смотря на огромный стуке вложенных f с, который строит первый аргумент.

foldl (соотв. foldl1) не может знать, что было бы гораздо эффективнее немедленно оценить промежуточные результаты.

Строгие левые складки, foldl' и foldl1' сделать это, они оценивают промежуточные результаты в слабой головной нормальной форме (конструктору значение внешней или лямбда), а

last = foldl1' (flip const) 

также будет очень эффективным.

Но, поскольку промежуточные результаты оцениваются дальше, чем с foldr, они были бы чуть менее эффективным, и, что важно, если какой-либо элемент списка является ⊥, версия foldl1' вернется ⊥:

foldl1' f [x1, ⊥, x3, x4] 
    ~> foldl' f x1 [⊥, x3, x4] 
    ~> case f x1 ⊥ of 
      pattern -- that causes ⊥ 
    ~> ⊥ 

тогда как версия foldr1 не имеет проблем с этим, поскольку она не проверяет элементы списка или промежуточные результаты вообще.

---

⁽¹⁾ Это f строго в его второй аргумент означает, что

f x ⊥ = ⊥ 

Поскольку f просто возвращает свой второй аргумент, что, очевидно, имеет место.