4

I've recently began studying Haskell and in one of my assignments I've got an exercise which asks to define the map function in terms of foldr, and I can't for the life of me figure out how to do this. I've searched stack overflow for solutions and came across this one:

How would you define map and filter using foldr in Haskell?

However here the solution involves using lambdas, which I haven't covered yet and I assume that because of this the exercise should be doable without lambdas (although you never know).

I guess what confuses me the most is that map takes in a unary function (e.g. +1), whereas foldr takes a binary function (e.g. +), and I don't really see how to make these two work together.

Community
  • 1
  • 1
user3062734
  • 95
  • 1
  • 6
  • 4
    Everything is doable without lambdas. Just create a named function that does the same thing. As for how to approach this, figure out how to write `id :: [a] -> [a]` with `foldr`. Then remember that `id :: [a] -> [a]` is the same thing as `map (id :: a -> a)`, and figure out where you need to apply the extra function. – Carl Dec 03 '13 at 18:36
  • 1
    There is no difference between what you call a "lambda" and any other function. They're all just functions. What's being shown there is the syntax for defining a function without a name. – Chuck Dec 03 '13 at 18:41
  • 1
    Relevant: http://web.jaguarpaw.co.uk/~tom/blog/posts/2012-11-04-what-is-foldr-made-of.html – Tom Ellis Dec 04 '13 at 01:02
  • try wikipedia, http://en.wikipedia.org/wiki/Fold_(higher-order_function) :) – JJJ Dec 04 '13 at 08:24
  • @TomEllis `left_fold f z xs = let rs = z : zipWith f xs rs in last rs` ; zipWith is a map: `zipWith f a b = map (uncurry f) $ zip a b` (although, `last` is kind of a fold...(?)). But, ignoring that, `rev xs = left_fold (flip (:)) [] xs` (reverse is a left fold); and then `right_fold f z xs = let rs = z : zipWith f (rev xs) rs in last rs`. cf. http://stackoverflow.com/a/11951590/849891. – Will Ness Dec 04 '13 at 14:03

2 Answers2

7

foldr is actually easy: Given a list (written with : and []) like

a : (b : (c : (d : [])))

then applying foldr h x to it will replace every : with `h` and [] with x:

a `h` (b `h` (c `h` (d `h` x)))

Compare that with what map f would to the list:

f a : (f b : (f c : (f d : [])))

This should guide you in choosing h and x so that foldr h x = map f.

Joachim Breitner
  • 25,395
  • 6
  • 78
  • 139
5

foldr decomposes a list from the right and allows you to thread an accumulated value through the compuation. Since map preserves the length of the list, you need to thread a new list through, which contains the transformed values.

The type of foldr is (a -> b -> b) -> b -> [a] -> b

Your accumulator function takes the state (the new list being constructed) and the current list element, and you need to create a new list which contains the element transformed by the mapping function.

The second argument to foldr is the initial accumulator value, and this is the value returned if the input list is empty, so you should be able to use this to figure out what it should be for you map function.

Lee
  • 142,018
  • 20
  • 234
  • 287