Why foldr' uses $! instead of $

Learn
1

hi guys, I completely don’t understand what’s a benefit to use $! instead of $ in foldr’ implementation from GHC.List. Here are my thoughts:

  1. Here is foldr’ from GHC.List
foldr' :: (a -> b -> b) -> b -> [a] -> b
foldr' f a xs = foldl (\ g x -> \ acc -> g $! f a x) id xs 0
  1. And here is simple example
foldr' (+) 0 [1..3]
  1. I will rewrite inner guts of foldl in terms of classic example, not foldr, for simplicity
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f a [] = a
foldl f a (x:xs) = foldl f (f a x) xs
  1. I’m replacing x with elements from the list
f (f (f id 1) 2) 3
  1. I’m starting “unfold” the full expression to see what will be the final one
-- f id 1 = (\ g x -> \ acc -> g $! f a x) id 1
f (f (\ acc -> id $! 1 + acc) 2) 3
-- f (\ acc -> id $! 1 + acc) 2 = (\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc)
f (\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc) 3
-- f (\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc) 3 =
-- (\ acc -> (\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc) $! 3 + acc)
(\ acc -> (\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc) $! 3 + acc) 0
  1. Now the question: $! evaluates the second argument and passes it to the function, but here we don’t know when acc will appear, so we have to postpone evaluation, we are creating thunk. So why $! instead of $ here? If we finally get 0, it will be evaluated in any case with or without $! and then $ or $! will pass the result to another lambda and so on and so forth. So where is strict in foldr then?
\ acc -> id $! 3 + acc
-- for me they are equivalent
\ acc -> id $ 3 + acc

I believe that I’ve missed something but I don’t know what exactly - could you help me, please?

2

I can’t really follow how you unfold the expression. Here’s how I would write it:

foldr' (+) 0 (1:2:3:[])
=
foldl (\k x z -> k $! x + z) id (1:2:3:[]) 0
=
foldl (\k x z -> k $! x + z) (\z -> id $! 1 + z) (2:3:[]) 0
=
foldl (\k x z -> k $! x + z) (\z -> id $! (1 +) $! (2 +) z) (3:[]) 0
=
foldl (\k x z -> k $! x + z) (\z -> id $! (1 +) $! (2 +) $! (3 +) z) [] 0
=
id $! (1 +) $! (2 +) $! (3 +) 0
=
id $! (1 +) $! (2 +) $! 3
=
id $! (1 +) $! 5
=
id $! 6
=
6

If you’d use normal application instead of $!, it would end like this instead:

id (1 + (2 + (3 + 0)))
=
1 + (2 + (3 + 0))
=
1 + (2 + 3)
=
1 + 5
=
6

Not a huge difference, but that’s mainly because + is already strict.

3

wow, your unfold much cooler

but still, am I right that the only difference is that id applies last or I again missed something?

btw, do you know examples where it much cleaner see how foldr’ works? I mean difference between $! and $

4

I think I understood the difference:
in case of using $! expression will look like this

(\ acc -> (\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc) $! 3 + acc) 0
--
(\ acc -> (\ acc -> id $! 1 + acc) $! 2 + acc) $! 3
--
(\ acc -> id $! 1 + acc) $! 5
--
id $! 6
--
6

but with $ it will look like this

(\ acc -> (\ acc -> (\ acc -> id $ 1 + acc) $ 2 + acc) $ 3 + acc) 0
--
(\ acc -> (\ acc -> id $ 1 + acc) $ 2 + acc) $ 3 + 0
--
(\ acc -> id $ 1 + acc) $ 2 + (3 + 0)
--
id $ 1 + (2 + (3 + 0))
--

as you can the latter expression builds thunks and passing it further, at the end it will evaluate, however in this case in the heap will be a lot of thunks