[Haskell-cafe] Rewriting filter with foldr

[Brandon S. Allbery KF8NH]

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