3

最近、Haskell 99 問題の第 66 回 (ツリーをコンパクトにレイアウト) を解決しようとしています。私は成功しましたが、ここの解決策に混乱しました( http://www.haskell.org/haskellwiki/99_questions/Solutions/66 )。

layout :: Tree a -> Tree (a, Pos)
layout t = t'
  where (l, t', r) = layoutAux x1 1 t
    x1 = maximum l + 1

    layoutAux :: Int -> Int -> Tree a -> ([Int], Tree (a, Pos), [Int])
    layoutAux x y Empty = ([], Empty, [])
    layoutAux x y (Branch a l r) = (ll', Branch (a, (x,y)) l' r', rr')
      where (ll, l', lr) = layoutAux (x-sep) (y+1) l
            (rl, r', rr) = layoutAux (x+sep) (y+1) r
            sep = maximum (0:zipWith (+) lr rl) `div` 2 + 1
            ll' = 0 : overlay (map (+sep) ll) (map (subtract sep) rl)
            rr' = 0 : overlay (map (+sep) rr) (map (subtract sep) lr)

-- overlay xs ys = xs padded out to at least the length of ys
-- using any extra elements of ys
overlay :: [a] -> [a] -> [a]
overlay [] ys = ys
overlay xs [] = xs
overlay (x:xs) (y:ys) = x : overlay xs ys

「x1」と「sep」の計算で無限ループが発生しないのはなぜですか? それらはどのように計算されましたか？

4

1 に答える 1