查找最嵌套的列表

Question

查找最嵌套的列表

listhaskellfunctional-programmingnested-lists

3

我有以下类型：

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])

- aljazfrancic

1

你能举一些例子来让你的问题更清晰吗？ - Lee Duhem

4

或许换个角度思考，以树的高度和/或深度为考量会有所帮助。 - epsilonhalbe

1

我已经添加了一个例子来说明我的意思... - aljazfrancic

@Pajac 无法显示，也许没问题。但为什么是 [1, 2, 3]？为什么不是 1、2 或 3？顺便说一下，这不是由您的值构造函数 Elem 和 List 构造的值。 - Lee Duhem

他的意思是你的例子没有通过类型检查，从技术上讲应该是（List [List [等等等等]]）。 - rafalio

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bheklilr · Accepted Answer

我将以二叉树为例进行说明，它与您的结构非常相似。您需要把它转换成适用于您的数据类型。假设我有一棵二叉树。

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之前删除各种函数（从顶部开始），以便您可以看到每个步骤的样子，这应该有助于您更好地理解算法。