In this article, I will present a JavaScript ES6 implementation of a lazily-evaluated linked list data structure. The recursively-defined linked list is an important collection type in many functional programming languages. In the Haskell language, which inspired this project, the list datatype fills the role that arrays occupy in JavaScript. Since this list type is defined using recursion, it is possible to generate and evaluate list elements on demand, rather than at the time of the list’s creation (that’s the “lazy” part), thereby making infinite lists not only feasible but relatively straightforward.
I rely on the new [Proxy](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Proxy) API from ES2015 (aka ES6) as a means of indirection for generating both finite and infinite ranged lists in JavaScript. Generators also make an appearance here, so this is a good opportunity to explore and actually use some of the latest extensions to the language while learning more about functional programming (a topic I discussed more explicitly in a prior article). The code presented here is adapted from my lazy-linked-lists npm module. The complete library is available as open source on GitHub, and, since we’re exploring laziness, I put the example code used specifically in this article into a separate GitHub Gist.
If you haven’t looked at Proxy yet, it’s going to turn your world upside down. Whether that’s a good thing or not will depend on your perspective. Along with its counterpart [Reflect](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Reflect), Proxy brings the full range of metaprogramming powers to bear on humankind’s most prolific programming language. As the term implies, metaprogramming entails the writing of code that is able to inspect and modify itself. In other words, it is programming “one level up” in the abstraction hierarchy, or the programming of programming itself.
A functional programmer might regard this sort of messing about with semantics as anathema and its mere possibility evidence of a failed language design. If functional programming’s greatest virtue is referential transparency, Proxy enables willful obfuscation. Although prior versions of JavaScript let you do metaprogramming to an extent, the ES2015 specification put this power front and center by making it a first class citizen. Whether or not this is a power that programming languages should have (Brendan Eich, for one, thinks that proxies are awesome), it ironically gives those of us coming from the functional world some extra ability to wedge our favorite language idioms into JavaScript more easily.
The Proxy API provides the means for intercepting the ordinary processes of a running application. This is accomplished by associating a target object with another object that acts on its behalf, i.e. as a proxy. The proxy object, in turn, filters incoming operations on the target object through methods, or “traps,” defined on a designated “handler” object. For example, you can trap attempts to get the values of an object’s properties:
class Secret {constructor(msg) { this.info = msg }}
let handler = {get: (target, prop) =>prop === "info" ? "Too many secrets" : target[prop]}
let makeSecret = msg => new Proxy(new Secret(msg), handler)
let s1 = new Secret("Confidential information")
let s2 = makeSecret("More confidential information")
s1.info // "Confidential information"
s2.info // "Too many secrets"
In this simple example, we have a tiny wrapper class called Secret that serves as a prototype for objects we might use to hide sensitive information. Rather than exposing the class itself to users of our API, we might offer instead a custom constructor function. Doing so allows us to customize the way that a Secret will behave in certain circumstances. Here, the function makeSecret doesn’t return the new Secret object itself but a proxy object that will act on its behalf. All “messages,” so to speak, directed to a given Secret will pass through its respective proxy first. And we can trap all, some, or none of those messages. The Secret proxy only traps attempts to read, or get, the value of the info property. In fact, all attempts to read properties of Secret are intercepted, because the handler object defines a get method. But the logic of that method only interferes with requests to get the info property. Instead of returning that value, the proxy returns a prescribed default value (one that is dear to the hearts of 1990s spy caper aficionados). You’ll note, of course, that this is hardly a full-proof mechanism for data hiding, but a more ambitious program, perhaps one that implements membranes, could certainly use Proxy for that purpose.
We can apply the same technique to create a functional interface for arbitrary-length linked lists. Since we’re in ES6 land, let’s start by defining a simple class for our list type:
class List {constructor (x, xs) {this.head = () => xthis.tail = () => xs}}
This will be a fairly straightforward functional data structure. The constructor function for List takes a value x as the first element, or head, of a new list object and another list xs as the tail, or the rest of the list. If you’re familiar with lower-level implementations of linked lists, you can think of the list object as a node comprising two cells: the head is the value (or label) of the node, and the tail is a pointer to the next node. The last value in any given list is always an empty list. The head and tail properties are defined to return not raw values but functions, in keeping with the functional paradigm and as some slight protection against tampering. Imagine them not as nullary functions but as equivalent to identity functions applied to their arguments (and if you were to parameterize that identity function instead, you’d have a monad, but I promised myself I wouldn’t discuss monads in this article).
In fact, the entire class declaration is just a special kind of function. Debates about the usefulness of OOP concepts notwithstanding, ES6 classes do possess one salient attribute that we can take advantage of here: you cannot directly invoke them as functions. Objects defined as classes can only be constructed with the new keyword; the class constructor function then ensures that new “does the right thing.” And debates about the propriety of new itself notwithstanding, this attribute allows us to hide the class declaration (for example, by not exporting it) and supply our own custom constructor function instead. In a way, we’re using the most controversial syntax in JavaScript against itself. Here’s the code we need for the interface that we do want to export:
const emptyList = new List()
const isEmpty = xs => xs === emptyList
const cons = (x, xs) => new List(x, xs)
const list = (...as) =>as.length === 0 ? emptyList : new List(as.shift(), list(...as))
const head = xs => {if (isEmpty(xs)) { throw Error('EmptyListError') }return xs.head()}
const tail = xs => {if (isEmpty(xs)) { throw Error('EmptyListError') }return xs.tail()}
In Haskell, a list is a sum type that requires two constructors: one that creates an empty list, and one that recursively creates a new list from a value (the head) and “more list” (the tail). Since JavaScript does not have sum types, the above implementation is a bit jury-rigged. But it works. The emptyList object is simply a symbolic placeholder. It doesn’t pass any arguments to List, so both the head and tail of an empty list are undefined. Since we don’t want the List constructor to be invoked directly anyway, this is fine: there is only one empty list for all occasions in our program, it is constructed once and only once, and it is emptyList. We also provide a function for checking whether a list is empty, a frequent necessity where recursion and base cases are concerned.
The other constructor is cons. cons, like the List class it wraps, _cons_tructs a new list from a value x and another list xs. x is prepended onto xs. If xs is the empty list, then cons simply creates a new single element list. Obviously, there is opportunity for abuse here, and a more comprehensive implementation of cons would validate and possibly even type check x. You could also create a curried version and make it truly functional, but for explanatory purposes I am trying to omit as much noise as possible.
The list function is here for convenience, since we can’t create our own syntactic sugar for declaring lists of multiple elements. list takes zero or more arguments and recursively consumes them until the arguments array (cleanly provided by the rest operator, another ES6 feature) is empty, at which point it reaches emptyList as a base case. The function call list(1,2,3) is equivalent to cons(1, cons(2, cons(3, emptyList))). head and tail are accessor functions for those respective properties. As in the Haskell Prelude, they are partial functions, which is not ideal, but again, they will suffice for demonstration purposes.
Since JavaScript is just going to treat our lists as objects, we’d like a way to print list values nicely. So let’s add a custom valueOf method:
class List {constructor(x, xs) {this.head = nullthis.tail = nullthis.head = () => xthis.tail = () => xs}valueOf() {let value = xs =>isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}`return isEmpty(this) ? `[]` : `[${value(this)}]`}}
Now, when we display list values, we get something reasonably legible:
let lst1 = list(1,2,3,4,5)
lst1.valueOf() // [1:2:3:4:5:[]]
let lst2 = cons(0, lst1)
lst2.valueOf() _// [0:1:2:3:4:5:[]]_let lst3 = cons(0, cons(1, cons(2, cons(3, cons(4, cons(5, emptyList))))))
lst3.valueOf() // [0:1:2:3:4:5:[]]
head(lst1) // 1
tail(lst2).valueOf() // [1:2:3:4:5:[]]
isEmpty(tail(tail(tail(tail(tail(lst1)))))) // true
I use colons instead of commas to avoid confusion with arrays, and to make its structure more obvious and more Haskell-y, but you can obviously print list values however you want (and look up: ES6 template literals!). The use of valueOf in these examples is only necessary if your REPL doesn’t pretty print object properties by default (node does when it can, but browser consoles do not).
Another nice-to-have convenience that ES6 now lets us implement is custom iteration using generators and the so-called “well-known symbol,” Symbol.iterator:
class List {constructor(x, xs) {this.head = nullthis.tail = nullthis.head = () => xthis.tail = () => xs}[Symbol.iterator]() {const listIterator = function* (xs) {do {yield head(xs)xs = tail(xs)} while (xs !== emptyList)}const gen = listIterator(this)return {next() { return gen.next() }}}valueOf() {let value = xs =>isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}`return isEmpty(this) ? `[]` : `[${value(this)}]`}}
Now we can use lists in the same way we might use arrays — if for some reason we’re in the mood to use for loops or have some other need for iterable objects:
let lst = list(1,2,3,4,5)
for (let value of lst) { console.log(value); }// 1// 2// 3// 4// 5
The next step is to recreate the functionality provided in Haskell by ranged list expressions. For example, the Haskell expression [1..10] is a shortcut for constructing the list [1,2,3,4,5,6,7,8,9,10]. Likewise, Haskell can also infer that when you type [1,3..10] what you mean is [1,3,5,7,9]. Let’s see how far we can get with this in JavaScript. First, we’ll define a function that recursively constructs a list of consecutive whole numbers:
const listRange = (start, end) => {if (start === end) { return list(start) }if (start > end) { return listRangeBy(start, end, x => x - 1) }return listRangeBy(start, end, x => x + 1)}
We give this function two values for start and end, and it gives us back a list of the numbers between them. Note that the result list, unlike in Haskell, is inclusive of the starting value but exclusive of the ending value (as in Python); that this function only operates on numbers (a version for characters wouldn’t be too hard to design, however — see my library); and that if start is greater than end, the result list counts down instead of counting up:
listRange(1,10).valueOf() // [1:2:3:4:5:6:7:8:9:[]]
listRange(10,1).valueOf() // [10:9:8:7:6:5:4:3:2:[]]
The sharp-eyed will observe that this function doesn’t actually do much on its own. Rather, it passes off responsibility for the list construction itself to another, more general function: listRangeBy. That function also creates a ranged list but parameterizes the “step” function used to increment the values, making it a more general case of listRange and also making it sensible to simply define one in terms of the other. Finally, with listRangeBy, we meet the proxies at the heart of this matter:
const listRangeBy = (start, end, step) => {if (start === end) { return list(start) }let x = startconst xs = list(x)const listGenerator = function*() {x = step(x)while (start < end ? x < end : x > end) {yield list(x)x = step(x)}}const gen = listGenerator()const handler = {get: function(target, prop) {if (prop === `tail` && isEmpty(tail(target))) {const next = gen.next()if (next.done === false) {target[prop] = () => new Proxy(next.value, handler)}}return target[prop]}}const proxy = new Proxy(xs, handler)return proxy}
This function is a little strange, and too imperative for a functional programmer’s taste, but it gets the job done. First, it takes the start value and creates a singleton list with it. Next, it declares an internal generator function, tailored to the parameterized step function, that will yield subsequent singleton lists until it hits the end. These new lists, when generated, are the “lazy” tails of the “list” (actually a proxy object) returned by the listRangeBy function. The head is the evaluated value of that particular node, but the rest of the list is considered “empty” until further calls for more list trigger subsequent evaluations. Each element of the tail is generated one at a time, on demand, and that is why we can say that these ranged lists are lazily evaluated.
The handler object comes next. This particular handler, as in the Secret example above, traps all attempts to get the values of properties defined on the target List. In this case, we’re only interested in the tail property. When the value of a “target” list’s tail is requested, instead of generating the entire rest of the list, the handler’s get method calls the generator function, which yields only the next head value—packaged up in another singleton list—and returns a new Proxy object that “targets” that newly generated singleton list. The tail of this new list is still emptyList, even though it really isn’t as long as the generator is able to produce new values. But we pretend that it is as part of the logic of our proxy handler. In our lazy list world, any given tail evaluated by the handler is going to be either a singleton list or a list that has already been partially or completely evaluated. In the case of a singleton list, the handler initiates the creation of a series of proxies that continue trapping calls to evaluate these nested tails until the list is completely evaluated or no more values are requested.
This works, because list tails are evaluated recursively. Any function that recurses through a list will eventually hit emptyList in its base case. For those lists that we have defined as lazy, the proxy handler checks whether the generator can yield another value if the tail of the list is empty. If it can, it returns a new proxy targeting a new list with that value as its head. If it can’t, it returns emptyList as normal, which means the original list has been fully evaluated and subsequent calls for its tail will fall through the proxy undisturbed. In the case of a list that has already been partially evaluated, the handler code is skipped over until more values need to be generated—until, that is, the target list’s tail equals emptyList. A completely evaluated list behaves identically to any other List object.
Finally, to get this whole ball rolling, listRangeBy creates a proxy object proxy that targets the original singleton list xs (the wrapper for our start value) and returns proxy, the filter at the head of the list line, in lieu of a “normal” List object. We have now abstracted over lazy evaluation.
It works:
let eagerList = list(1,2,3,4,5,6,7,8,9,10)
eagerList.valueOf() // [1:2:3:4:5:6:7:8:9:10:[]]
let lazyList = listRangeBy(1,100000, x => x + 3)
lazyList // List { head: [Function], tail: [Function] }
lazyList.valueOf() // RangeError: Maximum call stack size exceeded
Unfortunately, until proper tail calls finally make their way into JavaScript engines, extremely long lists are likely to blow up your stack frame when you try to perform certain operations. And speaking of extremely long lists… by using JavaScript’s handy Infinity global, we can now implement analogous functions for conveniently constructing lazy lists of infinite length:
const listInf = start => listInfBy(start, x => x + 1)
const listInfBy = (start, step) => listRangeBy(start, Infinity, step)
Since infinite lists are the coup de grâce of this little project, let’s define a few more basic list functions to better illustrate how they work:
const length = xs => {const lenAcc = (xs, n) =>isEmpty(xs) ? n : lenAcc(tail(xs), n + 1)return lenAcc(xs, 0)}
const index = (as, n) => {if (n < 0 || isEmpty(as)) { throw Error('OutOfRangeError') }const x = head(as)const xs = tail(as)if (n === 0) { return x }return index(xs, n - 1)}
const listAppend = (xs, ys) => {if (isEmpty(xs)) { return ys }if (isEmpty(ys)) { return xs }return cons(head(xs), listAppend(tail(xs), ys))}
const take = (n, as) => {if (n <= 0) { return emptyList }if (isEmpty(as)) { return emptyList }const x = head(as)const xs = tail(as)return cons(x, take(n - 1, xs))}
const drop = (n, as) => {if (n <= 0) { return as }if (isEmpty(as)) { return emptyList }const xs = tail(as)return drop(n - 1, xs)}
const map = (f, as) => {if (isEmpty(as)) { return emptyList }const x = f(head(as))const xs = tail(as)return cons(x, map(f, xs))}
length and index are similar to their array-based counterparts. listAppend is similar to concat in JavaScript (whereas concat in Haskell takes a multi-dimensional list and flattens it). take grabs the first n elements from a list and returns them in a new list. drop deletes the first n elements and returns what’s left. map, not surprisingly, applies the function f to each element in the list as. These functions work on both eagerly and lazily evaluated lists, including infinite lists, though some functions obviously won’t work on the latter (and might cause some weird behavior in your REPL):
let eagerList = list(1,2,3,4,5,6,7)
let lazyList = listRangeBy(1,1000, x => x * 2)
let infiniteList = listInf(1)
head(eagerList) // 1
head(lazyList) // 1
head(infiniteList) // 1
tail(eagerList).valueOf() // [2:3:4:5:6:7:8:9:10:[]]
tail(lazyList).valueOf() // [2:4:8:16:32:64:128:256:512:[]]
tail(infiniteList).valueOf()_// RangeError: Maximum call stack size exceeded_length(eagerList) // 7
length(lazyList) // 10
length(infiniteList) // RangeError: Maximum call stack size exceeded
index(eagerList, 3) // 4
index(lazyList, 9) // 512
index(infiniteList, 10000) // 10001
listAppend(eagerList, lazyList).valueOf()// [1:2:3:4:5:6:7:1:2:4:8:16:32:64:128:256:512:[]]
listAppend(lazyList, infiniteList).valueOf()// List { head: [Function], tail: [Function] }
index(listAppend(lazyList, infiniteList), 100) // 91
listAppend(infiniteList, eagerList).valueOf()_// RangeError: Maximum call stack size exceeded_take(5, eagerList).valueOf() // [1:2:3:4:5:[]]
take(5, lazyList).valueOf() // [1:2:4:8:16:[]]
take(5, infiniteList).valueOf() // [1:2:3:4:5:[]]
drop(5, eagerList).valueOf() // [6:7:[]]
drop(5, lazyList).valueOf() // [32:64:128:256:512:[]]
drop(5, infiniteList).valueOf()// RangeError: Maximum call stack size exceeded
let f = x => x * 10
map(f, eagerList).valueOf() // [10:20:30:40:50:60:70:[]]
map(f, lazyList).valueOf()// [10:20:40:80:160:320:640:1280:2560:5120:[]]
map(f, infiniteList).valueOf()// RangeError: Maximum call stack size exceeded
map(f, take(10, infiniteList)).valueOf()// [10:20:30:40:50:60:70:80:90💯[]]
In the last example, we can’t perform lazy mapping (though in principle it’s possible), but we can compose map with another function that does produce a finite list and map over that.
While we’re translating Haskell functions into JavaScript, why not import the basic functions for generating other kinds of infinite lists, too? These can be handy when you need to work with streams of values:
const iterate = (f, x) => listInfBy(x, x => f(x))
const repeat = a => cons(a, listInfBy(a, a => a))
const replicate = (n, x) => take(n, repeat(x))
iterate repeatedly applies the given function f to the value x. repeat returns an infinite list of the same value. replicate simply returns a list of n elements that are all of value x. There’s one more function, cycle, that deserves special mentioning, because it requires a special implementation. cycle takes a list and infinitely repeats it. Our regular listRangeBy function cannot handle this case, however, so we must provide a slightly altered version of it for cycle:
const cycle = as => {if (isEmpty(as)) { throw Error('EmptyListError') }let x = head(as)let xs = tail(as)const c = list(x)const listGenerator = function* () {do {x = isEmpty(xs) ? head(as) : head(xs)xs = isEmpty(xs) ? tail(as) : tail(xs)yield list(x)} while (true)}const gen = listGenerator()const handler = {get: function (target, prop) {if (prop === `tail` && isEmpty(tail(target))) {const next = gen.next()target[prop] = () => new Proxy(next.value, handler)}return target[prop]}}const proxy = new Proxy(c, handler)return proxy}
JavaScript, like life, is a little bit messy sometimes. Let’s see what these functions do:
let lst1 = iterate(x => x + 2, 0)
take(10, lst1).valueOf() _// [0:2:4:6:8:10:12:14:16:18:[]]_let lst2 = repeat(7)
take(20, lst2).valueOf()// [7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:[]]
let lst3 = replicate(5, 23)
lst3.valueOf() // [23:23:23:23:23:[]]
let lst4 = cycle(list(5,4,3,2,1))
index(ls4, 5) // 5
index(lst4, 10) // 5
index(lst4, 100) // 5
index(lst4, 104) // 1
If we want, we can use infinite lists to create even more specialized sorts of streams or as part of the implementations of well-known algorithms:
const booleans = cycle(list(false, true))
const fib = n => n < 2 ? n : fib(n - 1) + fib(n - 2)const fibs = n => map(fib, take(n, listInf(1)))
const fact = n => n === 1 ? n : fact(n - 1) * nconst facts = n => map(fact, take(n, listInf(1)))
const sqrt = (a0, eps, n) => {const within = (eps, rest) => {let a = index(rest, 0)let b = index(rest, 1)return Math.abs(a - b) <= eps ? b : within(eps, drop(1, rest))}const next = (n, x) => (x + n / x) / 2return within(eps, iterate(next.bind(null, n), a0))}
index(booleans, 20) // false
index(booleans, 10001) // true
index(fibs(10), 9) // 55
facts(5).valueOf() // [1:2:6:24:120:[]]
sqrt(1,0,2) // 1.414213562373095
sqrt(1,0,144) // 144
An infinite list of alternating booleans might come in handy as a filter for even or odd numbers or if you’re creating something else that entails an alternating pattern (such as shading for table rows). With a stream of values, you can just grab however many you need and not have to code the logic for counting them up. The fibonacci and factorial examples, aside from being the most famous recursion examples ever, show how you can use infinite lists to algorithmically produce custom series of values. The sqrt function shown here uses an infinite list to compute the square root of a number n, with a tolerance eps, and starting with an initial estimate a0. This example of the Newton-Raphson method for calculating square roots is adapted from Why Functional Programming Matters by John Hughes — essential reading, indeed.
There you have it: lazy, functional, infinite lists in JavaScript with various operations you might perform on them! Once again, please see my library on GitHub for even more List functions, including functions to take and drop elements conditionally, filter lists, sort lists, zip lists, and more. The full class definition also provides list equality checking, all the standard comparison methods, and implementations for common algebraic interfaces, such as monoid, foldable, functor, and monad (oops). In addition, the complete library better supports strings, which I ignored for the sake of simplicity in this article. Functions for converting between lists and JavaScript arrays and strings are also supplied. For type-checked and curried versions of all of these functions, see my more comprehensive library of Haskell functions translated into JavaScript: maryamyriameliamurphies.js.
The linked list is an ideal data structure for functional programming: it’s easy to define recursively, and it fits snugly into compositions of functions. A functional linked list is so straightforward to implement because it’s a mathematical object, not an abstraction over finite blocks of computer memory that must be procedurally manipulated or, as in JavaScript, a specialized record type. With a more purely functional language, we can describe this collection type as a simple formula and not have to worry about memory, pointers, or anything else the actual machine cares about but we, as programmers, do not. Furthermore, algebraic data types, scary as they may sound, can make our data so much easier to organize and our code so much easier to read and, as the saying goes, reason about.
The whole definition of a list in Haskell, for example, is data [] a = [] | a : [a]. That one snippet of code accomplishes essentially the same thing as my entire class — and it’s all thanks to the power and expressivity of sum types. Most languages have product types. Few have sum types. The JavaScript Object is a product type, because every object contains a field for every possible value. The List we defined above is not a true sum type, but it does reproduce the functionality of a type that contains either one value or set or values or another value or set of values. Where product types represent and, sum types represent or. You wouldn’t go without or in your boolean logic, so why go without it in your type system? Without the ability to define types as disjoint, you are trapped in a world of artificial hierarchies and over-specified abstractions. That’s what you get when everything is a product type, when you have no choice but to define custom types (i.e. classes) as aggregates of values rather than alternatives among values. If you’ve ever had trouble stitching a pile of objects together in an effort to model inconsistent data, then you know the pain whereof I speak. And now you have a remedy. With sum types, you can more easily adapt your model to the messy world of data rather than trying to force data to conform to your model. In functional programming, we prefer Proteus to Procrustes. And we prefer flexible lists to rigid arrays. JavaScript’s built-in Array type has made great strides toward becoming more functional, but it is still essentially a hack. Fortunately, JavaScript has higher-order functions, so we can do our own hacking, too.
Postscript — Binary Trees
The methods I demonstrate in this article to implement a linked list can, in principle, also be used for other linked structures. If a given data type has an obvious recursive definition, it won’t be too much trouble to apply to it the same logic. Let’s briefly look at binary trees. We can define a binary tree in Haskell as follows: data Tree a = Leaf | Node (Tree a) a (Tree a). Like our List type above, Tree is a sum type, which means any given Tree will be either a Leaf or a Node. Leaf is like emptyList: it’s the natural base case or terminal point of the structure. Whereas a linked list terminates at only one point, however, a tree can have multiple branches, each one of which could have further branches, all of them ending in terminal points. Here’s a basic implementation of this same structure in JavaScript, complete with functions for inserting into a tree and for displaying tree values in the usual orderings (converted into arrays for the sake of ease):
class Tree {constructor(left, label, right) {this.left = () => leftthis.label = () => labelthis.right = () => right}}
const leaf = new Tree()
const node = (left, label, right) => new Tree(left, label, right)
const insert = (x, t) => {if (t === leaf) { return node(leaf, x, leaf) }if (x === t.label()) { return t }if (x < t.label()) {return node(insert(x, t.left()), t.label(), t.right())}return node(t.left(), t.label(), insert(x, t.right()))}
const preorder = t => t === leaf ? [] :[t.label()].concat(preorder(t.left()).concat(preorder(t.right())))
const inorder = t => t === leaf ? [] :inorder(t.left()).concat([t.label()].concat(inorder(t.right())))
const postorder = t => t === leaf ? [] :postorder(t.left()).concat(postorder(t.right()).concat([t.label()]))
And now let’s construct a test tree and try out our little library of functions:
let tree = leaf
let squares = listInfBy(1, x => x * 2)
let cubes = listInfBy(1, x => x * 3)
for (let value of take(10, squares)) { tree = insert(value, tree) }
preorder(tree) // [1,2,4,8,16,32,64,128,256,512]
inorder(tree) // [1,2,4,8,16,32,64,128,256,512]
postorder(tree) _// [512,256,128,64,32,16,8,4,2,1]_for (let value of take(5, cubes)) { tree = insert(value, tree) }
preorder(tree) // [1,2,4,3,8,16,9,32,27,64,128,81,256,512]
inorder(tree) // [1,2,3,4,8,9,16,27,32,64,81,128,256,512]
postorder(tree) // [3,9,27,81,512,256,128,64,32,16,8,4,2,1]
After learning about functional linked lists, binary trees should be a piece of cake. Just for fun, I used an infinite list of squares to generate the example tree above, then mixed it up with a stream of cubes. Why? To illustrate function composition one more time. The power of functional programming comes from the accumulation of all these little concepts. Keep learning them, and keep growing your toolkit. The implementation of lazy binary trees I leave as an exercise for the reader.
Hacker Noon is how hackers start their afternoons. We’re a part of the @AMIfamily. We are now accepting submissions and happy to discuss advertising &sponsorship opportunities.
To learn more, read our about page, like/message us on Facebook, or simply, tweet/DM @HackerNoon.
If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!