On 13-03-21 06:32 AM, matteo vezzola wrote:
I'm playing with tagless final interpreters reading [1], using a very simple language:
class Ints repr where int :: Integer -> repr Integer (.+.) :: repr Integer -> repr Integer -> repr Integer (.*.) :: repr Integer -> repr Integer -> repr Integer (.-.) :: repr Integer -> repr Integer (.<=.) :: repr Integer -> repr Integer -> repr Bool newtype P repr t = P { unP :: Bool -> repr t } instance Ints repr => Ints (P repr) where int n = P $ \ s -> if s then int n else (.-.) (int n) (.-.) n = P $ unP n . not n .+. m = P $ \ s -> unP n s .+. unP m s n .*. m = P $ \ s -> unP n s .*. unP m s n .<=. m = P $ \ s -> unP n s .<=. unP m s After pushing down negations I'd like to distribute (.*.) over (.+.). [1] leaves it as an exercise, so it can't be that hard, but I don't get it...
Anyone knows how I could do it?
[1]: http://okmij.org/ftp/tagless-final/course/lecture.pdf
thanks,
It is exactly the same idea: you use a context to track whether you have something (a multiplication) waiting to be distributed. It is a tad more involved because you need to track more than a single bit of information. Write it out: draw two ASTs, one where there is something to distribute, and another where there isn't, put yourself in the position of the addition, and think "what information would I need now to perform the distribution". Once you've figured that out, the rest is straightforward. You do need to figure out the non-distribution case as well, otherwise you'll find yourself pushing a context too far and get wrong answers. Jacques