3 // Question 1: Expressions.
4 sealed abstract class Expr
5 case class Number(n
: Int
) extends Expr
6 case class Sum(e1
: Expr
, e2
: Expr
) extends Expr
7 case class Product(e1
: Expr
, e2
: Expr
) extends Expr
9 def eval(e
: Expr
): Int
= e
match {
11 case Sum(e1
, e2
) => eval(e1
) + eval(e2
)
12 case Product(e1
, e2
) => eval(e1
) * eval(e2
)
15 def showFromProduct(e
: Expr
) : String
= e
match {
16 case Sum(e1
, e2
) => s
"(${show(e1)} + ${show(e2)})"
20 def show(e
: Expr
): String
= e
match {
21 case Number(n
) => n
.toString()
22 case Sum(e1
, e2
) => s
"${show(e1)} + ${show(e2)}"
23 case Product(e1
, e2
) => s
"${showFromProduct(e1)} * ${showFromProduct(e2)}"
27 sealed abstract class BinaryTree
28 case class Leaf(value
: Int
) extends BinaryTree
29 case class Node(left
: BinaryTree
, right
: BinaryTree
) extends BinaryTree
31 def sum(tree
: BinaryTree
): Int
= tree
match {
33 case Node(l
, r
) => sum(l
) + sum(r
)
36 def min(a
: Int
, b
: Int
): Int
= if (a
< b
) a
else b
37 def minimum(tree
: BinaryTree
): Int
= tree
match {
39 case Node(l
, r
) => min(minimum(l
), minimum(r
))
42 // Question 3: Lists functions.
43 def last
[T
](l
: List
[T
]): T
= l
match {
44 case Nil
=> throw new Exception("empty list")
46 case x
:: xs
=> last(xs
)
48 def init
[T
](l
: List
[T
]): List
[T
] = l
match {
51 case x
:: xs
=> x
:: init(xs
)
53 def concat
[T
](l1
: List
[T
])(l2
: List
[T
]): List
[T
] = l1
match {
55 case x
:: xs
=> x
:: concat(xs
)(l2
)
57 def reverse
[T
](l
: List
[T
]): List
[T
] = l
match {
59 case x
:: xs
=> concat(reverse(xs
))(List(x
))
61 def take
[T
](l
: List
[T
])(n
: Int
): List
[T
] = l
match {
63 case _
if n
== 0 => Nil
64 case x
:: xs
=> x
:: take(xs
)(n
- 1)
66 def drop
[T
](l
: List
[T
])(n
: Int
): List
[T
] = l
match {
68 case xs
if n
== 0 => xs
69 case x
:: xs
=> drop(xs
)(n
- 1)
71 def apply
[T
](l
: List
[T
])(n
: Int
): T
= l
match {
72 case Nil
=> throw new Exception("out of bounds")
73 case x
:: xs
=> if (n
== 0) x
else apply(xs
)(n
- 1)
76 // Question 4: Predicates on lists.
77 def any
[T
](l
: List
[T
])(p
: T
=> Boolean
): Boolean
= l
match {
79 case x
:: xs
=> if (p(x
)) true else any(xs
)(p
)
81 def every
[T
](l
: List
[T
])(p
: T
=> Boolean
): Boolean
= l
match {
83 case x
:: xs
=> if (p(x
)) every(xs
)(p
) else false
86 def main(args
: Array
[String
]) = {
87 println("Assignment 4")
88 println("Question 1: Expressions")
90 val expr0
= Sum(Product(Number(2), Number(3)), Number(4))
91 println(s
"Expr0: ${show(expr0)}")
92 assert(eval(expr0
) == 10)
94 val expr1
= Product(Number(4), Number(12))
95 println(s
"Expr1: ${show(expr1)}")
96 assert(eval(expr1
) == 48)
98 val expr2
= Product(Sum(Number(2), Number(3)), Number(4))
99 println(s
"Expr2: ${show(expr2)}")
100 assert(eval(expr2
) == 20)
102 val expr3
= Product(Number(2), Sum(Number(3), Number(4)))
103 println(s
"Expr3: ${show(expr3)}")
104 assert(eval(expr3
) == 14)
108 println("Question 2: Tree")
109 val t
= Node(Node(Leaf(4), Leaf(8)), Leaf(2))
110 println(s
"minimum($t): ${minimum(t)}")
111 assert(minimum(t
) == 2)
112 val t2
= Node(Leaf(8), Node(Leaf(2), Leaf(1)))
113 println(s
"minimum($t2): ${minimum(t2)}")
114 assert(minimum(t2
) == 1)
118 println("Question 3: Lists functions")
120 val l1
= List(2, 3, 1, 4, 2, 9)
122 val l3
: List
[Int
] = Nil
124 println(s
"last($l1): ${last(l1)}")
125 println(s
"last($l2): ${last(l2)}")
127 println(s
"init($l1): ${init(l1)}")
128 println(s
"init($l2): ${init(l2)}")
129 println(s
"init($l3): ${init(l3)}")
131 println(s
"concat(concat($l1)($l2))($l3): ${concat(concat(l1)(l2))(l3)}")
133 println(s
"reverse($l1): ${reverse(l1)}")
134 println(s
"reverse($l2): ${reverse(l2)}")
135 println(s
"reverse($l3): ${reverse(l3)}")
137 println(s
"take($l1)(3): ${take(l1)(3)}")
138 println(s
"take($l1)(6): ${take(l1)(6)}")
139 println(s
"take($l1)(10): ${take(l1)(10)}")
141 println(s
"drop($l1)(3): ${drop(l1)(3)}")
142 println(s
"drop($l1)(6): ${drop(l1)(6)}")
143 println(s
"drop($l1)(10): ${drop(l1)(10)}")
145 println(s
"apply($l1)(0): ${apply(l1)(0)}")
146 println(s
"apply($l1)(3): ${apply(l1)(3)}")
147 println(s
"apply($l1)(5): ${apply(l1)(5)}")
151 println("Question 4: Predicates on lists")
152 println(s
"any($l1)(_ == 4): ${any(l1)(_ == 4)}")
153 println(s
"any($l1)(_ == 13): ${any(l1)(_ == 13)}")
155 println(s
"every($l1)(_ < 4): ${every(l1)(_ < 4)}")
156 println(s
"every($l1)(_ < 13): ${every(l1)(_ < 13)}")