Home » forums » LtU Forum

using foldr to do map

I am reading Hutton's book, programming in Haskell, and got stumped by a question. redefine map f using foldr. Since foldr is described as replacing (:) in a list with some provided operator it seemed it shouldn't be too hard.
foldr requires two components a what to do on empty list and the operator.

So I tried this:

> folmap :: (a -> b) -> [a] -> [b]
> folmap f = foldr (:.f) []

My reasoning is that you apply the : operator after f on every value in the list. (Though I may not understand the (.) I was thinking that if f = (a ->b) and g = (b -> c) then g.f would be g performed after f (or g.f is f followed by g).

Any advice??

By jdgallag at 2008-06-10 16:57 | LtU Forum | previous forum topic | next forum topic | other blogs | 8963 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Correct

Your solution seems correct to me. You just need extra parens around the colon operator to please the compiler: folmap f = foldr ((:) . f) [] (comp.lang.haskell is probably a better place for such questions though).

By Neil Madden at Tue, 2008-06-10 17:13 | login or register to post comments

Right idea

Just your syntax is a little off. First of all, : is an infix operator, so you need to convert it to a prefix operator by wrapping it in parentheses (:).

Also, due to warts of Haskell's syntax, I strongly recommend putting a space before and and after the composition operator when used infix, even though in some cases you can get away without it. It's overloaded for qualified names (e.g. Module.function), and (:.) is a valid infix operator name. So writing (:.f) is equivalent to (\x f -> x :. f) thanks to section syntax. (Actually, (:.) is a constructor name, and not just a function, so you have to introduce it in a data definition and you can pattern match against it too.)

It doesn't appear that you are too far from understanding (.). :) There isn't much to it, and it's really easy to define in any number of ways:

f . g = \x -> f (g x)
(f . g) x = f (g x)
(.) f g x = f (g x)
(.) f g = \x -> f (g x)
(.) f = \g -> \x -> f (g x)
(.) f = \g x -> f (g x)
(.) = \f g x -> f (g x)

etc etc. In Haskell, you have a lot of choices of syntax for the exact same thing. The only difference in these definitions is syntactic.

By Leon P Smith at Tue, 2008-06-10 17:36 | login or register to post comments

thanks, that did it

I had missed the parentheses around :

By jdgallag at Tue, 2008-06-10 23:28 | login or register to post comments