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:
- Write cell
- Read cell
- Move left
- Move right
- 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:
atom- is this symbol an atom (one of the basic characters)eq- are both these symbols atomscar- returns the first part of a two-element listcdr- returns the second part of a two-element listcons- constructs a list from two elements- 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.
Continue reading about Are map, reduce, and filter turing complete?
Semantically similar articles hand-picked by GPT-4
- JavaScript's native map reduce and filter are wrong
- Week 15: A tutorial on the expressiveness and universality of fold
- Functional isn't always better
- The birth of LISP - a summary of John McCarthy's original paper
- Fun javascript feature
Learned something new?
Read more Software Engineering Lessons from Production
I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.
Subscribe below 👇
Software Engineering Lessons from Production
Join Swizec's Newsletter and get insightful emails 💌 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. 👌"
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 ❤️