Hi Jacques,
thank you again for your post, better late than never :)!
Let me first apologize to you, I did not immediately recognize you as one
of the authors of the "Finally Tagless" paper.
After 2 years now of using haskell at a mere layman's level and
nevertheless writing better and more concise code than in the 10 years
before using other languages I was ready to move a step further.
I must admit that things like type arithmetic, monads, functors and
whathaveyou can be quite intimidating, but the other day I wrote my first
monad, and it really wasn't that hard at all.
Anyway, so I had managed to improve my code slightly by introducing an
abstraction, a tiny, trivial, naive DSL. That certainly was an eye-opener.
When you gave me your solution, I realized that while it was correct, that
just couldn't be the last word on it. Something from Oleg that contains a
bug? Can't be, I must have a mistake in my thinking here. So I didn't give
up on "Finally Tagless" but read everything I could get my hands on, plus
the responses to my posts were also quite enlightening.
One minor problem with your paper, and other work from Oleg, well to me
that is, I don't ML. Also Oleg is such an "insider" sometimes he forgets
tiny hints for the rest of us. The initial post (not from me) was about
"An issue with finally tagless ..." and in Olegs response to that he
eliminates the problem with ease (I know, typically Oleg). Well as soon as
I tried that nothing worked until I put the "NoImplicitPrelude" in there,
duh.
So at least now I know what to do next:
Design an EDSL taglessly for relational algebra (using HList too)
write one or 2 interpreters / compilers for SQL and in-memory
Dump the code I have written so far and pretend I never had.
Best wishes
Günther
Am 15.10.2009, 17:05 Uhr, schrieb Jacques Carette
(sorry for the slow reply on this topic...)
Robert Atkey and Oleg presented some very interesting code in response to your query. But some of you might (and should!) be asking "why on earth did Jacques use unsafePerformIO?", especially when neither Robert nor Oleg did.
Simply put: I answered your question exactly as asked, while they answered the question you *should* have asked. At the exact 'type' involved in your question, there is no good answer; if you want an instance of lam at a monadic type 'directly', you need to 'extract' from the monad. But the point is that that isn't really the right question. Rather than requiring complete parametric polymorphism in the answer-type, if you allow a little non-uniformity through a simple type family, the shift in types is sufficient to no longer require a monadic 'extract' at all.
But even once you've gotten to that point, that's not enough, because at that point you still have the issue of what calling convention (by value, name or need) to use. And figuring that out is rather fun, so you got detailed answer from Robert and Oleg explaining that part in detail. Robert carefully used IntT and :-> to label the different types, and Oleg's code (http://okmij.org/ftp/tagless-final/CB.hs) showed how these were really just 'labels', which are useful mnemonics for humans, but not essential.
If you dig into our JFP paper describing "finally tagless" in all its gory details, you'll see that we use a poor man's version of type families there too (see section 4.3). Jacques