时间戳

首页 > 解决方案 > 在模式匹配中首先强制评估？

haskell - 在模式匹配中首先强制评估？

问题描述

在对传递给函数的 Data 构造函数内的参数进行评估后，我想在模式上重新运行一个函数。例如

func (Plus a b) = func (Plus (func a) (func b))

请注意a和func a属于同一类型。当我尝试调用这样的东西时，程序被挂断了，我认为正在发生的事情是模式在评估内部之前无限期地与自身匹配(func a)and (func b)，否则会将其匹配到不同的模式。我试过使用类似的东西

func (Plus a b) = func (Plus newa newb)
    where newa = func a
          newb = func b

尝试强制评估func aandfunc b首先，但这不起作用。我想要做的甚至可能吗？

谢谢。

标签： haskellrecursionpattern-matchingghci

解决方案

你确实进入了一个循环，你Plus一遍又一遍地匹配，但你期望什么？

func (Plus a b)
   = func (Plus (func a) (func b))
   = func (Plus (func (func a)) (func (func b)))
   = func (Plus (func (func (func a))) (func (func (func b))))

问题在于您本质上是在说“评估func构造函数Plus，评估构造函数”。 funcPlus

其余的是func什么样子的？原则上，如果整个定义类似于：

func (Plus (Lit n) (Lit m)) = Lit (n + m)
func (Plus a b) = func (Plus (func a) (func b))

这里如果func a最终func b归约到Lit，那么第一个模式将匹配并且调用将终止。但是我会犹豫以这种方式编写一个函数，因为你怎么知道反复调用func一个参数最终会收敛到Lit？可能会出现不会的情况。

I suspect you are writing a symbolic evaluator. The better way to do this is to come up with a normal form for expressions, and then have your reducer reduce to the normal form. A normal form is a unique representation that you can always reduce an expression to. It sometimes takes some cunning to come up with a good normal form. But let's say your expression type were:

data Expr = Lit Int | Var String | Plus Expr Expr

For this, an example normal form might be:

data ExprNF = ExprNF Int [String]

which represents a constant plus a sum of variables in sorted order (keep it sorted so that equivalent expressions always compare equal). So if your expression were

1 + (x + 2) + (3 + 6) + (x + (y + x))

It would become the normal form:

ExprNF 10 ["x","x","x","y"]

Your reducer func :: Expr -> ExprNF computes the normal form recursively, and there is no need to repeatedly call it in hopes of convergence. 

func :: Expr -> ExprNF
func (Lit n) = ExprNF n []
func (Var s) = ExprNF 0 [s]
func (Plus a b) = case (func a, func b) of
    (ExprNF n vs, ExprNF n' vs') -> ExprNF (n + n') (sort (vs ++ vs'))

We never have to reduce any node in the tree more than once, because we get a normal form right away.

推荐阅读