[Haskell-cafe] Rewriting filter with foldr
Brandon S. Allbery KF8NH
allbery at ece.cmu.edu
Sun Sep 30 12:09:47 EDT 2007
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 at kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery at ece.cmu.edu
electrical and computer engineering, carnegie mellon university KF8NH
More information about the Haskell-Cafe
mailing list