[Haskell-cafe] Finally tagless and abstract relational Algebra

Günther Schmidt gue.schmidt at web.de
Mon Dec 28 10:39:25 EST 2009

Hi Jacques,

well in short my post is supposed to pretty much lay bare my lack of 
understanding of the problem I try to solve, with the hope that someone 
is willing to fill the gaps.

I do know that I could express my algorithms via list-comprehension or 
in a List Monad, all using tuples. And that would be concrete and 
grossly inefficient.

But I also wouldn't be able to express an incorrectly typed term 
*thanks* to using tuples.

So how would it be possible to express selecting /field/ b from /record/ 
x and field c from record y, creating record z, while making sure that 
record x does have field b and record y does have field c? I mean design 
a syntax for it?


Am 28.12.09 16:15, schrieb 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091228/3bc7c59c/attachment.html

More information about the Haskell-Cafe mailing list