Re: [Haskell-cafe] Rewriting filter with foldr
Well, note that foldr takes a function of x, which produces a function of xs. This function of xs either conses x onto it, or leaves it unchanged. We can write this down explicitly by removing the xs parameter and just writing what function should be produced:
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?
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? Many thanks, Paul
On Sep 30, 2007, at 11:57 , PR Stanley wrote: > >> Well, note that foldr takes a function of x, which produces a >> function of xs. This function of xs either conses x onto it, or >> leaves it unchanged. We can write this down explicitly by >> removing the xs parameter and just writing what function should be >> produced: >> >> 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? > 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? > Many thanks, Paul Those are the same question, actually. He is returning a function which takes one argument (either the partial application / section (x:) which expects a list argument, or the function "id" which expects any argument and returns it unmodified); since one argument is left unconsumed, that typechecks. (This is, after all, functional programming; returning functions is not only possible, but encouraged.) This follows from the fact that all (normal) Haskell functions are curried, so (\x y -> something) is the same as (\x -> (\y -> something)), i.e. a 2-argument function is really a 1-argument function which returns a 1-argument function. Contrariwise, any time a 2-argument function is expected you can instead pass a 1-argument function which returns a 1-argument function. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@kf8nh.com system administrator [openafs,heimdal,too many hats] allbery@ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH
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/
participants (3)
-
Brandon S. Allbery KF8NH -
PR Stanley -
Tim Newsham