[Haskell-cafe] Finally tagless and abstract relational Algebra

[Jacques Carette]

Günther Schmidt wrote:
> My guess is that finally tagless style allows one to create a syntax
> without any initial dependency to an implementation. Ie. once one has
> created the syntax in this style one can then proceed to construct terms.
Yes.

> So this is my goal, create a syntax for relational algebra, express an
> abstract relational algorithm in this syntax and worry about
> implementation / compilation / evaluation *later*. But at least being
> able to express a correctly typed term.
Good plan.  But syntax design is hard, whatever style you choose.

> I presume I will need to employ HList at some point, but I'm not
> entirely certain where. Will I need it at the very beginning, as
> constrains in the syntax so that only correct abstract terms can be
> built, or will I need it in on of the interpreters / compilers later?
You will not need HList for constraining the syntax -- Haskell's type
system should already provide all you need to constrain the syntax.  In
fact, in tagless final style (rather than in initial style), for the
lambda calculus you don't even need GADTs to deal with exotic terms! 

Why do you think you'll have to use HList?  While HList is great, in
this particular instance, I don't think you'll need it.

Jacques