CODEWITHSUNDEEP
haskellrecursionpattern-matchingghci
Doug
Doug

Reputation: 3

Forcing evaluation first in a pattern match?

I would like to re-run a function back on a pattern after that same function has been evaluated on parameters inside a Data constructor being passed to the function. For example

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

Note that a and func a are of the same type. When I try to call something like this, the program gets hung up, and I think what's happening is the pattern is getting indefinitely matched against itself before evaluating the inner (func a) and (func b), which would otherwise match it to a different pattern. I have tried using something like

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

to try and force the evaluation of func a and func b first, but this does not work. Is what I am trying to do even possible?

Thanks.

Upvotes: 0

Views: 148

Answers (1)

luqui
luqui

Reputation: 60463

You do get into a loop where you match Plus over and over, but what do you expect?

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))))

The problem is that you are essentially saying, "to evaluate func on a Plus constructor, evaluate func on a Plus constructor".

What does the rest of func look like? Your approach could, in principle, work if the whole definition were something like:

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

Here if func a and func b eventually reduce to Lit, then the first pattern will match and the call will terminate. But I would hesitate to write a function this way, because how do you know that repeatedly calling func on an argument will eventually converge to Lit? There will probably be a case where it won't.

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.

Upvotes: 3

Related Questions