1
\$\begingroup\$

This is a calculator that only sums numbers:

module Data.Calculator where

data Expr = Plus Expr Expr | Value Int

evaluate :: Expr -> Int
evaluate (Value a) = a
evaluate (Plus (Value a) (Value b)) = a + b
evaluate (Plus (Plus left right) (Value b)) = (evaluate left) + (evaluate right) + b
evaluate (Plus (Value a) (Plus left right)) = a + (evaluate left) + (evaluate right)
evaluate (Plus a@(Plus left right) b@(Plus left' right')) = (evaluate a) + (evaluate b)

The evaluate function seems way to verbose. How do I make this better?

\$\endgroup\$
2
  • \$\begingroup\$ Hint: There are two cases. One for Value Int and one for Plus Expr Expr. You don't need any more. \$\endgroup\$ – Dair Sep 10 '18 at 1:55
  • \$\begingroup\$ Using the catamorphism package, evaluate = expr (+) id. \$\endgroup\$ – Gurkenglas Sep 11 '18 at 17:35
2
\$\begingroup\$

As a general rule, when you are trying to define a recursive function that operates on a data type like this:

data Expr = Plus Expr Expr | Value Int

you want to first try to define your function using one pattern per constructor: one pattern for Plus and another pattern for Value. For some functions, you may find that this isn't sufficient, and then you will have to add additional patterns, but you'll be surprised how many useful functions can be written using this "one pattern per constructor" rule.

So, you want a pattern that can match all Value x expressions, and you already have that:

evaluate (Value a) = a

If you want a second pattern that can match ALL Plus e1 e2 expressions, then you can't write something like this:

evaluate (Plus (Value a) (Value b)) = ...

because that will only match some Plus expressions (namely those that are adding two Value expressions). If you want to match them all, you need to start with:

evaluate (Plus left right) = ...

Now, on the right-hand side, left and right are expressions, and the only thing we can do with them is evaluate them to integers, and then it becomes pretty obvious that you want to write:

evaluate (Plus left right) = evaluate left + evaluate right

You basically already figured this out, but you did it inside special cases like the pattern Plus (Plus left right) (Value b) instead of realizing that you could do it in the general Plus left right case.

And that's it! The full definition is:

evaluate :: Expr -> Int
evaluate (Value a) = a
evaluate (Plus left right) = evaluate left + evaluate right

and you'll find it works perfectly on all expressions. For more complicated expressions, the recursion automatically breaks it down:

evaluate (Plus (Value 1) (Plus (Value 2) (Value 3))
-- apply second pattern w/ left=(Value 1) and right=(Plus (Value 2) (Value 3))
=== evaluate (Value 1) + evaluate (Plus (Value 2) (Value 3))
-- apply first pattern w/ a=1
=== 1 + evaluate (Plus (Value 2) (Value 3))
-- apply second pattern w/ left=(Value 2) and right=(Value 3)
=== 1 + (evaluate (Value 2) + evaluate (Value 3))
-- apply first pattern w/ a=2
=== 1 + (2 + evaluate (Value 3))
-- apply first pattern w/ a=3
=== 1 + (2 + 3)
=== 6
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.