From Map/Reduce to JavaScript Functional Programming

Since ECMAScript 5.1, Array.prototype.map & Array.prototype.reduce were introduced to major browsers. These two functions not only allow developers to describe a computation more clearly, but also to simplify the work of writing loops for traversing an array; especially when the looping code actually is for mapping the array to a new array, or for the accumulation, checksum, and other similar reducing operations.

Left: using ordinary loop; Right: using map & reduce

Left: using ordinary loop; Right: using map & reduce

 

Map/Reduce

Map actually means to compute things with the original array without doing structural changes to the output. For example, when map receives an array, you can make sure the output will be another array, and the only difference is that the elements inside it may be transformed from the original value/type to another value/type. So we can say the doMap function from the above example comes with the following type signature:

doMap signature

The signature reveals that [Number] means this is an array of numbers. So we now can read the signature as:

doMap is a function, which would turn an array of numbers to an array of booleans

On the other hand, the reducing operation means we may change the structure of the input data type to a new one. For example, the signature of the doReduce is:

doReduce signature

Here, the Array of [Number] is gone. So we can see the major difference between map and reduce1.

Functional Programming

In fact, the concepts of map and reduce are older even than JavaScript and are widely used in other functional programming languages, such as Lisp or Haskell2. This observation is noted in the famous article ‘JavaScript: The World’s Most Misunderstood Programming Language’ by Douglas Crockford 3:

JavaScript’s C-like syntax, including curly braces and the clunky for statement, makes it appear to be an ordinary procedural language. This is misleading because JavaScript has more in common with functional languages like Lisp or Scheme than with C or Java.

This is one reason why JavaScript can do some functional-like things which other orthogonal OOP languages can’t or won’t do. For example, before Java 8 4 5, if we wanted to do some ‘callback’ things common in JavaScript, we’d need to create a redundant ‘anonymous class.’:

Button button =
  (Button) findViewById(R.id.button);
button.setOnClickListener(
  new OnClickListener() {
    public void onClick(View v) {
      // do something
    }
  }
);

Of course, using anonymous callbacks or not in JavaScript is always controversial. We may encounter callback hell especially when the component keeps growing. However, first-class functions can do lots of things beyond the callback. In Haskell, we can organize our whole GUI program similar to the Quake-like games6 with only functions7. That is, we can even make it without the classes, methods, inheritance, templates and other stuff8 people usually expect to have when a program needs to be constructed.

Frag

Frag, the Quake-like game in Haskell

Therefore, in the JavaScript world, it’s possible to follow similar patterns to construct our programs, rather than hurriedly implementing our own ‘class’ and ‘class system,’ as programmers often do when starting on a problem9. Adding some functional flavor in JavaScript is not so bad after all, especially when features like map and reduce are supported by native APIs. To adopt this approach also means we can write more concise code10 by combining features instead of redefining them. The only limitation is the language itself is still not functional enough, so we may run into trouble if we play too many tricks, although this should be solvable with the right library11.

map and reduce receive other functions as arguments and output them as results. This is important because in this way they present the basic idea of composing computations in the functional world, and are able to glue small pieces together with flexibility and scalability. For example, let’s take a look at the signature of our map expression mentioned above:

map signature

You’ll notice that the second argument indicates a function with type Number -> Boolean. In fact, you can give it any function with a -> b type. This may not be so odd in the world of JavaScript — we write tons of callbacks in our daily work. However, the point is that higher-order functions are functions as well. They can be composed into larger ones till we generate the complete program with only first-class functions and some powerful high-order functions like id, reduce, curry, uncurry, arrow and bind12.

Map/Reduce in Practice

Since we may encounter language limitations, we can’t write our JavaScript code in fully functional style; however, we can borrow the idea of types and composition to do lots of things. For example, when you think in types, you will find that map is not only for data handling:

map & fold signatures

This is what the type signatures for map and reduce would look like in Haskell. We can substitute the a and b with anything. So, what if a becomes SQL and b becomes IO x ? Remember, we’re thinking in type, and IO x is nothing more than an ordinary type like Int or URL:

-- Let's construct queries from SQL statements.
makeQueries strs = map str  prepare conn str
doQuery qrys = foldl (results query  results >> query) (return ()) qrys 
-- Do query and get results.
let stmts = [ "INSERT INTO Articles ('Functional JavaScript')"
            , "INSERT INTO Gecko VALUES ('30.a1')"
            , "DELETE FROM Articles WHERE version='deprecated'"
            ]
