How to write fewer patterns in an expression evaluator written using recursion schemes

Question

With the recursion-scheme library, it is easy to write abstract syntax trees and corresponding expression evaluations:

{-# 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 xy -> (+) xy MultF xy -> (*) xy ConstF x -> x 

Now consider the case in the alg function in the where eval clause. I think all variables x and y not required. So I'm looking for some way (syntax, language extension, etc.), delete this template and just write:

  PlusF -> (+) MultF -> (*) ConstF -> id 

Answer 1

Alternatively, you can reorganize your language into binary operations on the one hand and unary on the other. You must 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 

Then the evaluator becomes:

 eval :: Expr -> Int eval = cata $ \case BinF op lr -> bin op lr UnF op v -> un op v where bin = \case PlusOp -> (+) MultOp -> (*) un = \case ConstOp -> id 

Answer 2

https://hackage.haskell.org/package/catamorphism-0.5.1.0/docs/Data-Morphism-Cata.html gets 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 

Please note that it can also get catamorphic for Expr , which gives eval = expr (+) (*) id and allows you to skip Data.Functor.Foldable.TH for this particular utility.