AAFPA/Ch6 - 大久保弘崇

p.116 Fig6.2

Selected elements should be emphasized in italics.

p.120 split in qsort''

" if x < pivot " should be " if x <= pivot "

p.122

" msort'' " should be " msort' " (also appears in p.127)
"mergep" is abbreviation of "mergepairs"

p.124 L.6

Wrong: the first list cell
Correct: the deleted list cell

p.125 L.6 - L.8 Errata

The discussion here is corrupted.
Because 2nd argument is dominant in the definition of insert',
so the insert pipeline is not built progressively, but immediately.
For example, lazy evaluation go like :

head (insert 1 (insert 2 (insert 3 [])))
=> head (insert 1 (insert 2 [3]))
=> head (insert 1 [2,3])
=> head [1,2,3]
=> 1

So, the largest space used is O(n) in every situation.

p.125 L.-9 to L.-7 Errata

" qsort' " is " qs "
" split' " is " split "

p.127 L.-8 Errata

In inserting an element, whether it is small or large,
the merge operation always touch the bottom of the heap.
In deleting a smallest element, the merge operation always touch the bottom of the heap, too.
So, there is no "lucky" case, every case is the "worst" case here.

p.133 exercise 6.11

You need to use the alternative version

buildTree = foldl (flip addTree) EmptyBT
 

instead of the original foldr version.