나는 다음과 같은 유형이 가장 하위 목록

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 

을 정의 할 수 있습니다. 특정 값,이 경우 깊이를 0 초기화 할 추가 값을 운반하는 로컬 도우미 함수가 있습니다. 좋은 형식으로 출력물을 얻기 위해 내가 원하는 논리를 이미 포함했습니다. flip (comparing snd)은 역 정렬을 수행하므로 가장 큰 깊이가 먼저옵니다. 그런 다음 깊이별로 그룹화하고 첫 번째 그룹을 추출한 다음 값에서 깊이를 제거합니다.

이제 go을 정의해야합니다. 우리는 우리가 바닥을 쳤을 때, 우리는 우리가 발견 깊이와 우리의 축적에 값을 추가 할 것을 알고, 그래서

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

경우는 아주 쉽게, 우리는 가치와 깊이에서 튜플을 목록으로 포장하십시오. 다른 경우에, 우리는, 각 지점을 통과 깊은 요소를 발견하고 두 가지

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

재귀가 발생하는 곳입니다에서 가장 깊은을 반환합니다. 이것이 확실히 가장 효율적인 알고리즘은 아니지만 (하스켈리스트는 위와 같이 훌륭하지 않지만 간단하게하기 위해 사용합니다), 꽤 간단합니다. 우리가하는 일은 양쪽을 내려 가서 깊이를 늘리는 것입니다. 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) 

그 다음은 [2, 3]을 반환에 getDeepest을 적용하여

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

으로 시각화 할 수있다. getDeepest에서 형식 서명을 삭제하고 go tree 0 (위에서 시작) 전에 다양한 함수를 삭제하여 각 단계에서 어떻게 보이는지 알 수 있도록 알고리즘을 조금 더 시각화하는 데 도움이됩니다.