swizec.com

#### Senior Mindset Book

Get promoted, earn a bigger salary, work for top companies

# Are map, reduce, and filter turing complete?

Yes.

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?

No.

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
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)
)
.concat(x)
.concat(
quicksort(
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.

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

Semantically similar articles hand-picked by GPT-4

### Senior Mindset Book

Get promoted, earn a bigger salary, work for top companies

Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.

Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.

Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.

Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev

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

Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections

Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog

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 by Swizec with ❤️