找到最嵌套列表

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) 

然後可以通過應用getDeepest它返回[2, 3]被形象化爲

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

。我建議您從getDeepest中刪除類型簽名，並嘗試在go tree 0（從頂部開始）之前刪除各種函數，以便您可以在每個步驟中看到它的外觀，它應該可以幫助您更好地顯示算法。