How I Used Proxy to Implement Lazy Infinite Lists in JavaScript

In this article, I will present a JavaScript ES6 implementation of a lazily-evaluated data structure. The recursively-defined linked list is an important collection type in many functional languages. In the , which inspired this project, the fills the role that arrays occupy in . Since this list type is defined using , 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. linked list programming Haskell language list datatype JavaScript recursion I rely on the new API from (aka ES6) as a means of indirection for generating both finite and infinite ranged lists in JavaScript. 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 ). The code presented here is adapted from my npm module. The complete library is available as open source on , and, since we’re exploring laziness, I put the example code used specifically in this article into a separate . [Proxy](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Proxy) ES2015 Generators a prior article lazy-linked-lists GitHub GitHub Gist If you haven’t looked at 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 , brings the full range of powers to bear on humankind’s most prolific programming language. As the term implies, 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. Proxy [Reflect](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Reflect) Proxy metaprogramming metaprogramming 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, 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 have ( , for one, thinks that ), it ironically gives those of us coming from the functional world some extra ability to wedge our favorite language idioms into JavaScript more easily. Proxy should Brendan Eich proxies are awesome The 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 , i.e. as a . 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 attempts to the values of an object’s properties: Proxy acts on its behalf proxy trap get Secret { (msg) { .info = msg }} class constructor this handler = {get: (target, prop) =>prop === "info" ? "Too many secrets" : target[prop]} let makeSecret = msg => Proxy( Secret(msg), handler) let new new s1 = Secret("Confidential information") let new s2 = makeSecret("More confidential information") let s1.info // "Confidential information" s2.info // "Too many secrets" In this simple example, we have a tiny wrapper class called 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 will behave in certain circumstances. Here, the function doesn’t return the new object itself but a proxy object that will act on its behalf. All “messages,” so to speak, directed to a given will pass through its respective proxy first. And we can trap all, some, or none of those messages. The proxy only traps attempts to read, or , the value of the property. In fact, all attempts to read properties of are intercepted, because the handler object defines a method. But the logic of that method only interferes with requests to get the property. Instead of returning that value, the proxy returns a prescribed default value (one that is dear to the hearts of 1990s 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 , could certainly use for that purpose. Secret Secret makeSecret Secret Secret Secret get info Secret get info spy caper membranes Proxy 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: List { (x, xs) { .head = () => x .tail = () => xs}} class constructor this this This will be a fairly straightforward functional data structure. The constructor function for takes a value as the first element, or head, of a new list object and another list as the tail, or . 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 and 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 , but I promised myself I wouldn’t discuss monads in this article). List x xs the rest of the list head tail monad In fact, the entire 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 keyword; the class function then ensures that “does the right thing.” And debates about the propriety of 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 want to export: class declaration new constructor new new do emptyList = List() const new isEmpty = xs => xs === emptyList const cons = (x, xs) => List(x, xs) const new list = (...as) =>as.length === 0 ? emptyList : List(as.shift(), list(...as)) const new head = xs => { (isEmpty(xs)) { Error('EmptyListError') } xs.head()} const if throw return tail = xs => { (isEmpty(xs)) { Error('EmptyListError') } xs.tail()} const if throw return In Haskell, a list is a 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 object is simply a symbolic placeholder. It doesn’t pass any arguments to , so both the head and tail of an empty list are . Since we don’t want the 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 . We also provide a function for checking whether a list is empty, a frequent necessity where recursion and base cases are concerned. sum type emptyList List undefined List emptyList The other constructor is . , like the class it wraps, _cons_tructs a new list from a value and another list . is prepended onto . If is the empty list, then simply creates a new single element list. Obviously, there is opportunity for abuse here, and a more comprehensive implementation of would validate and possibly even type check . You could also create a and make it truly functional, but for explanatory purposes I am trying to omit as much noise as possible. cons cons List x xs x xs xs cons cons x curried version The function is here for convenience, since we can’t create our own syntactic sugar for declaring lists of multiple elements. 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 as a base case. The function call is equivalent to . and are accessor functions for those respective properties. As in the , they are , which is not ideal, but again, they will suffice for demonstration purposes. list list emptyList list(1,2,3) cons(1, cons(2, cons(3, emptyList))) head tail Haskell Prelude partial functions 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 method: valueOf List { (x, xs) { .head = null .tail = null .head = () => x .tail = () => xs}valueOf() { value = xs =>isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}` isEmpty( ) ? `[]` : `[${value( )}]`}} class constructor this this this this let return this this Now, when we display list values, we get something reasonably legible: lst1 = list(1,2,3,4,5) let lst1.valueOf() // [1:2:3:4:5:[]] lst2 = cons(0, lst1) let lst2.valueOf() _// [0:1:2:3:4:5:[]]_ lst3 = cons(0, cons(1, cons(2, cons(3, cons(4, cons(5, emptyList)))))) let 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: !). The use of in these examples is only necessary if your REPL doesn’t pretty print object properties by default ( does when it can, but browser consoles do not). ES6 template literals valueOf node 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 List { (x, xs) { .head = null .tail = null .head = () => x .tail = () => xs}[Symbol.iterator]() { listIterator = (xs) { { head(xs)xs = tail(xs)} (xs !== emptyList)} gen = listIterator( ) {next() { gen.next() }}}valueOf() { value = xs =>isEmpty(xs) ? `[]` : `${head(xs)}:${value(tail(xs))}` isEmpty( ) ? `[]` : `[${value( )}]`}} class constructor this this this this const function* do yield while const this return return let return this 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 loops or have some other need for iterable objects: for lst = list(1,2,3,4,5) let ( value lst) { console.log(value); } for let of // 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 is a shortcut for constructing the list . Likewise, Haskell can also infer that when you type what you mean is . 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: [1..10] [1,2,3,4,5,6,7,8,9,10] [1,3..10] [1,3,5,7,9] listRange = (start, end) => { (start === end) { list(start) } (start > end) { listRangeBy(start, end, x => x - 1) } listRangeBy(start, end, x => x + 1)} const if return if return return We give this function two values for and , 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 ); and that if is greater than , the result list instead of counting up: start end my library start end counts down 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: . That function also creates a ranged list but parameterizes the “step” function used to increment the values, making it a more general case of and also making it sensible to simply define one in terms of the other. Finally, with , we meet the proxies at the heart of this matter: listRangeBy listRange listRangeBy listRangeBy = (start, end, step) => { (start === end) { list(start) } x = start xs = list(x) listGenerator = () {x = step(x) (start end) { list(x)x = step(x)}} gen = listGenerator() handler = {get: (target, prop) { (prop === `tail` && isEmpty(tail(target))) { next = gen.next() (next.done === false) {target[prop] = () => Proxy(next.value, handler)}} target[prop]}} proxy = Proxy(xs, handler) proxy} const if return let const const function* while yield const const function if const if new return const new return 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 value and creates a singleton list with it. Next, it declares an internal generator function, tailored to the parameterized function, that will subsequent singleton lists until it hits the . These new lists, when generated, are the “lazy” tails of the “list” (actually a proxy object) returned by the 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. start step yield end listRangeBy The object comes next. This particular handler, as in the example above, traps all attempts to the values of properties defined on the target . In this case, we’re only interested in the property. When the value of a “target” list’s is requested, instead of generating the entire rest of the list, the handler’s method calls the generator function, which yields only the next value—packaged up in another singleton list—and returns a new object that “targets” that newly generated singleton list. The of this new list is still , 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. handler Secret get List tail tail get head Proxy tail emptyList This works, because list tails are evaluated recursively. Any function that recurses through a list will eventually hit 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 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 . A completely evaluated list behaves identically to any other object. emptyList emptyList emptyList List Finally, to get this whole ball rolling, creates a proxy object that targets the original singleton list (the wrapper for our value) and returns , the filter at the head of the list line, in lieu of a “normal” object. We have now abstracted over lazy evaluation. listRangeBy proxy xs start proxy List It works: eagerList = list(1,2,3,4,5,6,7,8,9,10) let eagerList.valueOf() // [1:2:3:4:5:6:7:8:9:10:[]] lazyList = listRangeBy(1,100000, x => x + 3) let lazyList // List { head: [Function], tail: [Function] } lazyList.valueOf() // RangeError: Maximum call stack size exceeded Unfortunately, until finally make their way into , 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 global, we can now implement analogous functions for conveniently constructing lazy lists of length: proper tail calls JavaScript engines Infinity infinite listInf = start => listInfBy(start, x => x + 1) const listInfBy = (start, step) => listRangeBy(start, Infinity, step) const 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: length = xs => { lenAcc = (xs, n) =>isEmpty(xs) ? n : lenAcc(tail(xs), n + 1) lenAcc(xs, 0)} const const return index = (as, n) => { (n { (isEmpty(xs)) { ys } (isEmpty(ys)) { xs } cons(head(xs), listAppend(tail(xs), ys))} const if return if return return take = (n, as) => { (n { (n { (isEmpty(as)) { emptyList } x = f(head(as)) xs = tail(as) cons(x, map(f, xs))} const if return const const return and are similar to their array-based counterparts. is similar to in JavaScript (whereas in Haskell takes a multi-dimensional list and flattens it). grabs the first elements from a list and returns them in a new list. deletes the first elements and returns what’s left. , not surprisingly, applies the function to each element in the list . 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): length index listAppend concat concat take n drop n map f as eagerList = list(1,2,3,4,5,6,7) let lazyList = listRangeBy(1,1000, x => x * 2) let infiniteList = listInf(1) let 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 f = x => x * 10 let 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 with another function that produce a finite list and map over that. can compose map does While we’re translating Haskell functions into JavaScript, why not import the for generating other kinds of infinite lists, too? These can be handy when you need to work with streams of values: basic functions 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)) const repeatedly applies the given function to the value . returns an infinite list of the same value. simply returns a list of elements that are all of value . There’s one more function, , that deserves special mentioning, because it requires a special implementation. takes a list and infinitely repeats it. Our regular function cannot handle this case, however, so we must provide a slightly altered version of it for : iterate f x repeat replicate n x cycle cycle listRangeBy cycle cycle = as => { (isEmpty(as)) { Error('EmptyListError') } x = head(as) xs = tail(as) c = list(x) listGenerator = () { {x = isEmpty(xs) ? head(as) : head(xs)xs = isEmpty(xs) ? tail(as) : tail(xs) list(x)} (true)} gen = listGenerator() handler = {get: (target, prop) { (prop === `tail` && isEmpty(tail(target))) { next = gen.next()target[prop] = () => Proxy(next.value, handler)} target[prop]}} proxy = Proxy(c, handler) proxy} const if throw let let const const function* do yield while const const function if const new return const new return JavaScript, like life, is a little bit messy sometimes. Let’s see what these functions do: lst1 = iterate(x => x + 2, 0) let take(10, lst1).valueOf() _// [0:2:4:6:8:10:12:14:16:18:[]]_ lst2 = repeat(7) let take(20, lst2).valueOf() // [7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:7:[]] lst3 = replicate(5, 23) let lst3.valueOf() // [23:23:23:23:23:[]] lst4 = cycle(list(5,4,3,2,1)) let 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: booleans = cycle(list(false, true)) const fib = n => n map(fib, take(n, listInf(1))) const const fact = n => n === 1 ? n : fact(n - 1) * n facts = n => map(fact, take(n, listInf(1))) const const sqrt = (a0, eps, n) => { within = (eps, rest) => { a = index(rest, 0) b = index(rest, 1) Math.abs(a - b) (x + n / x) / 2 within(eps, iterate(next.bind(null, n), a0))} const const let let return const return 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 function shown here uses an infinite list to compute the square root of a number , with a tolerance , and starting with an initial estimate . This example of the for calculating square roots is adapted from by John Hughes — essential reading, indeed. sqrt n eps a0 Newton-Raphson method Why Functional Programming Matters There you have it: lazy, functional, infinite lists in JavaScript with various operations you might perform on them! Once again, please see for even more 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: . my library on GitHub List 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 , 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, , 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. mathematical object algebraic data types The whole definition of a list in Haskell, for example, is . That one snippet of code accomplishes essentially the same thing as my entire class — and it’s all thanks to . Most languages have product types. Few have sum types. The JavaScript is a product type, because every object contains a field for every possible value. The we defined above is not a true sum type, but it does reproduce the functionality of a type that contains one value or set or values another value or set of values. Where product types represent , sum types represent . You wouldn’t go without in your boolean logic, so why go without it in your type system? Without the ability to define types as , you are trapped in a world of artificial hierarchies and over-specified abstractions. That’s what you get when everything is a , when you have no choice but to define custom types (i.e. classes) as aggregates of values rather than alternatives 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 to . And we prefer flexible lists to rigid arrays. JavaScript’s built-in 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. data [] a = [] | a : [a] the power and expressivity of sum types Object List either or and or or disjoint product type among Proteus Procrustes Array 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 . We can define a binary tree in Haskell as follows: . Like our type above, is a sum type, which means any given will be a a . is like : 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): binary trees data Tree a = Leaf | Node (Tree a) a (Tree a) List Tree Tree either Leaf or Node Leaf emptyList Tree { (left, label, right) { .left = () => left .label = () => label .right = () => right}} class constructor this this this leaf = Tree() const new node = (left, label, right) => Tree(left, label, right) const new insert = (x, t) => { (t === leaf) { node(leaf, x, leaf) } (x === t.label()) { t } (x 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()])) const And now let’s construct a test tree and try out our little library of functions: tree = leaf let squares = listInfBy(1, x => x * 2) let cubes = listInfBy(1, x => x * 3) let ( value take(10, squares)) { tree = insert(value, tree) } for let of 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]_ ( value take(5, cubes)) { tree = insert(value, tree) } for let of 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. is how hackers start their afternoons. We’re a part of the family. We are now and happy to opportunities. Hacker Noon @AMI accepting submissions discuss advertising &sponsorship To learn more, , , or simply, read our about page like/message us on Facebook tweet/DM @HackerNoon. If you enjoyed this story, we recommend reading our and . Until next time, don’t take the realities of the world for granted! latest tech stories trending tech stories