Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to write less boilerplate in a expression evaluator written with recursion-schemes

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 
like image 931
Jogger Avatar asked Feb 03 '18 17:02

Jogger


2 Answers

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.

like image 58
Gurkenglas Avatar answered Nov 20 '22 20:11

Gurkenglas


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
like image 1
gallais Avatar answered Nov 20 '22 22:11

gallais