Let’s implement forEach! Without using arrays.
Sounds stupid? Maybe. Probably you won’t need to implement forEach in your daily job, but during the process, you will learn some fascinating stuff about programming languages. If you’re curious, let’s begin!
We have the following task to solve:
Define functions "range" and "foreach", obeying the restrictions below, such that the following program works properly.var numbers = range(1, 5);
forEach(numbers, n => console.log(n * n));
/* output:
1
4
9
16
25
*/Restrictions:1. You must not use arrays. The square bracket characters, [ and ], are forbidden, as well as Array constructor.2. You must not use objects. The curly braces, { and }, and the dot character (.) are forbidden. You may use curly braces for code blocks, but not for creating JavaScript objects.3. You must not use iterator statements:
do...while
for
for...in
for...of
for await...of
while3. Should go without saying, these functions must be generic and do what their name implies. They must not be hard-coded for the particular 1..5 example.
Note: This is a slightly changed version of the task created by Mihai Bazon
Simple. I mean— the description is simple, the implementation is NOT! I will guide you through the solution and step by step, we will discover some fascinating stuff.
Let’s start with the simplest implementation of the desired function without restrictions, just to be clear that we’re on the same page.
Nothing fancy here, so let’s figure out how to implement these functions with constraints mentioned before.
To solve this problem, we need some data structure to operate on. We want to iterate over it, so we need some kind of collection. Without using builtin arrays or objects and any loop or method to iterate over them it seems impossible, but we’ll figure it out! We’ll implement the so-called “recursive data structure” using only a function. This collection will have always ONLY TWO elements.
How is it supposed to be a list? The key is in the closure —our list is just a function that has access to the a and b items. Thanks to that, we are able to retrieve these items from the list.
If we want to get the values of our list, we need to pass some kind of selector to the created list. Take a look at the example:
Great, it works! But calling list as a function seems counter-intuitive... Let’s just make some wrapper function to query the first and the second item of the list:
Note: You can play with these examples here
Perfect! Our list is working! But… now you probably think — “This is stupid! The two-elements data structure is completely useless!”. And you’re right, but - the key is in the word “recursive”. We can easily turn it into an infinite-items collection. This picture will explain everything:
Probably you already get the idea — instead of setting the second element of the list as the desired value, we set another list, which keeps the desired value as the first element. The second item is the next list, which keeps the desired value as the first element, and list as the second, and so on.. With our list implementation, we could represent it with the following code:
Believe me or not, but we’re ready to implement our first function — “range”:
The idea here is dead simple — we recursively create a list with two elements as mentioned before. The second element of the first list is also a list, and the second element of this list is also a list… you get it, it’s just recursion! Because we want to indicate somehow where is the end of the list (we’ll need it especially during iteration over these items), we’ll put null at the end. null will be our special value — if we’ll encounter null as the list element, we can be sure that this is the end of the list. Here’s the visualization of the list after each iteration, to better understand how it works.
Whoa! We just implemented a collection of items using only a function!
Now it’s time to implementforEach . We’ll also make use of recursion here. We’ll just apply the callback function to the first item of the list and call recursively forEach on the second element of the list. To know where we should stop, we’ll check first if it’s not the end of the list (if the item is not null).
We did it! We have all functions we need, and with few syntactic simplifications, it might look like this:
Yes, I agree, this is not the most readable code I’ve ever seen. But that’s not the case. What’s interesting here is that we implemented such basic things like collections and looping over it with only functions, arithmetic operators and logic operators.
So.. can we make it even further? Can we get rid of some other language functionalities and still make the code do what it’s intended?
Let’s resign from multi-arguments functions. This is the simple one. Every multi-argument function can be written as multiple single-argument functions with partial application. Take a look at the example:
If we apply those changes to our task solution, we’ll have a code like this:
Ok, now we’re really low-level! Before solving this task, I thought it’s impossible to achieve something like this with such basic language functionalities. But there’s more — using only a function, we can implement even conditional logic! Take a look at the example:
I won’t explain the details here, but you can check it that it really works! However, conditional logic without a number doesn’t mean much. Well, guess what? We can implement our own numbers, still using only a function!
This is quite complicated, but you don’t have to understand it deeply. Of course, I didn’t figure out all of these on my own! This stuff is known for almost 100 years. It’s laid down upon the foundation which is called lambda calculus. The Wikipedia definition tells us, that lambda calculus is “ a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.” Personally, I like more some more informal definition of it: “Lambda calculus is the smallest programming language in the world”. Syntax of lambda calculus allows you only to define functions, to call functions and to declare variables. So basically, we can say that any language limited to those capabilities is equivalent to the lambda calculus. It’s really fascinating what we can achieve with such simple functionality. Lambda calculus doesn’t have native support for recurrence. But that’s also not a problem — we can implement it on our own:
Let’s recap- with only such a basic functionality of a language we implemented data structure, forEach, conditional logic, numbers, and even recursion! So what actually CAN’T be implemented only with a function? The truth is that there’s no such thing. Lambda calculus is Turing complete, which means that:
Every computer program can be written in a language that has only three capabilities: defining functions, calling functions and using variables.
Take a minute and think about that. Every computer program that you wrote or used could be written in such a simple language. Of course, in most cases, it won’t be practical, but still, it’s possible.
Keep that in mind when next time you will complain about missing features in JavaScript! :)
