AAFPA/Ch7 - 大久保弘崇

p.139 definition of edgesU

... , v1 <= v2]

p.139 L.7

Wrong: MkGraph starts from an empty array
Correct: mkGraph starts from an array of empty lists

p.139 L.-1 def of adjacent, p.140 L.2 def of edgeIn

" /= Nothing " requires Eq class for weight type.
" Maybe.isJust " avoids this.

p.142 L.6

" a starting node s " is " a starting node start "

p.142- Re-Errata

The word "weight" seems it is Ord or Num class,
indeed they are just labels.
So, Class constraint to b should be removed, as:

Ix a => a -> Graph a b -> [a]

p.142 reduction of depthFirstSearch'

put "=> dfs [2,5,4] [6,3,2,1]"
before "=> dfs [5,4] [6,3,2,1]"

p.144-145

" tsort' " is " tsort "

p.145 def of inDegree

We can use the function edgeIn, so

inDegree g n = length [ () | v <- nodes g, edgeIn g (v,n) ]
 

is suffice.

p.146 expression

Wrong:
Correct:

p.146 L.-2 Errata

This line should be:

vertex themselves. This table points smaller node in the connected subgraph, or itself.

p.147 Errata

Add this:

We call here the root of a vertex as the smallest one found by tracing the table.

Replace 3.(a) as:

if both vertices that constitute this edge have different root, this
edge is added to the solution and the table is updated at larger root by the smaller
root, thus the subgraphs are identified by the root.

In unionFind, table should be updated at xv or yv, not v nor y.

unionFind :: Ord n => (n,n) -> Table n n -> (Bool,Table n n)
unionFind (x,y) t =
  let xv = findRoot t x
      yv = findRoot t y
  in  if xv == yv then (False, t)
      else (True, updTable (if yv <  xv then (xv,yv) else (yv,xv)) t)
 

or using guard and where clause and Maybe,

unionFind :: Ord n => (n,n) -> Table n n -> Maybe (Table n n)
unionFind (x,y) t = case compare xv yv of
  LT -> Just $ updTable (yv,xv) t
  EQ -> Nothing
  GT -> Just $ updTable (xv,yv) t
  where
    xv = findRoot t x
    yv = findRoot t y
findRoot:: Eq n => Table n n -> n -> n
findRoot t x | v == x = v
             | otherwise = findRoot v
  where v = findTable t x
 

p.148

Class constraint and definition of fillPQ are both weird.

fillPQ :: (Ord n, Ord w) =>
          [(n,n,w)] -> PQueue (n,n,w) -> PQueue (n,n,w)
fillPQ es ini = foldr (¥(x,y,w) pq -> enPQ (w,x,y) pq) ini es
 

Indeed, the priority queue is never enqueued after first build, so ordered list is enough.
(Aside from that List is concrete data type but PQ is ADT.)
And there is no need to carry mst around.

kruskal :: (Ix n, Ord w) => Graph n w -> [(w,n,n)]
kruskal g = kruskal' (sort $ map (\(x,y,w)->(w,x,y)) $ edgesU g)
                     (newTable [(x,x) | x<- nodes g])
                     (length (nodes g))
  where
    kruskal' _ _ 1 = []
    kruskal' ((e@(_,x,y)):es) t i = case unionFind (x,y) t of
      Just t' -> e : kruskal' es t' $! i-1
      Nothing ->     kruskal' es t  i
 

The result is now increasing order of weight.

p.149 def of prim

Align 2nd equation of prim'.