Haskell布局树

Question

最近，我尝试解决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”的计算不会导致无限循环？它们是如何计算的？

- realli

Answer 1

这能够运行的原因是Haskell采用了非严格求值模式，而不是大多数语言中看到的严格求值。

在你提供的例子中，可以计算maximum l，因为从layoutAux函数返回的l不包含对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 需要知道列表的内容，并且列表内容取决于 maximum 的结果。

- Ankur

---

非常感谢。我完全可以理解在一个小例子中的非严格评估，但是当尝试阅读长代码时仍然会迷失，更不用说使用它了。那么，这种编码风格是否值得推荐？如果是的话，我应该在哪里了解更多信息？ - realli

我也发现这种对非严格评估的利用有点棘手，特别是当非严格的深度达到一定程度时。但是我认为，也许对于某些类型的算法来说，这可能会带来更好的性能特征。 - Ankur

的确，有时候清晰易懂的代码更好，但有时候“巧妙”的代码会胜出。我应该学习更多以理解这种技巧。 - realli