Circular Instance Declarations

[Ashley Yakeley]

In article <Pine.GSO.4.44.0309091136120.26237-100000@clyde>,
 Brandon Michael Moore <brandon@its.caltech.edu> wrote:

> A simple irregular type is
> Irr a = Con a (Irr (F a))
> (as long as F uses a)

Would this be an irregular type, with F as ((->) val)?

  data SymbolExpression sym val a = ClosedSymbolExpression a |
   OpenSymbolExpression sym (SymbolExpression sym val (val -> a));

I used to use this in HScheme for expressions with free variables, as in 
the lambda calculus. For instance, "\x.xy" has "y" as a free variable, 
and might be represented as something like this:

  OpenSymbolExpression "y" (ClosedSymbolExpression (\y -> (\x -> x y)))

It's very clean and safe, and can be made an instance of 
FunctorApplyReturn, but it turned out to be a bit slow. I also tried 
this:

  data ListSymbolExpression sym val a =
     MkListSymbolExpression [sym] ([val] -> a);

  MkListSymbolExpression ["y"] (\[y] -> (\x -> x y))

This is much simpler, but now one has to make sure that the lists are 
the same size, so to speak. But this one turned out to be the fastest:

  newtype FuncSymbolExpression sym val a =
   MkFuncSymbolExpression ((sym -> val) -> a);

  MkFuncSymbolExpression (\f -> (\x -> x (f "y")))

The downside is that there's no way to find out what the free variables 
are. That's OK for Scheme, however, since Scheme doesn't complain about 
unbound variables until run-time.

So, um, any excuse to talk about HScheme anyway.

-- 
Ashley Yakeley, Seattle WA