[Haskell-cafe] Excercise on tagless final interpreters

[Jacques Carette]

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