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

Насколько я понимаю, 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) может закорачиваться, так как самый внешний f видит (&&) False ((&&) False (....)) видит первый аргумент как ложный и не должен оценивать второй аргумент (который является большим преобразователь).

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

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..

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


thunk lazy-evaluation fold haskell
person Ashish Negi    schedule 22.06.2016    source источник

Ответы (1)


arrow_upward
17
arrow_downward

Разница между 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 должно быть полностью повторено, прежде чем произойдет какое-либо реальное вычисление. (Не по теме: вот почему, даже когда это работает, foldl часто имеет ужасную производительность, а foldl' чаще используется на практике.)

В частности, опубликованный пример

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

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

person chi    schedule 22.06.2016