DailyJS

DailyJS

The JavaScript blog.


Tagalgorithms
Featured

lazy lisp modules clojure algorithms

Lazy Arrays

Posted on .

Oliver Caldwell has been working on a module that lets you use lazy arrays (GitHub: Wolfy87/lazy-array, License: The Unlicense, npm: lazy-array) in JavaScript. If you've ever used Clojure for any amount of time you'll find you start actually thinking in lazy sequences, and start wanting to use them on other platforms.

Clojure's lazy sequences are sequences of values that you can query, slice, and compose. They're generated algorithmically but don't haven't to exist entirely in memory. A good example of this is the Fibonacci sequence. With Oliver's module you can define and manipulate the Fibonacci sequence like this:

var larr = require('lazy-array');

function fib(a, b) {  
  return larr.create(function() {
    return larr.cons(a, fib(b, a + b));
  });
}

var f = fib(1, 1);  
larr.nth(f, 49); // 12586269025  

In this example, the larr.create method defines a sequence using larr.cons, which is a "core sequence" function. The methods provided by Lazy Array are based on Clojure's lazy sequence methods, so you get the following:

  • first: Get the first item
  • rest: Get the tail of the array
  • cons: Constructs a new array by prepending the item on the list
  • take: Returns a lazy array which is limited to the given length
  • drop: Returns a lazy array which drops the first n results
  • nth: Fetches the nth result

There are more methods -- if you want to see the rest look at the JSDoc comments in lazy-array.js.

Lazy sequences are not magic: you can easily make Clojure blow up:

(defn fib [a b] (lazy-seq (cons a (fib b (+ a b)))))

(take 5 (fib 1 1))
; (1 1 2 3 5)

(take 2000 (fib 1 1))

; ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1424)

But the point isn't that they're a way of handling huge piles of data, it's more a programming primitive that makes generative algorithms easier to reason about. What I really like about Oliver's work is he links it to UI development:

We JavaScript frontend wranglers deal with events, networking and state all day long, so building this had me wondering if I could apply laziness to the UI domain. The more I thought about this concept and talked with colleagues about it I realised that I’m essentially heading towards functional reactive programming, with bacon.js as a JavaScript example.

The UI example Oliver uses is based on an infinite lazy array of all possible times using a given start date and step timestamp. This might be a concise way of representing a reactive calendar widget.

If you're interested in lazy sequences and want to read more about Clojure, I found Lazy Sequences in Clojure useful when fact checking this article.

Featured

algorithms programming

Computer Science in JavaScript

Posted on .

Computer Science in JavaScript is
a set of classic computer science algorithms implemented in JavaScript.
To download, use git:

git clone git://github.com/nzakas/computer-science-in-javascript.git

This will download a set of scripts that implement base64, linked lists,
binary tree search, sorting, searching and checksums. These actually
cover the first year of the computing degree that I studied -- the
basics of data structures, algorithms and encoding.

Of particular interest to coming of age JavaScript hackers will be the
linked list implementations. The developer, Nicholas C.
Zakas
has even included unit tests (Written
with YUI). The scripts include comments with explanations of the methods
used, so it's best to check out the code and read it if you want to
explore this collection.