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

5

这样做的原因是Haskell 的非严格评估模式，而不是您在大多数语言中看到的严格评估。

在您给出的示例中，maximum l可以计算，因为从函数l返回的layoutAux函数不包含对x1. x1用于t'返回值的部分。

另一个显示类似行为的简单示例如下代码：

hello :: [Int] -> [Int]
hello x = x' where
  x' = hello' l x
  l = length x'
  hello' i lst = map (+i) lst

这不会永远循环，因为要获得列表的长度，您不需要知道它的内容，这就是列表内容依赖l不会导致它永远循环的原因。而如果你有类似的东西maximum而不是长度，那将导致它永远循环，因为maximum需要知道 list 的内容并且内容取决于maximum.

于 2013-09-26T10:06:43.353 回答