JavaScript Joel

Posted on Dec 10, 2018 • Updated on Dec 18, 2020

Creating a linked list using only Function Combinators

#javascript #functional #showdev

Today I will demonstrate how to create a Linked List without any data structures like Object or Arrays; Instead, using Function Combinators.

I am assuming you are already familiar with what a linked list is. If you need a refresher on linked lists, check out thank u, next: an introduction to linked lists by @aspittel .

My goal is to expose you something you may not have seen before. To show what is possible with currying, partial application, closures and function combinators. And most important of all, have a little fun while doing it.

⚠️ This article has runkit embedded in it. You are meant to run, modify, tweak, and play with the examples on this page.

What The What is a Function Combinator?

Definition from Thinking Functionally: Combinators

The word "combinator" is used to describe functions whose result depends only on their parameters. That means there is no dependency on the outside world, and in particular, no other functions or global value can be accessed at all.

In practice, this means that a combinator function is limited to combining its parameters in various ways.

That's a lot to take in, so maybe some examples will help?

/* ☝️ These are combinators */
const I = a => a
const K = a => b => a
const V = a => b => c => c (a) (b)
const B = a => b => c => a (b (c))
//        -    -    -    ---------
//         \   |   /        |
//           arguments   ---
//                      /
//       only arguments are used

/* 👎 These are not */
const nope = a => a.map(double)
//                  --- ------
//                 /           \    
//                /    ⚠️ reaching outside of the func
//               /
//     ⚠️ can't use map either.
const add => a => b => a + b
//                       -
//                      /
// ⚠️ Uh oh, `+` is not part of 'arguments'

To recap the code above: A combinator can only use its arguments. That excludes external functions, methods, and operators!

Don't worry, it's okay to still be a little confused. (⊙_☉)

Abandoning Structure

A typical linked list will use some sort of data structure like these:

class Node {
  constructor(data, next) {
    this.data = data
    this.next = next
  }
}

/* or */

const node = (data, next) => ({ data, next })

/* or */

const node = (data, next) => [ data, next ]

But we won't be using any of these data structures. We will be using Function Combinators.

Before we jump right into the deep end of the combinator pool, let's start with a basic function for our node:

function node (data, next) {
//             ----  ----
//           /            \
//       our data       the next node
}

Now how do we access data and next without using node like an object? If you said callbacks, you were right!

I don't really care for this implementation using bind. So I'm going to curry the node function so I can use partial application to apply data and next. This will have the same effect as using bind but with a much better syntax.

Now if you were paying very close attention, you might have noticed that node is identical to the V combinator above!

So now node can be reduced to:

const node = V

and we can create nodes like this:

const evenOdd = node ('Even') ('Odd')
const leftRight = node ('Left') ('Right')
const yesNo = node ('Yes') ('No')

If we were to look at a break down of what the partial application is doing, it would look something like this:

// first copy the node function
const evenOdd = data => next => callback => callback (data) (next)

// apply 'Even' to data.
const evenOdd =         next => callback => callback ('Even') (next)

// apply 'Odd' to next.
const evenOdd =                 callback => callback ('Even') ('Odd')

// We end up with this:
const evenOdd = callback => callback ('Even') ('Odd')

evenOdd now takes a single parameter, the callback. The callback expects a function that looks like this:

const callback = a => b => { /* ??? */ }

We are now at a point where we can start to play. Hit play on this runkit and modify the callback to return 'Left'.

Now modify the code again to return 'Right'.

Awesome! Now let's call the 'Left' function data and the 'Right' function next.

const data = a => _ => a
const next = _ => b => b

Run it all again with our new functions.

Did you notice data is also the same as our K Combinator?

// 💥 BOOM!
const data = K

next almost matches the K Combinator, but it's a little different. next returns b, while data returns a. There is a little trick for that:

// 🧙‍♀️ MAGIC!
const next = K (I)

This neat trick was the inspiration for an entire article The easiest problem you cannot solve. I bet you can solve this problem in less than 2 seconds now!

Link that List

Let's translate what we have learned into a linked list.

Count that List

We can create a simple function to enumerate the list and return a count.

Map that List

Mapping is similar to an Array.

Filter

Filtering is also similar to an Array.

But are Function Combinators really useful?

Sure, you should never create a linked list this way. Actually, you should never be creating a linked list, to begin with. So this is all just academic anyway.

Surprisingly, there are some practical uses for function combinators!

You might not recognize the B Combinator

const B = a => b => c => a (b (c))

Unless it was written like this:

const compose = f => g => x => f (g (x))

That's right! compose is just the B Combinator! If you were curious, pipe is the Q Combinator.

Another useful utility function is always. Ramda has an always in their library. You can also recreate it with a simple function combinator.

const always = K

const awesome = always ('Awesome!')

awesome () //=> 'Awesome!'
awesome (123) //=> 'Awesome!'
awesome ('hello') //=> 'Awesome!'

tap is also a common function that I use often. It could be written like (below). It's great for managing side-effects.

const tap = func => val => {
  func (val) // execute my side effect
  return val // return the original value
}

We could also write tap like this:

const tap = S (K)

That's a lot of really useful stuff that can be created with function combinators!

Summary

We learned how to create a Linked List without using any Data Structures.
We learned what function combinators are and how they can be useful.
We learned how you can use currying, partial application and closures to store data.

Let me know what else you might have learned!

Let me know what you thought of the runkit examples. I am considering incorporating them more in my posts.

Do you want to learn more about function combinators? Let me know in the comments!

If you love Functional JavaScript, follow me here or on Twitter @joelnet!

Top comments (18)

Raj Adigopula • Dec 11 '18

That's the best explanation I have seen on Combinators. Thanks for writing this.

JavaScript Joel • Dec 11 '18

Thanks! It's a topic most people aren't interested in, so I hope I was able to make it interesting!

Nick Stevens • Aug 6 '20

Your implementation of the list does not load in Chrome. Error is: Unable to load embed. Syntax error found in Preamble. See console for error.

JavaScript Joel • Aug 10 '20

I believe this is a problem with the runkit embed on the site. I just confirmed that the code itself does run in Chrome.

Does the Runkit embed show on your screen are you able to see the code? I'm not seeing any problems on my computer.

Nick Stevens • Aug 10 '20

It does not work in Chrome for me. This is what I see: dropbox.com/s/oedl3d60pvzni18/Scre...

JavaScript Joel • Aug 13 '20

Ahh I see it now! It looks like the first two runkit embeds are working. The others following do not. I have opened up a support ticket on Github for this issue.

github.com/forem/forem/issues/9773

Scott Sauyet • Dec 14 '20

It looks as if that issue is now resolved. I don't know if the fix requires changes from you to get these working properly.

BTW, a very nice article!

JavaScript Joel • Dec 18 '20

Awesome. Looks like I had to resave the page.

rhymes • Dec 10 '18

Loved it, and thank you for using RunKit!

One thing: is there a reason why the combinators are named I, K, V, B instead of having more mnemonic names?

JavaScript Joel • Dec 10 '18 • Edited

Oh this is the fun part. Maybe I should have mentioned it in the article. A lot of the combinators do go by other names. But my favorite names for function combinators actually come from To Mock a Mockingbird. In To Mock a Mockingbird, they are named after birds!

The Combinator Birds (for I, K, V, B) are:

B - Bluebird
K - Kestrel
V - Vireo

and my absolute favorite is

I - Identity Bird

because it is also famously referred to as The Idiot!

The letters are probably because function combinators come from maths. And math people just like single letters. (I'm just guessing at this)