Dean Herington heringtonlacey at mindspring.com
Mon Sep 12 03:41:06 EDT 2005

```At 11:44 PM +0000 9/10/05, Thomas Spriggs wrote:
>>From: gary ng <garyng2000 at yahoo.com>
>>
>>fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
>
>>Would appreciate if someone can knock on my head and
>>tell me what is going on in it.
>Well, here goes. The way the lambda function/foldr thing evaluates,
>the resulting foldl like function needs a new identity parameter
>hence the additional "1". To demonstrate something like how this is
>evaluated for a low number eg 3: (Please would someone correct me if
>I have made a mistake in this)
>fac 3 = (foldr (\x g n -> g (x*n)) id [1..3]) 1
>fac 3 = (foldr (\x g n -> g (x*n)) id [1,2,3]) 1
>fac 3 = (foldr (\x g n -> g (x*n)) (\n -> id (3*n)) [1,2])) 1
>fac 3 = (foldr (\x g n -> g (x*n)) (\n -> (\n -> id (3*n)) (2*n)) [1]) 1
>fac 3 = (foldr (\x g n -> g (x*n)) (\n -> (\n -> (\n -> id (3*n))
>(2*n)) (1*n)) []) 1
>fac 3 = (\n -> (\n -> (\n -> id (3*n)) (2*n)) (1*n)) 1
>fac 3 = (\n -> (\n -> id (3*n)) (2*n)) (1*1)
>fac 3 = (\n -> (\n -> id (3*n)) (2*n)) 1
>fac 3 = (\n -> id (3*n)) (2*1)
>fac 3 = (\n -> id (3*n)) 2
>fac 3 = id (3*2)
>fac 3 = id 6
>fac 3 = 6

Your equations are correct, but I find the (first part of the)
sequence a bit confusing because it doesn't follow directly from the
definition of foldr.  Here's how I would explain it:

From the prelude definition:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Rewriting for conciseness:
fac n = (ffz [1..n]) 1  where ffz = foldr (\x g n -> g (x*n)) id

fac 3 = (ffz [1,2,3]) 1
= (\n1 -> (ffz [2,3]) (1*n1)) 1
= (\n1 -> (\n2 -> (ffz [3]) (2*n2)) (1*n1)) 1
= (\n1 -> (\n2 -> (\n3 -> (ffz []) (3*n3)) (2*n2)) (1*n1)) 1
= (\n1 -> (\n2 -> (\n3 -> id (3*n3)) (2*n2)) (1*n1)) 1
= (\n2 -> (\n3 -> id (3*n3)) (2*n2)) (1*1)
= (\n3 -> id (3*n3)) (2*(1*1))
= id (3*(2*(1*1)))
= (3*(2*(1*1)))
= 6
```