Haskell: Более строгая складка с помощью deepseq

Страница Foldr Foldl Foldl'обсуждает foldl'и определяет его следующим образом:

foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x 
                    in seq z' $ foldl' f z' xs

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

Однако это не обязательно работает, как указано здесь:

Задействованная функция seqвычисляет только самый верхний конструктор. Если аккумулятор является более сложным объектом, то fold'по-прежнему будет создавать неоцененные санки.

Очевидное решение — заменить seqнаdeepseq , как показано (при условии, что вы работаете сNFData):

foldl_strict f z []     = z
foldl_strict f z (x:xs) = let z' = z `f` x 
                          in deepseq z' $ foldl_strict f z' xs

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

Затем я попробовал следующее:

foldl_stricter  f z l      = deepseq z $ foldl_stricter' f z l
foldl_stricter' f z []     = z
foldl_stricter' f z (x:xs) = let z' = deepseq x $ z `f` x 
                             in seq z' $ foldl_stricter' f z' xs

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

foldl_stricter (\x y -> x + head y) 0 [[1..],[2..]]

Таким образом, fold_stricterслишком строг. Список не обязательно должен быть строгим, для предотвращения утечки пространства важно, чтобы аккумулятор был строгим. fold_stricterзаходит слишком далеко и также делает список строгим, что приводит к сбою вышеописанного.

Что возвращает нас к fold_strict.Повторный запуск deepseqдля структуры данных размером nзанимает O(n)времени или только O(n)времени в первый раз и O(1)после этого? (Как предлагает dbauppв своем комментарииниже)