[Haskell-cafe] Finally tagless - stuck with implementation of "lam"

[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