Home » forums » LtU Forum

Algebraic Data Types in JavaScript

It is generally known that JavaScript supports a functional style of programming. But because it does not have algebraic data types, the functional programming is usually limited to some simple higher order functions applied to Arrays.

I have often build small libraries that allow working with some aspects of algebraic data types in JavaScript. This time I thought is was cool enough to write a bit about it:

Algebraic Data Types in JavaScript

It includes:

  • a very small footprint
  • unfold, map and fold over any adt
  • merging (read deforestation/fusion) of unfold, map and fold
  • user defined derived properties (think derived classes Show, Eq...)

I also show how to do the Data Types à la carte style of Wouter Swierstra with this library.

By Sjoerd Visscher at 2008-06-17 17:42 | LtU Forum | previous forum topic | next forum topic | other blogs | 20969 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

neat stuff

This is very interesting! Some questions:

  1. What specifies the constructor argument order? For example, why is it that
    Point = Data(function() ({ Pt: { x: Number, y: Number, color: Color } }))
    results in a constructor where the argument order is x, y, color?
  2. What exactly do the "type" annotations in the Data declaration mean? Are they somehow checked, or do they correspond to the way the data is constructed?
  3. Similarly, what purpose do the parameterized type arguments serve? They aren't being checked somehow, are they?

I like how the recursion is explicit, as if you had a type fixpoint combinator μ. I'm also thrilled to see you using expression closures (I'm ecstatic that FF 3 has added them already, even before ES4 is done).

By Dave Herman at Tue, 2008-06-17 22:35 | login or register to post comments

Thanks!

  1. Syntactic order, using for/in. I know it is not spec'ed to be in order, but every browser has to implement it that way, if they don't want to break the web. If you really want to be sure, you can also use the array syntax, then your properties will be called 0, 1, 2.
  2. If you build a transformer, those types are passed to getAtomXF. I realize now that this means that you could build a type checker as a fold. But some built in type checking might not be a bad idea.
  3. Type parameters are used when the type is used in another type, like List in the Node type. F.e. fold has to know that the recursion of Node occurs inside the List structure. And the map method uses this: you pass a function for each type parameter.

I love expression closures! I don't think I would have finished this without them, the code simply becomes too horrible to look at.

By Sjoerd Visscher at Tue, 2008-06-17 23:31 | login or register to post comments

Re: Thanks!

Syntactic order, using for/in. I know it is not spec'ed to be in order, but every browser has to implement it that way, if they don't want to break the web. If you really want to be sure, you can also use the array syntax, then your properties will be called 0, 1, 2.

Well, browser-specific enumeration order is a bit thorny-- not all browsers behave exactly the same. Although I think they behave the same for arrays created from the literal syntax, so you might be safe there. But relying on for/in enumeration order is a delicate affair.

I love expression closures! I don't think I would have finished this without them, the code simply becomes too horrible to look at.

You bet! For an admittedly contrived example, compare

function Z(f) {
    return (function (x) { return f(function (y) {
                                        return x(x)(y)
                                    }) })( // must place paren on this line!!!
            function (x) { return f(function (y) {
                                        return x(x)(y)
                                    }) });
}

with:

function Z(f)
    (function (x) f(function (y) x(x)(y)))
    (function (x) f(function (y) x(x)(y)))

By Dave Herman at Wed, 2008-06-18 01:04 | login or register to post comments

I saw this yesterday and

I saw this yesterday and planned to post it, so I am instead promoting this to the home page.

I guess it's member week here on LtU...

By Ehud Lamm at Wed, 2008-06-18 00:07 | login or register to post comments

Comparison with generic programming approaches in Haskell

I read Comparing Approaches to Generic Programming in Haskell. It seems that my implementation looks the most like PolyP. The "structure representation" contains both recursion and type parameters, which also means that it can only support regular types.

But you can also do SYB stuff, f.e. the paradise benchmark looks like this:

increase = function(k) Company.fold({ S: function(s) S (s * (1+k)) })

By Sjoerd Visscher at Wed, 2008-06-18 21:59 | login or register to post comments