Wobbly types

Wobbly types: type inference for generalised algebraic data types

Simon Peyton Jones, Geoffrey Washburn, and Stephanie Weirich.
July 2004

Generalised algebraic data types (GADTs), sometimes known as "guarded recursive data types" or "first-class phantom types", are a simple but powerful generalisation of the data types of Haskell and ML. Recent works have given compelling examples of the utility of GADTs, although type inference is known to be difficult.

It is time to pluck the fruit. Can GADTs be added to Haskell, without losing type inference, or requiring unacceptably heavy type annotations? Can this be done without completely rewriting the already-complex Haskell type-inference engine, and without complex interactions with (say) type classes? We answer these questions in the affirmative, giving a type system that explains just what type annotations are required, and a prototype implementation that implements it. Our main technical innovation is wobbly types, which express in a declarative way the uncertainty caused by the incremental nature of typical type-inference algorithms.

Edit: Made the title into a hyperlink, as the "Postscript" link could easily get lost in a sea of blue text...

Edit 2:Quoted the article with a plain-ol' <blockquote> instead. Better?

Functional programming in Java


Vadim Nasardinov pointed out this article, which although pitched at an introductory level, provides a reasonably thorough overview of functional programming possibilities in Java. It focuses on the use of closures and higher-order functions, via Java's anonymous inner classes, and works its way up to "using closures to implement business rules" as one of its concrete examples.

Perhaps a little too introductory for LtU, but articles like this can be a useful starting point when talking to Java programmers who've had little or no previous exposure to FP, or who need some hints about useful ways to apply FP concepts in Java. Using anonymous inner classes to implement e.g. GUI event listeners in Java is common practice, but often, more advanced and useful possibilities are overlooked.

OCaml Release 3.08.0

Objective Caml release 3.08.0 is official and incorporates many improvements. A big thank-you to the OCaml team for this stable release. Those on the bleeding edge of post-3.08 CVS work can follow Xavier's advice.

Functional programming with GNU make

One of the gems squirreled away on Oleg's site is "Makefile as a functional language program":

"The language of GNU make is indeed functional, complete with combinators (map and filter), applications and anonymous abstractions. That is correct, GNU make supports lambda-abstractions."

Although I've classified this under Fun, Oleg exploits
the functional nature of Make for a real, practical application:

"...avoiding the explosion of makefile rules in a project that executes many test cases on many platforms. [...] Because GNU make turns out to be a functional programming system, we can reduce the number of rules from <number-of-targets> * <number-of-platforms> to just <number-of-targets> + <number-of-platforms>."

See the article for a code comparison
between make and Scheme, and check out the Makefile in question.

Enumerating the Rationals

Jeremy Gibbons, David Lester and Richard Bird (2004). Enumerating the Rationals. May 2004.

In this paper,we explain an elegant technique for enumerating the positive rationals without duplicates. Moreover, we show how to do so as a simple iteration, generating each element of the enumeration from the previous one alone,with constant cost per element (assuming unit cost for simple operations on arbitrary-precision rationals). Best of all, the resulting program is extremely simple...

Cute. Nothing earth shattering, but fun none the less.

Debugging Functional Programs

An interesting thread on the Haskell mailing list.

I am not sure whether the most reasonable conclusion from this thread isn't to not choose lazy languages. I don't think it's simply a problem of lack of tools. Debugging lazy code is iherently problematic.

XML feed