At 11:44 PM +0000 9/10/05, Thomas Spriggs wrote:
From: gary ng
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