Haskell,树的列表列表

Question

我有一个树的数据结构:

数据树a = NodeT a(树a)(树a)| EmptyT

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

          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 指出的那样,这种一般方法与使用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的回答引用了Okasaki的广度优先编号:算法设计中的小练习的经验教训,这是一篇优秀论文,强调了许多功能性程序员的"盲点",并提供了很好的论据,使抽象数据类型易于使用,他们不会被错过了.然而,论文描述的问题比这个问题要复杂得多; 这里不需要机械.此外,本文还指出面向水平的解决方案实际上比ML中的基于队列的解决方案略快; 我希望看到像Haskell这样的懒惰语言有更大的差异.

Jakub Daniel的回答尝试了一种面向关卡的解决方案,但遗憾的是它存在效率问题.它通过重复将一个列表附加到另一个列表来构建每个级别,并且这些列表可以全部具有相同的长度.因此,在最坏的情况下,如果我正确地计算它,则需要O(n log n)处理具有n元素的树.

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

Answer 2

您递归计算级别，并始终逐点合并两个子树中的列表（因此，同一深度的所有切片将合并在一起）。

f :: Tree a -> [[a]]
f EmptyT = []
f (NodeT a t1 t2) = [a] : merge (f t1) (f t2)

merge :: [[a]] -> [[a]] -> [[a]]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = (x ++ y) : merge xs ys

如果树是完整的（从根到列表的所有路径都具有相同的长度），则可以使用zipWith (++)as merge。