patrickt

data Lit
  = StrLit String
  | IntLit Int
  | Ident String
  deriving (Show, Eq)

data Expr
  = Index Expr Expr
  | Call [Expr]
  | Unary String Expr

patrickt

-- the representation of `printf("2 + 3 is %d", 2 + 3)`
printfExample :: Stmt
printfExample = 
  Expression 
    (Call 
      (Constant (Ident "printf")) 
        [ Constant (StrLit "2 + 3 is %d")
        , Binary 
            (Constant (IntLit 2)) 
            "+" 

patrickt

-- this would turn the expression
--    (((anArray[(10)])))
-- into
--    anArray[10]

flatten :: Expr -> Expr
  -- base case: do nothing to constants
  flatten (Constant i) = Constant i
  -- this is the important case: we shed the Paren constructor and just 
  -- apply `flatten` to its contents

patrickt

data Expr a
  = Index a a
  | Call [a]
  | Unary String a
  | Binary a String a
  | Paren a
  | Literal Lit
  deriving (Show, Eq)

patrickt

-- given a function f from a's to b's, `apply f` is a function that turns Expr a's into Expr b's
-- by mapping its argument over each subexpression of type a.
apply :: (a -> b) -> Expr a -> Expr b
-- The Constant constructor has no eligible subexpressions, so apply does nothing.
apply f (Constant ident) = (Constant ident)
-- Indexes have two children of type a; apply f to both of them.
apply f (Index x y) = Index (f x) (f y)
-- Calls have a list of arguments, so we map `apply f` over it
apply f (Call name args) = Call (f name) (map f args) 
-- et cetera, et cetera

patrickt

class Functor f where
  fmap :: Functor f => (a -> b) -> f a -> f b

patrickt

-- not legal Haskell!
type ExprTree = Expr (Expr (Expr (Expr ...)))

patrickt

fix :: (a -> a) -> a
fix f = f (fix f)

patrickt

newtype Term f = In { out :: f (Term f) } )

patrickt

{-# LANGUAGE DeriveFunctor #-}

data Expr a
  = Index a a
  | Call [a]
  | Unary String a
  | Binary a String a
  | Paren a
  | Literal Lit
  deriving (Show, Eq, Functor) -- fmap for free