list - 找到最嵌套的列表

Question

我有以下类型:

data NestedList a = Elem a | List [NestedList a]

我正在尝试编写一个函数来返回给定列表中嵌套最多的列表，但我不知道从哪里开始。任何帮助表示赞赏!

例子:

函数的输入是这样的:

(List [List [List [List [Elem 1, Elem 2, Elem 3], Elem 5, Elem 6], List [Elem 5, Elem 6]], List [Elem 5, Elem 6]])

函数的期望输出:

(List [Elem 1, Elem 2, Elem 3])

Answer 1

我将举一个使用二叉树的示例，它与您的结构非常相似。您将练习将其转换为适用于您的数据类型。

假设我有一个二叉树

data Tree a
    = Leaf a
    | Node (Tree a) (Tree a)
    deriving (Eq, Show)

我想找到具有最大深度的值(可以有多个!)。我将如何解决这个问题是递归地遍历每个分支，边走边记录深度，然后返回底部的值及其深度。

首先，我将定义我的函数结构

import Data.List (sortBy, groupBy)
import Data.Ord (comparing)
import Data.Function (on)


getDeepest :: Tree a -> [a]
getDeepest tree
    = map fst                        -- Strip the depth from the values
    . head                           -- Get just the ones with the largest depth
    . groupBy ((==) `on` snd)        -- Group by the depth
    . sortBy (flip (comparing snd))  -- Reverse sort by the depth (largest first)
    $ go tree 0                      -- Find all the "bottom" nodes
    where
        go :: Tree a -> Int -> [(a, Int)]
        go (Leaf a)   n = undefined
        go (Node l r) n = undefined

这是您将在 Haskell 中看到的一种常见的递归格式。我有一个本地辅助函数，它带有一个我想初始化为特定值的附加值，在本例中为深度 0。为了以良好的格式获得输出，我已经包含了我知道我想要的逻辑。 flip (comparing snd) 将进行反向排序，因此最大深度将排在第一位。然后我们按深度分组，提取第一组，然后从值中去除深度。

现在我们只需要定义go 做什么。我们知道，当我们触底时，我们希望将值添加到我们找到的深度的累加器中，所以

go (Leaf a)   n = [(a, n)]

这种情况很简单，我们只需根据值和深度创建一个元组并将其包装为一个列表。对于另一种情况，我们想向下遍历每个分支，找到最深的元素，并从两个分支中返回最深的元素

go (Node l r) n = go l (n + 1) ++ go r (n + 1)

这是递归发生的地方。虽然这肯定不是最有效的算法(Haskell 列表对此不是很好，但为了简单起见我们将使用它们)，但它仍然非常简单。我们所做的就是沿着每一侧向下，将深度增加 1。所以整个算法在一起:

getDeepest :: Tree a -> [a]
getDeepest tree
    = map fst                        -- Strip the depth from the values
    . head                           -- Get just the ones with the largest depth
    . groupBy ((==) `on` snd)        -- Group by the depth
    . sortBy (flip (comparing snd))  -- Reverse sort by the depth (largest first)
    $ go tree 0                      -- Find all the "bottom" nodes
    where
        go :: Tree a -> Int -> [(a, Int)]
        go (Leaf a)   n = [(a, n)]
        go (Node l r) n = go l (n + 1) ++ go r (n + 1)

---

举个例子:

myTree :: Tree Int
myTree =
    Node
        (Node
            (Leaf 1)
            (Node
                (Leaf 2)
                (Leaf 3)))
        (Leaf 4)

可以想象为

                Node
               /    \
            Node    Leaf 4
           /    \
       Leaf 1    Node
                /    \
            Leaf 2   Leaf 3

然后通过对它应用 getDeepest 返回 [2, 3]。我鼓励您从 getDeepest 中删除类型签名并尝试删除 go tree 0 之前的各种函数(从顶部开始)，这样您就可以看到它的样子每一步，它都应该帮助您更好地可视化算法。