Map, Filter, Foldr in DrRacket/Scheme

Question

Programming language: Scheme/DrRacket

We're currently going over map, filter, and foldr in my comp sci class. I understand that all three can be used to create abstract functions, but I am honestly a little confused about the difference between the three and when I'd use each one.

Anyone care to explain what each is used for and how they are different? Unfortunately my book is not very clear.

Answer 1

The basic idea is that all three are ways of applying some function to all the elements of a list.

Map is perhaps the simplest--you just apply the function to each element of the list. This is basically the same as a for-each loop in other languages:

 (map (lambda (x) (+ x 1)) '(1 2 3))
   => (2 3 4)

Basically, map is like this: (map f '(1 2 3)) is the same as (list (f 1) (f 2) (f 3)).

Filter is also simple: the function acts like an arbiter, deciding whether to keep each number. Imagine a really picky eater going through a menu and whining about the things he won't eat ;)

 (filter (lambda (x) (equal? x 1)) '(1 2 3))
   => (1)

Fold is the hardest to understand, I think. A more intuitive name would be "accumulate". The idea is that you're "combining" the list as you go along. There are some functions in ever day use that are actually folds--sum is a perfect example.

 (foldr + 0 '(1 2 3)) 
   => 6

You can think of the fold as taking the function and putting it between each element in the list: (foldr + 0 '(1 2 3)) is the same as 1 + 2 + 3 + 0.

Fold is special because, unlike the other two, it usually returns a scalar value--something that was the element of the list rather than the list itself. (This isn't always true, but think of it this way for now anyway.)

Note that I may not have gotten every detail of the code perfect--I've only ever used a different, older implementation of Scheme so I might have missed some Racket details.

Answer 2

I can recommend these finger exercises (and the text that comes before):

http://htdp.org/2003-09-26/Book/curriculum-Z-H-27.html#node_idx_1464