Haskell，树中列表的列表

Question

我有一棵树的数据结构：

data Tree a = NodeT a (Tree a) ( Tree a) |空T

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

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

为此：[[1],[2,3],[4,5,6,7]]

函数必须具有以下形式：

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

如何使用递归来实现？

有人吗？

谢谢

Answer 1

您递归地计算层级并始终逐点合并来自两个子树的列表（因此相同深度的所有切片合并在一起）。

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 (++) 作为 merge。

Answer 2

比被接受的解决方案稍微复杂一些，但我认为我的解决方案在内存消耗方面可能更好（有点晚了，所以请自己检查）。

直觉来自 Chris Okasaki "Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design" 的精彩论文。您可以详细了解函数式语言中树的广度优先树遍历的一般直觉。

我做了一些丑陋的添加来添加 "list of lists" 拆分，可能有更好的方法：

module Main where

data Tree a = NodeT a (Tree a) (Tree a) | EmptyT

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

f :: Tree a -> [[a]]
f t = joinBack (f' [(t, True)])

type UpLevel = Bool

f' :: [(Tree a, UpLevel)] -> [(a, UpLevel)]
f' [] = []
f' ((EmptyT, _) : ts) = f' ts
f' ((NodeT a t1 t2, up) : ts) = (a, up) : f' (ts ++ [(t1, up)] ++ [(t2, False)])

joinBack :: [(a, UpLevel)] -> [[a]]
joinBack = go []
  where
    go acc [] = [reverse acc]
    go acc ((x, False) : xs) = go (x : acc) xs
    go acc ((x, True) : xs) = reverse acc : go [] ((x, False):xs)

main :: IO ()
main = do
  let tree = NodeT 1 (NodeT 2 (NodeT 4 EmptyT EmptyT) (NodeT 5 EmptyT EmptyT))
                     (NodeT 3 (NodeT 6 EmptyT EmptyT) (NodeT 7 EmptyT EmptyT))
             :: Tree Int
  print (tail (f tree))

Answer 3

回答

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)

folds 的粉丝会注意到它们的结构是变形的：

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 的 cites Okasaki's Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design，这是一篇优秀的论文，强调了许多函数式程序员的 "blind spots" 并提供了很好的论据，使抽象数据类型足够容易使用，不会被遗漏。但是，论文描述的问题比这个问题复杂得多；这里不需要那么多机器。此外，该论文还指出，面向级别的解决方案实际上比 ML 中基于队列的解决方案要快一些；我希望在像 Haskell.

这样的惰性语言中看到更大的差异

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

我选择的方法是面向级别的，但是通过将每个左子树传递给它的右兄弟和表兄弟的级别来避免串联的痛苦。树的每个 node/leaf 只处理一次。该处理涉及 O(1) 工作：在那个 node/leaf 上进行模式匹配，如果它是一个节点，则在从右兄弟和堂兄弟派生的列表上进行模式匹配。因此，处理具有 n 个元素的树的总时间是 O(n)。

Haskell，树中列表的列表

Haskell, list of lists from a tree

tree

haskell

list

回答

讨论