Friday, June 20th, 2008

Algebraic Data Types in JavaScript

Category: JavaScript

Sjoerd Visscher has written a library that lets you create algebraic data types in JavaScript for use in your functional programming world.

ADT.js is written in JavaScript 1.8 “which means that as of this writing it only runs in Firefox 3.0. I have chosen to keep it 1.8, because the code is a lot cleaner, thanks to the new expression closures. But there is nothing that cannot be made to work in ECMAScript edition 3. And I have no doubt that the same thing could be done in Python or Ruby.”

Now you have the library, you can create types like this (with Haskell to compare):

javascript

  1. // Haskell:
  2. // data Color = Red | Green | Blue | Yellow
  3. // data Point = Pt Float Float Color
  4. Color = Data(function() ({ Red: {}, Green: {}, Blue: {}, Yellow: {} }))
  5. Point = Data(function() ({ Pt: { x: Number, y: Number, color: Color } }))
  6.  
  7. // Haskell:
  8. // data Attrs n v = Attr n v
  9. // data Node  n v = Elem n (List (Attrs n v)) (List (Node n v)) | Text v
  10. Attrs = Data(function(_, n, v) ({ Attr: {name: n, value: v} }))
  11. Node = Data(function(node, n, v) ({
  12.   Elem: { name: n, attributes: List(Attrs(n, v)), childNodes: List(node) },
  13.   Text: v
  14. }))

Now you have the types, you can do things to them:

javascript

  1. // With unfold you can easily generate algebraic data structures from other data. The following example shows how to generate a decreasing list of numbers.
  2. var counter = List.unfold(function(n, c) n ? c.Cons(n, n - 1) : c.Nil)
  3.  
  4. // Fold is the reverse of unfold. It destructs data into a return value. Here is an example that multiplies a list of numbers.
  5. var prod = List.fold({ Nil: 1, Cons: function(h, t) h * t })
  6.  
  7. // With map you provide a function for each type parameter. Here are 2 examples using the XML data types
  8. var addPrefix = Node.map(function (name) "x:" + name, id)
  9. var normalizeSpace = Node.map(id, function (value) value.replace(/^\s+|\s+$/g, ""))

And, a lot more.

Posted by Dion Almaer at 6:12 am
Comment here

+++--
3.7 rating from 21 votes

Comments Here »

Comments feed TrackBack URI

Leave a comment

You must be logged in to post a comment.