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/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
