Swizec Teller - a geek with a hatswizec.com

    Are map, reduce, and filter turing complete?


    You can implement any algorithm with map, reduce, and filter when taken in the context of modern languages that implement these constructs. The predicate functions they rely on are turing complete, which makes them turing complete by extension.

    But that's smartass answer isn't it? Implementing your whole algorithm in a predicate function and wrapping it in a map call feels like cheating.

    Can you implement an algorithm just with map, reduce, and filter?


    Those three functions on their own can't do squat. Writing something like map(reduce(reduce(map(reduce(filter(4)))))) will not make anything happen.

    We first have to decide what we're trying to ask.

    I've been losing sleep over this whole thing ever since a technical editor nerdsniped me last week. "A smart man once told me you can write any program as a sequence of map and reduce calls. I like to add filter for a more comprehensive toolset.", I wrote in Data Visualization with d3.js.

    The editor's only comment was "This is wrong. For instance, you can't implement sorting like this."

    And well, yes, he's right. But he also isn't. What did Smart Guy (tm) try to tell me all those years ago when he introduced me to functional programming?

    Back to basics.

    To have a turing complete language you need:

    1. Write cell
    2. Read cell
    3. Move left
    4. Move right
    5. Branching (based on cell value)

    We assume our memory is practically infinite. Meaning it's not infinite per se, but we can add more when we run out.

    In his LISP-creating paper, McCarthy wrote that a recursive alternative to an iterative turing machine needs the following constructs:

    1. atom - is this symbol an atom (one of the basic characters)
    2. eq - are both these symbols atoms
    3. car - returns the first part of a two-element list
    4. cdr - returns the second part of a two-element list
    5. cons - constructs a list from two elements
    6. recursive definitions using these five constructs

    Where does this leave us in regards to our original question? Can we construct anything out of a sequence of map, reduce, and filter?

    It depends.

    In the context of a strict functional language, with the addition of recursion, yes we probably can.

    After all, implementing a naive quicksort in Haskell takes nothing more than recursion, car, cdr, cons and filter.

    quicksort [] = []
    quicksort (x:xs) =
    let smaller = quicksort (filter (<=x) xs)
    bigger = quicksort (filter (>x) xs)
    in smaller ++ [x] ++ bigger

    Basically, if quicksort gets an empty list, return an empty list. Otherwise make a new list and put elements smaller than x on left, bigger on right. ++ is essentially cons and that (x:xs) bit splits the list so the first item becomes x and the other items become xs.

    One of the tersest sorting implementations I've ever seen. And we didn't really go out of our map, reduce, filter framework did we? The ability to append to and split lists is usually assumed.

    But can we go a step further? Can we implement filter with map and reduce? Let's try.

    function filter(predicate, list) {
    return list
    .map(function (a) {
    return predicate(a) ? [a] : null;
    .reduce(function (prev, current) {
    return current ? prev.concat(current) : prev;
    }, []);

    Yes we can. Even in Javascript, which the original question was about. It's rather simple - mark unwanted entries with map, then use reduce to create a new list sans unwanted entries.

    We could go a step further and use only reduce.

    function filter2(predicate, list) {
    return list.reduce(function (prev, current) {
    return predicate(current) ? prev.concat(current) : prev;
    }, []);

    Turns out reduce and filter are the same function once you assume branching and comparison are a given. .concat is Javascript's version of cons by the way.

    We can implement that Haskell example in Javascript as well. Proving that even with Javascript recursion, map, and reduce are enough to do anything.

    function quicksort(list) {
    if (list.length == 0) {
    return [];
    var x = list[0],
    xs = list.slice(1);
    return quicksort(
    filter2(function (a) {
    return a <= x;
    }, xs)
    filter2(function (a) {
    return a > x;
    }, xs)

    Exact same code as before, just wordier because Javascript is fluffier than Haskell.

    But are we any closer to discovering our question?

    Not really no. We've just shown that given conditionals, a way to slice and append lists, recursion, map, and reduce we can do anything. Even in Javascript.

    Enhanced by Zemanta

    Did you enjoy this article?

    Published on September 17th, 2013 in Functional programming, Haskell, JavaScript, Lisp, Recursion, Turing completeness, Uncategorized

    Learned something new?
    Want to become an expert?

    Here's how it works 👇

    Leave your email and I'll send you thoughtfully written emails every week about React, JavaScript, and your career. Lessons learned over 20 years in the industry working with companies ranging from tiny startups to Fortune5 behemoths.

    Join Swizec's Newsletter

    And get thoughtful letters 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.

    "Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"

    ~ Ashish Kumar

    Join over 14,000 engineers just like you already improving their careers with my letters, workshops, courses, and talks. ✌️

    Have a burning question that you think I can answer? I don't have all of the answers, but I have some! Hit me up on twitter or book a 30min ama for in-depth help.

    Ready to Stop copy pasting D3 examples and create data visualizations of your own?  Learn how to build scalable dataviz components your whole team can understand with React for Data Visualization

    Curious about Serverless and the modern backend? Check out Serverless Handbook, modern backend for the frontend engineer.

    Ready to learn how it all fits together and build a modern webapp from scratch? Learn how to launch a webapp and make your first 💰 on the side with ServerlessReact.Dev

    Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

    By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️

    Created bySwizecwith ❤️