Pearls/Errata-3 - 大久保弘崇

Chapter 5

p.27 l.14

Wrong:
and A this bound is also a lower bound.
Correct:
and A, this bound is also a lower bound.

p.30, Fig. 5.1, definition of cmp

Wrong:

Correct:

p.31, definition of sortsubs

add ")" at the end of line.

Chapter 6

An assumption should be added
"We assume that every given problem has at least one solution."

If all of ok candidate is not good, solution gives empty list.
But if some extension failed to make any candidate, the "foldr extend" resumes unintentionally.
For example:

solution 100 [1..3] => [] (OK)
solution   1 [1..3] => [[[1]]] (NG)

I'll present my proposal for refinement later.

p.38 partitions

It is not in the Standard Prelude.

partitions :: [a] -> [[[a]]]
partitions [ ] = [ [ ] ] -- redundant
partitions [x] = [ [[x]] ]
partitions (x:xs) = map (\ (p:ps) -> (x:p):ps) pss ++ map ([x]:) pss
  where pss = partitions xs
 

or use foldrn of Chapter 7.

p.39 Definition of modify

It is derived form (6.4) and the definition of extend.

modify x [] = [(10,x,1,0)]
modify x kftes = concatMap inner kftes where
  inner (k,f,t,e) = [(10*k,k*x+f,t,e),(10,x,f*t,e),(10,x,1,f*t+e)]
 

Refinement Proposal

The assumption above is not trivial and therefore the algorithm presented in this chapter is partial.
Here is my assumption:

Let there is an unique empty candidate, call it seed.
And it's value is also unique,

seedvalue = value seed
 

(ok seedvalue) must be True.
Change equation (6.1) as:

candidates = foldr extend [seed]
 

Redefinition of candidate

candidates = map (fork (id, value)) . foldr extend' [seed]
 

Fused version

candidates = foldr expand [(seed,seedvalue)]
 

Final abstract version

solutions = map fst . filter (good . snd) . foldr expand [(seed,seedvalue)]
expand x = filter (ok . snd) . zip . cross (extend x, modify x) . unzip
 

Century problem specific version

seed = []
 

Definition of extend

extend :: Digit -> [Expression] -> [Expression]
extend x es = concatMap (glue x) es
glue :: Digit -> Expression -> [Expression]
glue x [ ] = [ [[[x]]] ] -- seed case
glue x ((xs : xss) : xsss) = [ ((x : xs) : xss) : xsss
                             , ([x] : xs : xss) : xsss
                             , [[x]] : (xs : xss) : xsss ]
 

Assume that

modify x = concatMap (md x)
 

for some function md.
Then, from the definition of extend above and (6.4), we can conclude that:

md x <seedvalue> = [(10,x,1,0)]
md x (k,f,t,e) = [(k*10, k*x+f,t,e), (10,x,f*t,e), (10,x,1,f*t+e)]
 

For unique seedvalue, we can use

Simplified version of expand

expand c x evs = concat (map (filter (ok c . snd) . glue x) evs)
glue x ([], _) = [ ([[[x]]], (10,x,1,0)) ] -- seed is unique, seedvalue matching not needed
glue x ((xs : xss) : xsss,(k,f,t,e)) = <unchanged>
 

Place comment here