main = execute (doQuery (makeQuery stmts))`

(Note: This is a simplified Haskell example for demo only. It can’t actually be executed.)

The example creates a makeQueries function with map, which will turn the SQL into IO ()13; this also means we generate several actions which can be performed.

makeQueries signature

And then, the doQuery function, which is actually a reducing operation, will execute the queries:

doQueries signature

Note its reducing operation performs IO action with the help of the bind function (>>) of the specific Monad. This topic is not covered in this article, but readers should imagine this as a way to compose functions to execute them step by step, just as a Promise does24.

The technique is useful not only in Haskell but also in JavaScript. We can use this idea with Promises and ES6 arrow functions to organize a similar computation:

  // Use a Promise-based library to do IO.
  var http = require("q-io/http")
     ,noop = new Promise(()=>{})
     ,prepare =
        (str)=> http.read('http://www.example.com/' + str)
                  .then((res)=> res.body.toString())
                  // the 'then' is equal to the '>>'
     ,makeQuery = 
        (strs)=> strs.map((str)=> prepare(str))
     ,doQuery = 
        (qrys)=> qrys.reduce((results, qry)=> results.then(qry), noop)
     ,stmts = [ "articles/FunctionalJavaScript"
              , "blob/c745ef73-ece9-46da-8f66-ebes574789b1"
              , "books/language/Haskell"
              ]
     ,main = doQuery(makeQuery(stmts));

(NOTE: In Node.js, the similar querying code with map/reduce and Promise would not run like the Haskell version, since we need Lazy Promise14 and Lazy Evaluation15)

We’re very close to what we want: define computations with functions, and then combine them to perform it later, although the idea of ‘later’ is not actually true since we don’t have real lazy evaluation in JavaScript. This can be accomplished if we play the trick of keeping an undone Promise — a resolve function which is only resolved when we want to do so. However, even this is tricky, and there are still some unsolvable issues.

Another thing to note is that our program doesn’t need variable variables, but some computation results are transformed and forwarded at every step of our program. In fact, this is just one reason why functional languages can stay pure, and thus they can benefit from the optimization and getting rid of unexpected side-effects 1617.

More on Functional Programming

Map/reduce are the most common functional features in JavaScript. With other not-so-functional features like Promise, we can use tricks like Monad-style computation control, or we can easily define curried functions with ES6’s fat-arrow functions18 and so on. Also, there are some excellent libraries which provide nice functional features19 20 21, and some Domain Specific Languages (DSLs) are even born with functional spirit 22 23. Of course, the best way to understand functional programming is to learn a language designed for it, like Haskell, ML or OCaml. Scala, F#, and Erlang are good choices, too.


1. In fact, map can be implemented with reduce. The most basic operation for structure like this is reduce.
https://github.com/timoxley/functional-javascript-workshop/blob/440da6737f34b4550301ba3a77b2e4b7721e99fd/problems/implement_map_with_reduce/solution.js#L11

2. http://en.wikipedia.org/wiki/Lisp_(programming_language)#Control_structures

3. http://javascript.crockford.com/javascript.html

4. Java 8 now includes the lambda function: https://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html

5. C++ traditionally has not been a functional language, but C++11 introduces lambda functions: http://en.wikipedia.org/wiki/C%2B%2B11#Lambda_functions_and_expressions

6. https://www.haskell.org/haskellwiki/Frag

7. Haskell can represent data structure in function sense, even though declaring a function and a data type are still not the same thing: http://book.realworldhaskell.org/read/data-structures.html

8. Yes, I’m cheating: we have Typeclass, Functor, instance and type variable in Haskell.

9. For those who can’t live without classes, ES6 is in your future: http://wiki.ecmascript.org/doku.php?id=strawman:maximally_minimal_classes

10. I’ve found that some ‘bad functional code’ can be refactored as concisely as possible by strictly following some functional patterns. The most problematic ‘functional’ code happens when the coder mixes two programming styles badly. This can mix problems from two paradigms in a way that makes the code more complicated.

11. I always hit a wall when I want to have nice Monad and lazy Promise in JavaScript. However, if you don’t mind a ‘crazy’ implementation, these are doable, and we can even have ‘Monad Transformer’ in JavaScript. Other features, like tail-recursion optimization and real lazy-evaluation, are impossible to do without runtime support.

12. The functions arrow and bind are actually >>> and >>= in Haskell. They’re the keys In Haskell to compose our computation and program with specific effects; hence we can have state machine, networking, event handling, IO statements, and asynchronous flow control. Importantly, these are still plain functions.

13. The type IO () means ‘do IO without any value returned.’ The IO a means some IO actions may get value a when the function had been performed, although some actions only get (). For example, the function to get a string from user input would be: ask:: IO String, while the function to print string out is print:: String -> IO String.

14. http://www.jroller.com/vaclav/entry/promises_getting_lazy

15. http://www.haskell.org/haskellwiki/Lazy_evaluation

16. JavaScript can do this with a library for structures like map, set, and list. Facebook created a library of immutable data structures called immutable-js for this: https://github.com/facebook/immutable-js

17. You can do almost the same thing with immutable-js and convince everyone to use only let and const to define variables.

18. http://wiki.ecmascript.org/doku.php?id=harmony:arrow_function_syntax

19. wu.js: http://fitzgen.github.io/wu.js/

20. Ramda: http://ramdajs.com/ramdocs/docs/

21. transducer.js: http://jlongster.com/Transducers.js–A-JavaScript-Library-for-Transformation-of-Data

22. LiveScript: http://livescript.net/

23. Elm: http://elm-lang.org/

24. No, they’re not really the same, but you *could* implement Promise in Monad


5 comments

  1. Gleb Bahmutov

    I believe immediate transition from typical imperative JavaScript to functional or reactive programming with event streams is too drastic of a change. I recommend step by step gradual progression as I describe in http://bahmutov.calepin.co/journey-from-procedural-to-reactive-javascript-with-stops.html

    January 30th, 2015 at 08:22

  2. Kyle Kress

    Great conceptual article. I’ve been doing quite a lot of functional exploration in the last year and most recently Elm, as mentioned in the footnotes. I think the biggest inherent problem though is that currently you pretty much have to shoehorn these paradigms into JavaScript—even if it’s ‘possible’. In JavaScript’s native .map you call everything in a backward order than say a Haskell list map. JavaScript it’s `array .map (func)` or using `Array.prototype.map ( array, func )` or even LoDash/Underscore `_.map ( array, func )`—whereas in Haskell it’s `map func list` in that order. This messes up currying and composability. Libraries like Ramda (also mentioned in the footnotes) have addressed this—but that’s the thing, you need a library to use these higher-order functions with sanity in JavaScript currently. Not to mention natively you have to either define map on all your prototypes or strangely call Array.prototype.map on something like a NodeList tthat seems like it’d have it’s own map function on the NodeList prototype.

    With ES6 having tail call optimization as part of the spec and the rise in functional popularity, I’m really hoping to see ES7 support more higher order functions out of the box with composability instead of the backwards parameters. Until then, it seems to make more sense to use something like Elm or PureScript which has type annotation and tunctional features as ‘first class’ in its language that compiles to JavaScript as a target.

    February 1st, 2015 at 07:42

  3. Aldo

    That’s right javascript sometimes could be painful for some task like this but programmers have to deal with this and for this scenario map save the day.

    February 2nd, 2015 at 08:59

  4. Alex Weber

    Great article! As someone who’s becoming more familiar with functional programming, this was really helpful. The ES6 stuff was an educational double-whammy-bonus.

    My only question at this point is: what’s a good starting point for learning more in-depth functional programming? Suggested Haskell tutorials/books?

    Thanks!

    February 6th, 2015 at 12:44

  5. Brian m

    If I have to maintain code give me a nice for loop any day, in any language, it’s readable and debugable!
    I’m afraid javascript just goes from bad to worse, little added that does any real good, just complicates and introduces more chances of bugs or too clever for ‘everyone’ coders who will misuse it.

    Trying to add functional programing in as well is just making it even more confusing as a language, its OOP based credentials are to say the least very poor compared to Java, c# or c++!

    It’s only advantage is that it’s everwhere, but so is the common cold!

    February 7th, 2015 at 15:24

Comments are closed for this article.