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!