We can see that we can use reduce/foldl1 as the function by which we can define other higher order functions such as map, filter and reverse.
(defn mapl [f coll]
(reduce (fn [r x] (conj r (f x)))
[] coll))
(defn filterl [pred coll]
(reduce (fn [r x] (if (pred x) (conj r x) r))
[] coll))
(defn mapcatl [f coll]
(reduce (fn [r x] (reduce conj r (f x)))
[] coll))
We also appear to be able to do this in terms of foldr. Here is map and filter in terms of foldr from Rich Hickey's Transducers talk at 17:25.
(defn mapr [f coll]
(foldr (fn [x r] (cons (f x) r))
() coll))
(defn filterr [pred coll]
(foldr (fn [x r] (if (pred x) (cons x r) r))
() coll))
Now it turns out there are some papers that explain this:
BIRD - Lectures on Constructive Functional Programming - 1988 https://www.cs.ox.ac.uk/files/3390/PRG69.pdf
HUTTON - A tutorial on the universality and expressiveness of fold - 1999 http://www.cs.nott.ac.uk/~gmh/fold.pdf
Now I heard somebody say this week:
well
flatmap(mapcat) is fundamental - you can express lots of higher order functions in terms of it.
So here is map implemented in terms of mapcat.
=> (defn mymap [f coll] (mapcat (comp vector f) coll))
=> (mymap #(+ 1 %) (range 0 9))
(1 2 3 4 5 6 7 8 9)
But to me that feels artificial since you're really just boxing things and working out whether map itself is 'fundamental'.
The reason this last example feels a little artificial is that mapcat is already defined in terms of map. If you look at the source for mapcat - we see something similar to:
(defn mapcat
[f & colls]
(apply concat (apply map f colls)))
So the example above merely reverses out the concat and reuses the underlying definition of map inside of mapcat - which to me feels artificial. Now it would be ok if mapcat could be used to define other HOFs - but I don't know how to do that - and I'm hoping someone can point me in that direction.
My question is: Is flatmap/mapcat a function that can be used as the basis of other higher order functions?
