[Haskell-cafe] Rewriting filter with foldr

[Tim Newsham]

>> 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/