Haskell Data.Tree에서 노드의 경로를 찾는 방법

Question

Haskell의 한 트리 (Data.Tree으로 표시)를 사용하면 노드 경로를 어떻게 찾을 수 있습니까?

예컨대 보이는 트리를 형성

는

import Data.Tree 

tree = Node 1 [Node 2 [Node 3 []], Node 4 []] 

같은 :

1 
| 
+- 2 
| | 
| `- 3 
| 
`- 4 

어떻게 함수를 만들 수 pathToNode 있도록 :

내 특정 경우

pathToNode 0 tree => [] 
pathToNode 1 tree => [1] 
pathToNode 2 tree => [1, 2] 
pathToNode 3 tree => [1, 2, 3] 
pathToNode 4 tree => [1, 4] 

, 주어진 값은 나타납니다 트리에서 한 번이므로 경로를 반환하는 솔루션을 사용할 수 있습니다.

pathToNode :: (Eq a) => a -> Tree a -> [a] 
pathToNode x (Node y ys) | x == y = [x] 
         | otherwise = case concatMap (pathToNode x) ys of 
             [] -> [] 
             path -> y:path 

가이 글을 쓰는 좀 더 간결한 방법이 있나요 :

지금까지 내 가장 좋은 대답이 무엇입니까? 내 트래버스 로직 작성을 피하기 위해 Data.Foldable 또는 Data.Traversable을 활용할 수 있습니까?

Answer 1

디폴트 값 Traversable 및 Foldable 인스턴스는 경로를 유지하기에 충분한 문맥 정보를 제공하지 않기 때문에 (예 : State 모나드에서 트래버스 할 때) 여기서 사용할 수 없습니다. 둘 다 어떤 순서로 트리의 각 요소를 한 번 방문하기 때문에 이전에 방문한 값이 현재 노드의 부모 또는 형제 노드에 속하는지 여부를 알 수 없습니다.

pathsToNode :: Eq a => a -> Tree a -> [[a]] 
pathsToNode x (Node y ns) = [[x] | x == y] ++ map (y:) (pathsToNode x =<< ns) 

그것은 x의 모든 복사본에 대한 경로를 나열하지만 만약 당신이 원하는 당신은 언제나 느리게 처음 발견 경로를 취할 수 있습니다

나는 다음과 같은 기능이 충분히 간결 생각합니다.

Answer 2

catamorphism이라고하는 접이식 개념이 일반화되어 있습니다. fold가 명시적인 재귀없이리스트를 "소비"하는 것과 같은 방식으로, catamorphism은 명시 적 재귀없이 나뭇잎에서 시작하여 상향식으로 트리 또는 다른 데이터 유형을 "소비"하게합니다. 규칙적인 폴드와는 달리, 트리의 구조를 인식합니다.

cata 기능은 recursion-schemes 패키지 Data.Functor.Foldable (Data.Foldable 아님) 모듈에 있습니다. 불행하게도,이 같은 Data.Tree 작동하지 않습니다, 당신은 간접적으로, 두 단계 방식으로 상응하는 데이터 유형을 정의해야합니다 : cata를 사용

{-# LANGUAGE DeriveFunctor #-} 

import Data.Functor.Foldable 

data Node a b = Node a [b] deriving (Functor,Eq) 

type Tree a = Fix (Node a) 

tree :: Tree Int 
tree = Fix (Node 1 [ Fix (Node 2 [ Fix (Node 3 []) ]), 
        Fix (Node 4 []) ]) 

, 우리는 모든 경로의 목록을 구성 할 수 있습니다 트리의 모든 값. 명시 적 재귀의 부족주의 :

paths :: Tree a -> [(a,[a])] 
paths = cata algebra 
    where 
    algebra :: Node a [(a,[a])] -> [(a,[a])] 
    algebra (Node a as) = (a,[a]) : map (\(i,is)->(i,a:is)) (concat as) 

그리고 그 함수에서, 우리가 정의 할 수 pathToNode :

pathToNode :: (Eq a) => a -> Tree a -> [a] 
pathToNode a = snd . head . filter ((==a).fst) . paths 

이 솔루션은 내가 두려워 더 간결 아니라 catamorphims이 가지고있는 유용한 도구입니다 너의 벨트에.