[Haskell-cafe] foldl in terms of foldr

[Neil Brown]

Xingzhi Pan wrote:
> On Tue, Jan 26, 2010 at 11:24 PM, Eduard Sergeev
> <Eduard.Sergeev at gmail.com> wrote:
>   
>> Xingzhi Pan wrote:
>>     
>>> The first argument to foldr is of type (a -> b -> a), which takes 2
>>> arguments.  But 'step' here is defined as a function taking 3
>>> arguments.  What am I missing here?
>>>       
>> You can think of step as a function of two arguments which returns a
>> function with one argument (although in reality, as any curried function,
>> 'step' is _one_ argument function anyway):
>> step :: b -> (a -> c) -> (b -> c)
>>
>> e.g. 'step' could have been defined as such:
>> step x g = \a -> g (f a x)
>>
>> to save on lambda 'a' was moved to argument list.
>>     
>
> Right.  But then step is of the type "b -> (a -> c) -> (b -> c)".  But
> as the first argument to foldr, does it agree with (a -> b -> a),
> which was what I saw when I type ":t foldr" in ghci?
>   
step is of type b -> (a -> a) -> (a -> a), which does agree with (a -> b 
-> b), the first argument to foldr (what you posted, both times, a -> b 
-> a, is the type of the first argument of *foldl* not foldr).  The code 
is building up a function (type: a -> a) from the list items, which it 
then applies to the initial value given to foldl.

Thanks,

Neil.