Newer
Older
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
# Exercise 1 : Aggregate
## Question 1
- g(f(z, x1), f(f(z, x2), x3))
- g(f(f(z, x1), x2), f(z, x3))
- g(g(f(z, x1), f(z, x2)), f(z, x3))
- g(f(z, x1), g(f(z, x2), f(z, x3)))
## Question 2
Variant 1
This might lead to different results.
Variant 2
This might lead to different results.
Variant 3
This always leads to the same result.
Variant 4
This always leads to the same result.
## Question 3
A property that implies the correctness is:
```
forall xs, ys. g(xs.F, ys.F) == (xs ++ ys).F (split-invariance)
```
where we define
```
xs.F == xs.foldLeft(z)(f)
```
The intuition is the following. Take any computation tree for
`xs.aggregate`. Such a tree has internal nodes labelled by g and segments processed using `foldLeft(z)(f)`. The split-invariance law above says that any internal g-node can be removed by concatenating the segments. By repeating this transformation, we obtain the entire result equals `xs.foldLeft(z)(f)`.
The split-invariance condition uses `foldLeft`. The following two conditions together are a bit simpler and imply split-invariance:
```
forall u. g(u,z) == u (g-right-unit)
forall u, v. g(u, f(v,x)) == f(g(u,v), x) (g-f-assoc)
```
Assume g-right-unit and g-f-assoc. We wish to prove split-invariance. We do so by induction on the length of `ys`. If ys has length zero, then `ys.foldLeft` gives `z`, so by g-right-unit both sides reduce to xs.foldLeft. Let `ys` have length `n>0` and assume by I.H. split-invariance holds for all `ys` of length strictly less than `n`. Let `ys == ys1 :+ y` (that is, y is the last element of `ys`). Then
```
g(xs.F, (ys1 :+ y).F) == (foldLeft definition)
g(xs.F, f(ys1.F, y)) == (by g-f-assoc)
f(g(xs.F, ys1.F), y) == (by I.H.)
f((xs++ys1).F, y) == (foldLeft definition)
((xs++ys1) :+ y).F == (properties of lists)
(xs++(ys1 :+ y)).F
```
## Question 4
```scala
def aggregate[B](z: B)(f: (B, A) => B, g: (B, B) => B): B =
if (this.isEmpty) z
else this.map((x: A) => f(z, x)).reduce(g)
```
## Question 5
```scala
def aggregate(z: B)(f: (B, A) => B, g: (B, B) => B): B = {
def go(s: Splitter[A]): B = {
if (s.remaining <= THRESHOLD)
s.foldLeft(z)(f)
else {
val splitted = s.split
val subs = splitted.map((t: Splitter[A]) => task { go(t) })
subs.map(_.join()).reduce(g)
}
}
go(splitter)
}
```
## Question 6
The version from question 4 may require 2 traversals (one for `map`, one for `reduce`) and does not benefit from the (potentially faster) sequential operator `f`.
# Exercise 2 : Depth
## Question 1
Somewhat counterintuitively, the property doesn't hold. To show this, let's take the following values for *L1*, *L2*, *T*, *c*, and *d*.
```
L1 = 10, L2 = 12, T = 11, c = 1, and d = 1.
```
Using those values, we get that:
```
D(L1) = 10
D(L2) = max(D(6), D(6)) + 1 = 7
```
## Question 2
*Proof sketch*
Define the following function D'(L).
Show that *D(L) ≤ D'(L)* for all *1 ≤ L*.
Then, show that, for any *1 ≤ L1 ≤ L2* we have *D'(L1) ≤ D'(L2)*. This property can be shown by induction on *L2*.
Finally, let *n* be such that *L ≤ 2n < 2L*. We have that:
```
D(L) ≤ D'(L) Proven earlier.
≤ D'(2n) Also proven earlier.
≤ log2(2n) (d + cT) + cT
< log2(2L) (d + cT) + cT
= log2(L) (d + cT) + log2(2) (d + cT) + cT
= log2(L) (d + cT) + d + 2cT
```
Done.