Search code examples
schemesicpmap-functionflatmap

What is the significance of `flatmap` in SICP?

(define (accumulate op initial sequence) 
  (if (null? sequence) 
   initial 
   (op (car sequence) 
     (accumulate op initial (cdr sequence))))) 
      
(define (flatmap proc seq) 
  (accumulate append nil (map proc seq)))

The above is a code snippet from SICP, in Scheme. Why is the flatmap procedure needed? What is the difference between flatmap and map?

Solution

  • (map proc seq) will apply proc to the sequence seq, returning one value for each element. It is possible for each such value to be another sequence.

    (accumulate append nil seq) will use append to concatenate all copies of elements in seq into a new list.

    Thus, flatmap will apply proc to all elements of seq, and produce a new flattened list with all the results. Conceptually, this is the difference of map and flatmap in other languages as well (Java, Scala, etc.), in that map produces one value for each element, while flatmap may produce multiple or none (thanks Chris).

    For instance, in Clojure:

    (map #(clojure.string/split  % #"\s+") ["two birds" "with one stone"])
;; => (["two" "birds"] ["with" "one" "stone"])

(mapcat #(clojure.string/split  % #"\s+") ["two birds" "with one stone"])
;; => ("two" "birds" "with" "one" "stone")