기능적으로 폭 우선 트리를 생성하는 방법. (하스켈로)

Question

내가 "국가는"간단한 래퍼 다음 하스켈 나무 종류, 말해봐있다 - 소요 나는 또한 기능이

data Tree a = Branch (State a) [Tree a] 
      | Leaf (State a) 
      deriving (Eq, Show) 

의 "> 트리 확장 :: 트리에" 리프 노드 을 분기로 확장하거나 분기를 가져 와서 변경되지 않은 상태로 반환합니다. 이 트리 유형은 N 개 (N-ary) 검색 트리를 나타냅니다.

깊이 검색은 낭비입니다. 검색 공간이 분명 무한하기 때문에 모든 트리의 리프 노드에서 확장을 사용하여 검색 공간을 쉽게 확장 할 수 있고 실수로 누락 될 가능성이 있습니다 목표 상태는 거대합니다 ... 따라서 유일한 솔루션은 광범위한 우선 here에 구현되어 있으므로 해결 방법을 찾을 수 있습니다. 내가 생성 원하는 무엇

는하지만, 나무가 해결책을 찾는까지 를 이송됩니다. 목표 상태가 발견 될 때까지 단순히 첫 번째 자식 노드에서 "확장"기능이라고도 불리는이 깊이 우선 수행하는 방법 만 알고 있기 때문에 이것은 문제가됩니다. (이것은 실제로 다른 불편한 목록을 생성하지 않을 것입니다.)

아무도 나에게이 방법 (또는 전체 알고리즘)을 수행하는 방법에 대한 힌트를주지 않거나 괜찮은 복잡성으로 가능한지에 대한 평결을 줄 수 있습니까? ? (또는 이것에 대한 출처는 다소 적다.)

Answer 1

Chris Okasaki의 "Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design"을 보았습니까? Data.Tree 모듈에는 해당 용지에서 채택한 알고리즘을 사용하는 unfoldTreeM_BF이라는 모나드 트리 빌더가 포함되어 있습니다.

은 가정하자 나는 모든 왼쪽 아이들이 부모 문자열 플러스 "에"있는 문자열의 무한 이진 트리를 검색하려면, 오른쪽 : 여기

내가 무슨 일을하는지와 일치를 생각하는 예입니다 아이들은 부모 플러스 "bb"입니다.

import Control.Monad.State 
import Data.Tree 

children :: String -> [String] 
children x = [x ++ "a", x ++ "bb"] 

expand query x = do 
    found <- get 
    if found 
    then return (x, []) 
    else do 
     let (before, after) = break (==query) $ children x 
     if null after 
     then return (x, before) 
     else do 
      put True 
      return (x, before ++ [head after]) 

searchBF query = (evalState $ unfoldTreeM_BF (expand query) []) False 

printSearchBF = drawTree . searchBF 

이 정말 예쁜 아니지만, 그것을 작동 : 나는 나무 폭 우선 검색과 솔루션까지 검색된 트리를 반환 unfoldTreeM_BF를 사용할 수 있습니다. 나는 "AABB"을 검색하면 내가 원하는 정확히 무엇을 얻을 :

| 
+- a 
| | 
| +- aa 
| | | 
| | +- aaa 
| | | 
| | `- aabb 
| | 
| `- abb 
| 
`- bb 
    | 
    +- bba 
    | 
    `- bbbb 

이 당신이 설명하고 물건의 종류 인 경우, 당신의 나무 유형에 대한 적응 어렵지 않을 것이다.

UPDATE : 여기 expand의 DO-무료 버전이 경우에 당신은 이런 종류의 일에있어, 다음과 같습니다. 기존 제어 구조 습관에서 멀리 나를 괴롭히는 위해 camccann하는

expand q x = liftM ((,) x) $ get >>= expandChildren 
    where 
    checkChildren (before, []) = return before 
    checkChildren (before, t:_) = put True >> return (before ++ [t]) 

    expandChildren True = return [] 
    expandChildren _  = checkChildren $ break (==q) $ children x 

(덕분에 나는이 희망 버전은 더 받아 들일 수 있습니다.)

Answer 2

expand 함수가 필요한 이유가 궁금하다. 단순히 전체 트리를 재귀 적으로 생성하고 원하는 검색을 수행하지 않는 이유는 무엇입니까?

expand을 사용하는 경우 검색으로 검사되는 노드를 추적하기 위해 이동 중에 목록을 작성하는 것이 더 간단하거나 두 번째 트리 구조로 보입니다. GHCi에서 그것을 밖으로 시도

data State a = State { getState :: a } deriving (Eq, Show) 

data Tree a = Branch { 
    state :: State a, 
    children :: [Tree a] 
    } deriving (Eq, Show) 

breadth ts = map (getState . state) ts ++ breadth (concatMap children ts) 
search f t = head $ filter f (breadth [t]) 

mkTree n = Branch (State n) (map mkTree [n, 2*n .. n*n]) 

testTree = mkTree 2 

:

여기에 바로 제거 가짜 Leaf 생성자, 발견 한 첫 번째 결과를 반환하는 간단한 예제의 대비를

> search (== 24) testTree 
24 

가 여기에 순진한 심도 우선 검색 :

depth (Branch (State x) ts) = x : (concatMap depth ts) 
dSearch f t = head $ filter f (depth t) 

... 물론 실패합니다. s는 (== 24)으로 검색 할 때 끝나야합니다. 가장 왼쪽 분기가 2s의 끝이없는 계열이기 때문입니다.