[Haskell-cafe] foldl in terms of foldr
daniel.is.fischer at web.de
Tue Jan 26 10:59:15 EST 2010
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.
More information about the Haskell-Cafe