Почему фолдр не такой строгий, как фолдл? - PullRequest
Новая
       116

Почему фолдр не такой строгий, как фолдл?

6 голосов
/ 06 августа 2020

Рассмотрим эти различные попытки чего-то, что работает как last: 

Prelude> import Data.Foldable
Prelude Data.Foldable> foldr const undefined (reverse [1,2,3])
3
Prelude Data.Foldable> foldr' const undefined (reverse [1,2,3])
3
Prelude Data.Foldable> foldl (flip const) undefined [1,2,3]
3
Prelude Data.Foldable> foldl' (flip const) undefined [1,2,3]
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:5:21 in interactive:Ghci4

Для меня имеет смысл, что foldl и foldr работают, так как они не строги в своем аккумуляторе. , и мне кажется логичным, что foldl' этого не делает, поскольку это так. Но почему foldr' работает? А в аккумуляторе тоже должно быть строго?

1 Ответ

3 голосов
/ 06 августа 2020

Для справки: экземпляр Foldable [] переопределяет foldr, foldl, foldl', но не foldr' ( источник ): 

instance Foldable [] where
    elem    = List.elem
    foldl   = List.foldl
    foldl'  = List.foldl'
    foldl1  = List.foldl1
    foldr   = List.foldr
    {- ... -}

foldr' по умолчанию определяется как ( source ): 

foldr' :: (a -> b -> b) -> b -> t a -> b
foldr' f z0 xs = foldl f' id xs z0
  where f' k x z = k $! f x z

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

Это предлагает другую реализацию, которая заставляет аккумулятор: 

foldr'' :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr'' f = foldr (\x z -> f x $! z)

(Отредактировано: предыдущая версия была специализирована для списков.)

Понятия не имею, почему одно было предпочтено другому. Вероятно, это недосмотр, и для foldr' было бы более логично не использовать реализацию по умолчанию в экземпляре Foldable [].

Кроме того, определение по умолчанию foldl' также отличается от указанного в списке таким же образом: 

-- Default (class Foldable t where ...)
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
  where f' x k z = k $! f z x

-- List implementation
foldl'           :: forall a b . (b -> a -> b) -> b -> [a] -> b
foldl' k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> z `seq` fn (k z v))) (id :: b -> b) xs z0
...