loading...

Creating a linked list using only Function Combinators

joelnet profile image JavaScript Joel Updated on ・7 min read

ABC written on chalk board

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!

///////////////////////////////////////////////////////////// // // // 📌 ATTENTION: You can modify and run these code blocks! // // // ///////////////////////////////////////////////////////////// function node (data, next, callback) { return callback(data, next) } // I can use bind to store my data and next values. const head = node.bind(null, 'data', null) // Use a callback to read the values from head. head((data, next) => { return { data, next } })

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.

const node = data => next => callback => callback (data) (next) // ---- ---- -------- ---- ---- // \ | / / / // parameters are curried ------------- // / // closures make data and next available // to callback when it is finally called. // I can use bind to store my data and next values. const head = node ('data') (null) // ------ ---- // / / // We can partially apply the arguments data and null. // Use a callback to read the values from head. head (data => next => { return { data, next } })

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'.

const V = a => b => c => c (a) (b) const node = V const leftRight = node ('Left') ('Right') // TODO: modify callback so the code returns 'Left' const callback = a => b => {} leftRight (callback) //=> '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.

const V = a => b => c => c (a) (b) const node = V const data = a => _ => a const next = _ => b => b const leftRight = node ('Left') ('Right') console.log (leftRight (data)) console.log (leftRight (next))

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.

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') // Just an Object to detect the end. const first = node ('1st') (Nil) // --- // / // Nil signifies the end const second = node ('2nd') (first) // ----- // / // pass the first node in as the next const third = node ('3rd') (second) // -----_ // / // pass the second node in as the next console.log (third (data)) //=> '3rd' console.log (third (next) (data)) //=> '2nd' console.log (third (next) (next) (data)) //=> '1st'

Count that List

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

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') const length = (list, value = 0) => list === Nil ? value : length (list (next), value + 1) const first = node ('1st') (Nil) const second = node ('2nd') (first) const third = node ('3rd') (second) console.log (length (first)) //=> 1 console.log (length (second)) //=> 2 console.log (length (third)) //=> 3

Map that List

Mapping is similar to an Array.

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') // Don't worry about this implementation. // It is just to demo the code below. const map = func => list => list === Nil ? list : node (func (list (data))) (map (func) (list (next))) const first = node ('1st') (Nil) const second = node ('2nd') (first) const third = node ('3rd') (second) const upper = x => x.toUpperCase() const THIRD = map (upper) (third) console.log (THIRD (data)) //=> '3RD' console.log (THIRD (next) (data)) //=> '2ND' console.log (THIRD (next) (next) (data)) //=> '1ST'

Filter

Filtering is also similar to an Array.

const I = a => a const K = a => b => a const V = a => b => c => c (a) (b) const node = V const data = K const next = K (I) const Nil = Symbol('Nil') // Don't worry about this implementation. // It is just to demo the code below. const filter = predicate => list => list === Nil ? list : predicate (list (data)) ? node (list (data)) (filter (predicate) (list (next))) : filter (predicate) (list (next)) const first = node (1) (Nil) const second = node (2) (first) const third = node (3) (second) const fourth = node (4) (third) const isEven = x => x % 2 === 0 const evens = filter (isEven) (fourth) console.log (evens (data)) //=> 4 console.log (evens (next) (data)) //=> 2

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!

Cheers!

Posted on Dec 10 '18 by:

joelnet profile

JavaScript Joel

@joelnet

Cofounded Host Collective (DiscountASP.net). Cofounded Player Axis (Social Gaming). Computer Scientist and Technology Evangelist with 20+ years of experience with JavaScript!

Discussion

markdown guide
 

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

 

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

 

Nice implementation and consumption of runkit. i like it

 

Thanks! I'm hoping to use runkit more in my posts. I wish I had some stats on how many actually are using it.

Cheers!

 

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?

 

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)

 

Thank you!

I'll call them Identity, Bluebird, Kestrel and Vireo :D

 
 
 

Thanks for pointing me there!

I really only knew about the CodePen embeds and those didn't work for what I wanted.

 

keep these posts coming... great write up

 

Thanks! I have a few more articles at about 90%. I just need to spend some time to get them over the finish line.

Cheers!