[Haskell-cafe] foldl in terms of foldr

[Daniel Fischer]

Am Dienstag 26 Januar 2010 16:44:11 schrieb Xingzhi Pan:
> 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?
>

No, typo by Eduard, step :: b -> (a -> c) -> (a -> c).

foldr :: (t -> u -> u) -> u -> [t] -> u

, so t === b, u === a -> c

Now, in "foldr step id xs", id has type u === a -> c, hence c === a.