Why does foldr return immediately?

Question

Newbie to Haskell.

Trying to figure out why:

foldr (\_ _ -> 1) 2 [1..]

returns 1 immediately, however:

foldl (\_ _ -> 1) 2 [1..]

runs forever.

Reading some source code, but stuck at some #.s .

Help me out. (Run tests on Windows GHC 7.10.3)

Answer 1

That source is the default Foldable implementation of foldr, it's not the actual implementation for lists. The actual implementation is straightforward:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

The result of foldr (\_ _ -> 1) 2 [1..] can be understood by substitution:

foldr (\_ _ -> 1) 2 [1..] 
go [1..]                  
go (1 : [2..])            -- evaluate [1..]
(\_ _ -> 1) 1 (go [2..])  -- evaluate `go` at (:) case
1                         -- evaluate expression

Answer 2

Specifically in GHC, foldl is actually implemented by foldr:

foldl :: forall a b. (b -> a -> b) -> b -> [a] -> b
{-# INLINE foldl #-}
foldl k z0 xs =
  foldr (\(v::a) (fn::b->b) -> oneShot (\(z::b) -> fn (k z v))) (id :: b -> b) xs z0

So no matter your folding function evaluates the parameters or not, it will build a composed function from the list and pass the initial value to it, so will not terminate with infinite list.