Почему foldl не является коротким замыканием с функцией andFn?

Question

Я понимаю, что foldl и foldr выполняет как:

foldl f a [1..30] =>(f (f (f ... (f a 1) 2) 3) ... 30)

и

foldr f a [1..30] =>(f 1 (f 2 (f 3 (f ....(f 30 a)))))..)

так .. foldr (&&) False (repeat False) может shortciruit, как внешний f видит (&&) False ((&&) False (....)) видит первый аргумент как false и не нужно оценивать второй аргумент (который является большим thunk).

так, что происходит с

andFn :: Bool -> Bool -> Bool 
andFn _ False = False 
andFn x True = x 

и

foldl andFn True (repeat False) -- => 

-- (andFn (andFn ...(andFn True False) ... False) False) 
-- ^^ outermost andFn 

Но это берет навсегда.

Я думал, что outermost andFn будет знать, что по шаблону на второй аргумент, ответ False ..

Что еще здесь происходит?

Answer 1

Существует большая разница между foldr и foldl, чем порядок аргументов andFn.

foldr f z (x:xs) = f x (foldr f z xs) 
foldl f z (x:xs) = foldl f (f z x) xs 

Обратите внимание, как foldr немедленно передает управление f: если f ленив он может избежать вычисления foldr f z xs.

Вместо foldl передает управление ... foldl: функция f будет только начать используется, когда основной корпус достиг

foldl f z [] = z  -- z contains the chained f's, which NOW get evaluated 

Следовательно foldl f z infiniteList будет всегда расходятся, независимо от того, что f является: весь infiniteList должен быть полностью повторен до того, как произойдет какое-либо реальное вычисление. (Off темы: вот почему, даже когда он работает, foldl часто имеет ужасную производительность, и foldl' больше используется на практике.)

В частности, размещен пример

foldl andFn True (repeat False) -- => 
-- (andFn (andFn ...(andFn True False) ... False) False) 
-- ^^ outermost andFn 

частично неправильно. «Самый внешний andFn» на самом деле был бы последним один, то есть тот, который связан с последним элементом в repeat False. Но такого зверя нет.