With the recursion-scheme library it's easy to write abstract syntax trees and the corresponding expression evaluators:
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE LambdaCase #-}
import Data.Functor.Foldable
import Data.Functor.Foldable.TH
data Expr = Plus Expr Expr
| Mult Expr Expr
| Const Expr
deriving (Show, Eq)
makeBaseFunctor ''Expr
-- Write a simple evaluator
eval :: Expr -> Int
eval = cata alg
where
alg = \case
PlusF x y -> (+) x y
MultF x y -> (*) x y
ConstF x -> x
Now look at the case in the alg
function in the where clause of eval
. I think all the x
and y
variables
should not be necessary. Therefore I'm looking for some way (a syntax, a language extension etc.)
to remove this boilerplate and just to write:
PlusF -> (+)
MultF -> (*)
ConstF -> id
https://hackage.haskell.org/package/catamorphism-0.5.1.0/docs/Data-Morphism-Cata.html derives a catamorphism for ExprF
.
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE TemplateHaskell #-}
import Data.Functor.Foldable
import Data.Functor.Foldable.TH
import Data.Morphism.Cata
data Expr
= Plus Expr Expr
| Mult Expr Expr
| Const Expr
deriving (Show, Eq)
makeBaseFunctor ''Expr
$(makeCata defaultOptions ''ExprF)
-- Write a simple evaluator
eval :: Expr -> Int
eval = cata $ exprF (+) (*) id
Note that it can also derive a catamorphism for Expr
, yielding eval = expr (+) (*) id
and letting you skip Data.Functor.Foldable.TH
for this specific usecase.
Alternatively you could refactor your language to have binary operations on one hand and unary ones on the other. You'd write:
data BinOp = PlusOp | MultOp deriving (Show, Eq)
data UnOp = ConstOp deriving (Show, Eq)
data Expr = Bin BinOp Expr Expr
| Un UnOp Expr
deriving (Show, Eq)
makeBaseFunctor ''Expr
The evaluator then becomes:
eval :: Expr -> Int
eval = cata $ \case
BinF op l r -> bin op l r
UnF op v -> un op v
where
bin = \case
PlusOp -> (+)
MultOp -> (*)
un = \case
ConstOp -> id
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With