list - Haskell，来自树的列表列表

Question

我有一个树的数据结构:

数据树 a = NodeT a (树 a) ( 树 a) |空T

我需要创建一个函数，该函数返回一个列表列表，其中列表的每个元素代表树的一个级别。例如，从这里:

          1
         / \
       2     3
      / \   / \
     4   5 6   7     

对此:[[1],[2,3],[4,5,6,7]]

该函数必须具有以下形式:

                     f :: Tree a -> [[a]]

如何使用递归来做到这一点？

任何人？

谢谢

Answer 1

回答

levels :: Tree a -> [[a]]
levels t = levels' t []

levels' :: Tree a -> [[a]] -> [[a]]
levels' EmptyT rest = rest
levels' (NodeT a l r) [] = [a] : levels' l (levels r)
levels' (NodeT a l r) (x : xs) = (a : x) : levels' l (levels' r xs)

levels' 的一个稍微复杂但更懒惰的实现:

levels' EmptyT rest = rest
levels' (NodeT a l r) rest = (a : front) : levels' l (levels' r back)
  where
    (front, back) = case rest of
       [] -> ([], [])
       (x : xs) -> (x, xs)

褶皱的粉丝会注意到这些被构造为 catamorphisms:

cata :: (a -> b -> b -> b) -> b -> Tree a -> b
cata n e = go
  where
    go EmptyT = e
    go (NodeT a l r) = n a (go l) (go r)

levels t = cata br id t []
  where
    br a l r rest = (a : front) : l (r back)
      where
        (front, back) = case rest of
          [] -> ([], [])
          (x : xs) -> (x, xs)

如 chi points out ，这种通用方法与使用 Jakub Daniel 的解决方案并将差异列表作为中间形式的结果之间似乎存在某种联系。这可能看起来像

import Data.Monoid

levels :: Tree a -> [[a]]
levels = map (flip appEndo []) . (cata br [])
  where
    br :: a -> [Endo [a]] -> [Endo [a]] -> [Endo [a]]
    br a l r = Endo (a :) : merge l r

merge :: Monoid a => [a] -> [a] -> [a]
merge [] ys = ys
merge (x : xs) ys = (x <> y) : merge xs ys'
   where
     (y,ys') =
       case ys of
         [] -> (mempty, [])
         p : ps -> (p, ps)

我不完全确定这与更直接的方法相比如何。

讨论

Kostiantyn Rybnikov 的 answer引用冈崎的 Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design ，一篇出色的论文，突出了许多函数式程序员的“盲点”，并提供了很好的论据，使抽象数据类型足够容易使用，不会被遗漏。然而，论文描述的问题比这个问题复杂得多；这里不需要那么多机器。此外，该论文指出，在 ML 中，面向级别的解决方案实际上比基于队列的解决方案略快；我希望在像 Haskell 这样的惰性语言中看到更大的差异。

雅各布丹尼尔的 answer尝试了面向级别的解决方案，但不幸的是存在效率问题。它通过重复将一个列表附加到另一个列表来构建每个级别，并且这些列表的长度可能相同。因此，在最坏的情况下，如果我计算正确，则需要 O(n log n)用 n 处理一棵树元素。

我选择的方法是面向级别的，但通过将每个左子树传递给其右兄弟和表亲的级别来避免连接的痛苦。树的每个节点/叶子都只处理一次。该处理涉及 O(1)工作:该节点/叶子上的模式匹配，如果它是一个节点，则从正确的 sibling 和堂兄弟派生的列表上进行模式匹配。因此总时间为 O(n)用 n 处理一棵树元素。