如何在用递归方案编写的表达式计算器中编写更少的样板文件
How to write less boilerplate in a expression evaluator written with recursion-schemes
使用 recursion-scheme 库
编写抽象语法树和相应的表达式计算器很容易:
{-# 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
现在看eval
的where子句中的alg
函数中的情况。我认为所有 x
和 y
变量
应该没有必要。因此我正在寻找某种方式(语法、语言扩展等)
删除此样板并写入:
PlusF -> (+)
MultF -> (*)
ConstF -> id
https://hackage.haskell.org/package/catamorphism-0.5.1.0/docs/Data-Morphism-Cata.html 推导出 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
请注意,它还可以为 Expr
派生变形,生成 eval = expr (+) (*) id
并让您跳过此特定用例的 Data.Functor.Foldable.TH
。
或者,您可以重构您的语言,使其一方面具有二元运算,另一方面具有一元运算。你会写:
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
评价者则变成:
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
使用 recursion-scheme 库 编写抽象语法树和相应的表达式计算器很容易:
{-# 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
现在看eval
的where子句中的alg
函数中的情况。我认为所有 x
和 y
变量
应该没有必要。因此我正在寻找某种方式(语法、语言扩展等)
删除此样板并写入:
PlusF -> (+)
MultF -> (*)
ConstF -> id
https://hackage.haskell.org/package/catamorphism-0.5.1.0/docs/Data-Morphism-Cata.html 推导出 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
请注意,它还可以为 Expr
派生变形,生成 eval = expr (+) (*) id
并让您跳过此特定用例的 Data.Functor.Foldable.TH
。
或者,您可以重构您的语言,使其一方面具有二元运算,另一方面具有一元运算。你会写:
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
评价者则变成:
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