Eval.hs

-- Copyright 2018 Google LLC.
-- SPDX-License-Identifier: Apache-2.0

{-# LANGUAGE FlexibleContexts #-}

import Control.Applicative
import Control.Monad.Writer

data Expr = Lit Int | Plus Expr Expr | Times Expr Expr
  deriving (Eq, Show)

ev ev e = ev' e
  where ev' (Lit i) = pure i
        ev' (Plus a b) = liftA2 (+) (ev a) (ev b)
        ev' (Times a b) = liftA2 (*) (ev a) (ev b)

evTell ev0 ev e = do
  v <- ev0 ev e
  tell [(e, v)] 
  return v

eval e = execWriter (fix (evTell ev) e)

main = mapM_ print (eval test)
  where test = (Lit 1 `Plus` Lit 2) `Times` (Lit 3 `Plus` Lit 4)

Ouputs:

(Lit 1,1)
(Lit 2,2)
(Plus (Lit 1) (Lit 2),3)
(Lit 3,3)
(Lit 4,4)
(Plus (Lit 3) (Lit 4),7)
(Times (Plus (Lit 1) (Lit 2)) (Plus (Lit 3) (Lit 4)),21)

This is nice, but is there a way to stuff the result alongside the AST, as in
(Times (Plus (Lit 1, 1) (Lit 2, 2), 3) (Plus (Lit 3, 3) (Lit 4, 4), 7),21) ?
IMO it is shorter and context is maintained.