Generalizing traversal of expressions with changes on specific nodes

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Generalizing traversal of expressions with changes on specific nodes

Antoni Boucher
Hi.
I read the lectures from the CIS194 course (version fall 2014) and I
wanted to have some comments on my solution to the Exercise 7 of the
Homework 5.
Here is the question:

Exercise 7 (Optional) The distribute and squashMulId functions are
quite similar, in that they traverse over the whole expression to make
changes to specific nodes. Generalize this notion, so that the two
functions can concentrate on just the bit that they need to transform.

(You can see the whole homework here:
http://www.seas.upenn.edu/~cis194/hw/05-type-classes.pdf)

Here is my squashMulId function from Exercise 6:

squashMulId :: (Eq a, Ring a) => RingExpr a -> RingExpr a
squashMulId AddId = AddId
squashMulId MulId = MulId
squashMulId (Lit n) = Lit n
squashMulId (AddInv x) = AddInv (squashMulId x)
squashMulId (Add x y) = Add (squashMulId x) (squashMulId y)
squashMulId (Mul x (Lit y))
    | y == mulId = squashMulId x
squashMulId (Mul (Lit x) y)
    | x == mulId = squashMulId y
squashMulId (Mul x y) = Mul (squashMulId x) (squashMulId y)

And here is my solution to Exercise 7:

distribute :: RingExpr a -> RingExpr a
distribute = transform distribute'
    where distribute' (Mul x (Add y z)) = Just $ Add (Mul x y) (Mul x z)
          distribute' (Mul (Add x y) z) = Just $ Add (Mul x z) (Mul y z)
          distribute' _ = Nothing

squashMulId :: (Eq a, Ring a) => RingExpr a -> RingExpr a
squashMulId = transform simplifyMul
    where simplifyMul (Mul x (Lit y))
              | y == mulId = Just $ squashMulId x
          simplifyMul (Mul (Lit x) y)
              | x == mulId = Just $ squashMulId y
          simplifyMul _ = Nothing

transform :: (RingExpr a -> Maybe (RingExpr a)) -> RingExpr a -> RingExpr a
transform f e
    | Just expr <- f e = expr
transform _ AddId = AddId
transform _ MulId = MulId
transform _ e@(Lit n) = e
transform f (AddInv x) = AddInv (transform f x)
transform f (Add x y) = Add (transform f x) (transform f y)
transform f (Mul x y) = Mul (transform f x) (transform f y)

Is there a better way of doing such generalization?

Thanks for your help.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 473 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20141226/aa53a05a/attachment.sig>