reify/reflect

reify-reflect.hs

{-

Examples:

> reify @Int $ eval $ A (reflect (abs :: Int -> Int)) (I (-9))
9

> reify @Int $ eval $ A (A (reflect ((*) :: Int -> Int -> Int)) (reflect @Int 3)) (reflect @Int 5)
15

> reify @[Int] $ eval $ A (reflect (reverse :: [E] -> [E])) (reflect ([1..3] :: [Int]))
[3,2,1]

> reify @[Int] $ eval $ A (A (reflect (map :: (E -> E) -> [E] -> [E])) (reflect @(Int -> Int) (* 2))) (reflect ([1..3] :: [Int]))
[2,4,6]

Using an instance of Eq/Ord for E:

> reify @Int $ eval $ A (reflect (minimum :: [E] -> E)) (reflect ([4,5,2,7] :: [Int]))
2

etc.

-}

{-# language TypeApplications, ScopedTypeVariables #-}

data E = A E E
       | F (E -> E)
       | I Int
       | List [E]

instance Eq E where
  (==) (I x) (I y) = (==) x y

instance Ord E where
  compare (I x) (I y) = compare x y

class Reflect t where
  reflect :: t -> E
  reify :: E -> t

instance Reflect Int where
  reflect = I
  reify (I i) = i

instance (Reflect i, Reflect o) => Reflect (i -> o) where
  reflect f = F (reflect @o . f . reify)
  reify (F f) = reify @o . f . reflect

instance Reflect E where
  reflect = id
  reify = id

instance Reflect a => Reflect [a] where
  reflect = List . map reflect
  reify (List es) = map reify es

eval (A f x) = (reify (eval f)) (eval x)
eval (List es) = List (map eval es)
eval e = e