处理递归和类型时如何减少代码重复 [英] How to reduce code duplication when dealing with recursive sum types
问题描述
我目前正在为一种编程语言开发一个简单的解释器，并且我有一个像这样的数据类型：
data Expr
=可变字符串
|数字整数
|添加[Expr]
| Sub Expr Expr
我有很多函数可以执行以下简单操作：
-用变量
的值替换replaceName :: String->整数-> Expr-> Expr
替代名称name newValue = go
其中
去（变量x）
| x ==名称=数字newValue
go（加xs）=
添加$ map go xs
go（Sub xy）=
Sub（go x）（go y）
go other = other
-用一个常数替换减法，加一个负数
replaceSubWithAdd :: Expr-> Expr
replaceSubWithAdd = go
其中
go（Sub x（y））=
加[go x，Number（-y）]
go（Add xs ）=
添加$ map go xs
go（Sub xy）=
Sub（go x）（go y）
go other = other
但是在每个这些函数中，我都必须重复递归调用代码的部分，而对函数的一部分进行少量更改。有没有更通用的现有方法？我宁愿不必复制并粘贴此部分：
go（加xs）=
添加$地图xs
go（Sub xy）=
Sub（go x）（go y）
go other = other
每次都只更改一个大小写，因为复制这样的代码似乎效率低。
我唯一能解决的方法最重要的是有一个函数，该函数首先在整个数据结构上调用一个函数，然后递归地对如下结果进行调用：
recurseAfter ::（Expr-> Expr）-> Expr-> expr
recurse在f x =
情况下
的f x添加xs->
添加$地图（f后递归）xs
子x y->
Sub（f recurseAfter）（f recurseAfter）
其他->其他
AlternativeName ::字符串->整数-> Expr-> $ r
替代名name newValue =
recurse在$ \case
变量x
| x ==名称->数字newValue
其他->其他
replaceSubWithAdd :: Expr-> Expr
replaceSubWithAdd =
recurse在$情况下
Sub x（y）->
加[x，数字（-y）]
其他->其他
但是我觉得应该已经有一种更简单的方法了。我错过了什么吗？
恭喜，您刚刚重新发现了变形！
这是您的代码，将其改写为与 recursion-schemes 包一起使用。 las，它并不短，因为我们需要一些样板来使机械正常工作。 （可能有某种自动的方法来避免样板，例如使用泛型。我只是不知道。）
下面，您的 recurseAfter 替换为标准 ana 。
我们首先定义您的递归类型，以及
{-＃语言DeriveFunctor，TypeFamilies，LambdaCase＃-}
{ -＃选项-Wall＃-}
模块AnaExpr，其中
导入Data.Functor.Foldable
data Expr
=可变字符串
|数字整数
|添加[Expr]
| Sub Expr Expr
派生（显示）
数据ExprF a
= VariableF字符串
| NumberF Int
| AddF [a]
| SubF aa
派生（Functor）
然后我们将两者与几个实例连接起来，以便我们可以将 Expr 展开为同构的 ExprF Expr ，然后将其折回。
类型实例Base Expr = ExprF
实例递归Expr，其中
项目（变量s）= VariableF s
项目（编号i） = NumberF i
项目（Add es）= AddF es
项目（Sub e1 e2）= SubF e1 e2
实例Corecursive Expr其中
嵌入（VariableF s）=变量s
embed（NumberF i）=数字i
embed（AddF es）=添加es
embed（SubF e1 e2）= Sub e1 e2
最后，我们调整您的原始代码，并添加一些测试。
substituteName ::字符串->整数-> Expr-> Expr
替代名称name newValue = ana $ \case
变量x | x ==名称-> NumberF newValue
其他->项目其他
testSub :: Expr
testSub = AlternativeName x 42（添加[Add [Add [Variable x]，数字0]]）
replaceSubWithAdd： ：Expr-> Expr
replaceSubWithAdd = ana $ \case
Sub x（y）-> AddF [x，数字（-y）]
其他->项目其他
testReplace :: Expr
testReplace = replaceSubWithAdd
（添加[子（添加[变量 x，子（变量 y）（数字34）]）） （数字10），数字4]）
另一种方法是定义仅表示ExprF a ，然后得出类型Expr = Fix ExprF 。这节省了上面的一些样板（例如，两个实例），但以不得不使用 Fix（VariableF ...）而不是 Variable为代价... ，以及其他构造方法的类似方法。
一个人可以进一步减轻使用模式同义词的负担（代价是
更新：我终于使用模板Haskell找到了自动魔术工具。这使得整个代码相当短。请注意， ExprF 函子和上面的两个实例仍然存在，并且我们仍然必须使用它们。我们仅省去了手动定义它们的麻烦，仅此一项就节省了很多工作。
{-＃语言DeriveFunctor ，DeriveTraversable，TypeFamilies，LambdaCase，TemplateHaskell＃-}
{-＃OPTIONS -Wall＃-}
AnaExpr模块，其中
import Data.Functor.Foldable
import Data.Functor.Foldable.TH
data Expr
=可变字符串
|数字整数
|添加[Expr]
| Sub Expr Expr
deriving（显示）
makeBaseFunctor’’Expr
替代名称::字符串->整数-> Expr-> Expr
替代名称name newValue = ana $ \case
变量x | x ==名称-> NumberF newValue
其他->项目其他
testSub :: Expr
testSub = AlternativeName x 42（添加[Add [Add [Variable x]，数字0]]）
replaceSubWithAdd： ：Expr-> Expr
replaceSubWithAdd = ana $ \case
Sub x（y）-> AddF [x，数字（-y）]
其他->项目其他
testReplace :: Expr
testReplace = replaceSubWithAdd
（添加[子（添加[变量 x，子（变量 y）（数字34）]）） （数字10），数字4]）
I am currently working on a simple interpreter for a programming language and I have a data type like this:
data Expr
= Variable String
| Number Int
| Add [Expr]
| Sub Expr Expr
And I have many functions that do simple things like:
-- Substitute a value for a variable
substituteName :: String -> Int -> Expr -> Expr
substituteName name newValue = go
where
go (Variable x)
| x == name = Number newValue
go (Add xs) =
Add $ map go xs
go (Sub x y) =
Sub (go x) (go y)
go other = other
-- Replace subtraction with a constant with addition by a negative number
replaceSubWithAdd :: Expr -> Expr
replaceSubWithAdd = go
where
go (Sub x (Number y)) =
Add [go x, Number (-y)]
go (Add xs) =
Add $ map go xs
go (Sub x y) =
Sub (go x) (go y)
go other = other
But in each of these functions, I have to repeat the part that calls the code recursively with just a small change to one part of the function. Is there any existing way to do this more generically? I would rather not have to copy and paste this part:
go (Add xs) =
Add $ map go xs
go (Sub x y) =
Sub (go x) (go y)
go other = other
And just change a single case each time because it seems inefficient to duplicate code like this.
The only solution I could come up with is to have a function that calls a function first on the whole data structure and then recursively on the result like this:
recurseAfter :: (Expr -> Expr) -> Expr -> Expr
recurseAfter f x =
case f x of
Add xs ->
Add $ map (recurseAfter f) xs
Sub x y ->
Sub (recurseAfter f x) (recurseAfter f y)
other -> other
substituteName :: String -> Int -> Expr -> Expr
substituteName name newValue =
recurseAfter $ \case
Variable x
| x == name -> Number newValue
other -> other
replaceSubWithAdd :: Expr -> Expr
replaceSubWithAdd =
recurseAfter $ \case
Sub x (Number y) ->
Add [x, Number (-y)]
other -> other
But I feel like there should probably be a simpler way to do this already. Am I missing something?
Congratulations, you just rediscovered anamorphisms!
Here's your code, rephrased so that it works with the recursion-schemes package. Alas, it's not shorter, since we need some boilerplate to make the machinery work. (There might be some automagic way to avoid the boilerplate, e.g. using generics. I simply do not know.)
Below, your recurseAfter is replaced with the standard ana.
We first define your recursive type, as well as the functor it is the fixed point of.
{-# LANGUAGE DeriveFunctor, TypeFamilies, LambdaCase #-}
{-# OPTIONS -Wall #-}
module AnaExpr where
import Data.Functor.Foldable
data Expr
= Variable String
| Number Int
| Add [Expr]
| Sub Expr Expr
deriving (Show)
data ExprF a
= VariableF String
| NumberF Int
| AddF [a]
| SubF a a
deriving (Functor)
Then we connect the two with a few instances so that we can unfold Expr into the isomorphic ExprF Expr, and fold it back.
type instance Base Expr = ExprF
instance Recursive Expr where
project (Variable s) = VariableF s
project (Number i) = NumberF i
project (Add es) = AddF es
project (Sub e1 e2) = SubF e1 e2
instance Corecursive Expr where
embed (VariableF s) = Variable s
embed (NumberF i) = Number i
embed (AddF es) = Add es
embed (SubF e1 e2) = Sub e1 e2
Finally, we adapt your original code, and add a couple of tests.
substituteName :: String -> Int -> Expr -> Expr
substituteName name newValue = ana $ \case
Variable x | x == name -> NumberF newValue
other -> project other
testSub :: Expr
testSub = substituteName "x" 42 (Add [Add [Variable "x"], Number 0])
replaceSubWithAdd :: Expr -> Expr
replaceSubWithAdd = ana $ \case
Sub x (Number y) -> AddF [x, Number (-y)]
other -> project other
testReplace :: Expr
testReplace = replaceSubWithAdd
(Add [Sub (Add [Variable "x", Sub (Variable "y") (Number 34)]) (Number 10), Number 4])
An alternative could be to define ExprF a only, and then derive type Expr = Fix ExprF. This saves some of the boilerplate above (e.g. the two instances), at the cost of having to use Fix (VariableF ...) instead of Variable ..., as well as the analogous for the other constructors.
One could further alleviate that using pattern synonyms (at the cost of a little more boilerplate, though).
Update: I finally found the automagic tool, using template Haskell. This makes the whole code reasonably short. Note that the ExprF functor and the two instances above still exist under the hood, and we still have to use them. We only save the hassle of having to define them manually, but that alone saves a lot of effort.
{-# LANGUAGE DeriveFunctor, DeriveTraversable, TypeFamilies, LambdaCase, TemplateHaskell #-}
{-# OPTIONS -Wall #-}
module AnaExpr where
import Data.Functor.Foldable
import Data.Functor.Foldable.TH
data Expr
= Variable String
| Number Int
| Add [Expr]
| Sub Expr Expr
deriving (Show)
makeBaseFunctor ''Expr
substituteName :: String -> Int -> Expr -> Expr
substituteName name newValue = ana $ \case
Variable x | x == name -> NumberF newValue
other -> project other
testSub :: Expr
testSub = substituteName "x" 42 (Add [Add [Variable "x"], Number 0])
replaceSubWithAdd :: Expr -> Expr
replaceSubWithAdd = ana $ \case
Sub x (Number y) -> AddF [x, Number (-y)]
other -> project other
testReplace :: Expr
testReplace = replaceSubWithAdd
(Add [Sub (Add [Variable "x", Sub (Variable "y") (Number 34)]) (Number 10), Number 4])
这篇关于处理递归和类型时如何减少代码重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
