-
Notifications
You must be signed in to change notification settings - Fork 0
/
Ring.hs
68 lines (55 loc) · 2.03 KB
/
Ring.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
-- Define a class of mathematical rings
-- See also http://en.wikipedia.org/wiki/Ring_(mathematics)
module Ring where
-- You can optionally include a list of symbols after an import statement
-- to say exactly what you're importing from the other module. This is sometimes
-- useful for documentation, and to avoid name clashes between modules.
import Control.Arrow ( first )
import Data.Maybe ( listToMaybe )
class Ring a where
addId :: a -- additive identity
addInv :: a -> a -- additive inverse
mulId :: a -- multiplicative identity
add :: a -> a -> a -- addition
mul :: a -> a -> a -- multiplication
-- Something is parsable if there is a way to read it in from a string
class Parsable a where
-- | If successful, 'parse' returns the thing parsed along with the
-- "leftover" string, containing all of the input string except what
-- was parsed
parse :: String -> Maybe (a, String)
-- The canonical instance for integers:
instance Ring Integer where
addId = 0
addInv = negate
mulId = 1
add = (+)
mul = (*)
instance Parsable Integer where
parse = listToMaybe . reads
-- Look up these functions online. Think about why this combination works.
-- (It should work for any member of the `Read` class. Like `Integer`.)
-- | A datatype for storing and manipulating ring expressions.
data RingExpr a = Lit a
| AddId
| AddInv (RingExpr a)
| MulId
| Add (RingExpr a) (RingExpr a)
| Mul (RingExpr a) (RingExpr a)
deriving (Show, Eq)
instance Ring (RingExpr a) where
addId = AddId
addInv = AddInv
mulId = MulId
add = Add
mul = Mul
instance Parsable a => Parsable (RingExpr a) where
parse = fmap (first Lit) . parse
-- | Evaluate a 'RingExpr a' using the ring algebra of 'a'.
eval :: Ring a => RingExpr a -> a
eval (Lit a) = a
eval AddId = addId
eval (AddInv x) = addInv (eval x)
eval MulId = mulId
eval (Add x y) = add (eval x) (eval y)
eval (Mul x y) = mul (eval x) (eval y)