[Haskell-cafe] Rewriting filter with foldr
Tim Newsham
newsham at lava.net
Sun Sep 30 14:12:33 EDT 2007
>> filter f = foldr (\x -> if (f x) then (x:) else id) []
> That's one neat solution but it also raises a few questions for me:
> foldr :: (a -> b -> b) -> b -> [a] -> b
> yet you've managed to squeeze in a function that takes only one argument. How
> is this possible without GHCI blowing its top?
Someone already explained this so I'll skip it.
> 2. Could you please explain the role of the identity function (id) in your
> code? Where's its argument, or is it sort of implicitly noted? For example,
> is it the case that the second argument is held in reserve and passed to the
> first function which would take it, hence (x:) and id?
How about working through an example?
[I'm using notes on the left hand side. a number starting
with a colon is a reference to a definition, and a word
followed by a close paren ")" is a justification for the step.]
1: filter f = foldr (\x -> if (f x) then (x:) else id) []
2: foldr k z xs = go xs
3: where go [] = z
4: go (y:ys) = y `k` go ys
filter (> 3) [5,2,6]
1) = foldr (\x -> if (> 3) x then (x:) else id) [] [5,2,6]
2) = go [5,2,6]
where
5: go [] = []
6: go (y:ys) = (\x -> if (> 3) x then (x:) else id) y (go ys)
6) = (\x -> if (> 3) x then (x:) else id) 5 (go [2,6])
lambda) = (if (> 3) 5 then (5:) else id) (go [2,6])
if) = (5:) (go [2,6])
6) = (5:) ((\x -> if (> 3) x then (x:) else id) 2 (go [6]))
lambda) = (5:) (if (> 3) 2 then (2:) else id) (go [6]))
if) = (5:) (id (go [6]))
id) = (5:) (go [6])
6) = (5:) ((\x -> if (> 3) x then (x:) else id) 6 (go []))
lambda) = (5:) (if (> 3) 6 then (6:) else id) (go []))
if) = (5:) ((6:) (go []))
5) = (5:) ((6:) [])
(6:)) = (5:) [6]
(5:)) = [5, 6]
So you can see that its building up a chain of one-argument
functions such as:
(5:) (id ((6:) []))
before collapsing it down to a list like
[5,6]
(note to save space, I collapsed the "id" term early. If I left
it till longer we would have arrived at the expression above).
> Many thanks, Paul
Tim Newsham
http://www.thenewsh.com/~newsham/
More information about the Haskell-Cafe
mailing list