상태가있는 Haskell 재귀 데이터 타입

Question

다음을 계산하는 방법을 찾으려고합니다.

주어진 루트 값은 해당 값의 마지막 문자로 시작하는 모든 값을 찾습니다. 당연히 경로에서 이미 사용 된 요소는 반복 될 수 없습니다.

t1 = ["sour","piss","rune","profit","today","rat"] 

우리가 최대 경로 5.

siP 1 --- 
    |  | 
    |  | 
    pisS 2 profiT 2 
    |  | 
    |  | 
    |  todaY 3 
    | 
    souR 3 --- 
    |  | 
    |  | 
    runE 4 raT 4 
      | 
      | 
      todaY 5 

나는 내가 생각하는 것을 볼 것입니다 : (가장 긴 경로) 씨 "sip"와 단어, 예를 들어 너무

최대 깊이를 찾기 다음과 올바른 트랙에 -하지만 실제로 재귀 적으로 호출하는 방법을 해결할 수 없습니다.

[Node 's' (fromList ["piss","sip"]) 2 [Empty],Node 't' (fromList ["profit","sip"]) 2 [Empty]] 

을하지만 지금은 계속하는 방법을 작동하지 않을 수 있습니다

type Depth = Int 
type History = Set.Set String 
type AllVals = Set.Set String 
type NodeVal = Char 

data Tree a h d = Empty | Node a h d [Tree a h d] deriving (Show, Read, Eq, Ord) 

singleton :: String -> History -> Depth -> Tree NodeVal History Depth 
singleton x parentSet depth = Node (last x) (Set.insert x parentSet) (depth + 1) [Empty] 

makePaths :: AllVals -> Tree NodeVal History Depth -> [Tree NodeVal History Depth] 
makePaths valSet (Node v histSet depth trees) = newPaths 
    where paths = Set.toList $ findPaths valSet v histSet 
      newPaths = fmap (\x -> singleton x histSet depth) paths 

findPaths :: AllVals -> NodeVal -> History -> History 
findPaths valSet v histSet = Set.difference possible histSet 
    where possible = Set.filter (\x -> head x == v) valSet 

그래서 ...

setOfAll = Set.fromList xs 
tree = singleton "sip" (Set.empty) 0 

Node 'p' (fromList ["sip"]) 1 [Empty] 


makePaths setOfAll tree 

준다.

Answer 1

실제로 재귀 적으로 계속해야합니다. 현재 귀하의 코드에서 makePaths은 findPaths을 호출하지만 findPaths도 아니고 makePaths도 makePaths 또는 findPaths을 반복적으로 호출하지 않습니다. 두 가지 이유 때문에 알고리즘의 메커니즘을 보는 것이 약간 어렵습니다. 첫째, 나무에 많은 임시 상태를 주석으로 추가하고 두 번째로 불필요하게 Set을 처리하고 있습니다.

그런 것들을 버리자.

---

트리부터 시작해 보겠습니다. 궁극적으로 노드에 값이있는 n -ary 트리 만 있으면됩니다.

data Tree a = Empty | Node a [Tree a] deriving (Show, Read, Eq, Ord) 

명확하게하기 위해,이 Tree은 동일합니다 당신의 궁극적 인 목표 나무는 우리가 목표로하는거야 String들과 노드에 장식 된 것 하나이기 때문에, 말했다 Tree

type OldTree a h d = Tree (a, h, d) 

makeTree :: String -> [String] -> Tree String 

여기서 첫 번째 문자열은 시드 값이고, 문자열 목록은 가능한 연속성입니다. 문자열은 남아 있고, 트리는 우리가 만든 문자열의 나무입니다. 이 함수는 직접 작성할 수도 있습니다.

makeTree seed vals = Node seed children where 
    children = ... 

아이들은 자신의 서브 트리를 구축하여 반복적으로 진행 : 그것은 반복적으로 우리가 바로 우리의 트리의 루트를 알고 씨앗을 제공한다는 사실을 기반으로 진행된다. 이것은 의 문자열을 새로운 시드로 사용하는 것을 제외하고는 지금까지 실행 한 알고리즘의 정확한 복사본입니다. 이렇게하려면 목록을 "선택한 값"목록으로 분할하는 알고리즘을 원합니다.

selectEach :: [a] -> [(a, [a])] 

같은 비슷해 그 목록 c:extraslst는 다른 순서로, 아마도 것처럼 모두 같은 값을 가진다 (c, extras) 같은 elem (c, extras) (selectEach lst)하는 각 값에 대해. 결과는 세 가지 등으로 구분된다 어디

selectEach :: [a] -> [([a], a, [a])] 

으로, 그러나 조금 다르게이 기능을 쓸거야 그 (before, here, after)이 값 elem (before, here, after) (selectEach lst) 다음 lst == reverse before ++ [here] ++ after 경우. 이것은 우리가 쉽게 우리 나무의 자녀를 생성 할 수 있습니다이 보조 기능

selectEach []  = [] 
selectEach (a:as) = go ([], a, as) where 
    go (before, here, []) = [(before, here, [])] 
    go (before, here, after@(a:as)) = (before, here, after) : go (here:before, a, as) 

> selectEach "foo" 
[("",'f',"oo"),("f",'o',"o"),("of",'o',"")] 

좀 더 쉽게 판명 할 것이다 그러나 우리는 너무 많이 생성 종료됩니다.

makeTree seed vals = Node seed children where 
    children = map (\(before, here, after) -> makeTree here (before ++ after)) 
       (selectEach vals) 

사실 너무 많습니다. 우리가

makeTree "sip" ["sour","piss","rune","profit","today","rat"] 

을 실행한다면 우리는 크기 1957 대신 우리가 원하는 크기 8의 좋은 편리한 나무의 나무를 생산하고있어. 이것은 우리가 지금까지 시드의 마지막 글자가 계속하기 위해 선택된 값의 첫 글자 여야한다는 제약 조건을 없앴기 때문입니다. 우리는 나쁜 나무를 걸러 냄으로써 그 문제를 해결할 것입니다.

goodTree :: String -> Tree String -> Bool 

특히이 제약 조건을 따르는 경우 "양호한"트리를 호출합니다. 시드 값이 주어지면 트리의 루트 노드가 시드의 마지막 글자와 첫 글자가 같은 값을 갖는다면 좋다.

goodTree [] _    = False 
goodTree seed Empty   = False 
goodTree seed (Node "" _) = False 
goodTree seed (Node (h:_) _) = last seed == h 

우리는 단순히이 선정시

makeTree seed vals = Node seed children where 
    children = 
    filter goodTree 
    $ map (\(before, here, after) -> makeTree here (before ++ after)) 
    $ selectEach 
    $ vals 

그리고 지금 우리가 완료에 따라 아이들을 필터링 할 수 있습니다!

> makeTree "sip" ["sour","piss","rune","profit","today","rat"] 
Node "sip" 
    [ Node "piss" [ Node "sour" [ Node "rune" [] 
           , Node "rat" [ Node "today" [] ] 
           ] 
       ] 
    , Node "profit" [ Node "today" [] ] 
    ] 

전체 코드는 다음과 같습니다

selectEach :: [a] -> [([a], a, [a])] 
selectEach []  = [] 
selectEach (a:as) = go ([], a, as) where 
    go (before, here, []) = [(before, here, [])] 
    go (before, here, after@(a:as)) = (before, here, after) : go (here:before, a, as) 

data Tree a = Empty | Node a [Tree a] deriving Show 

goodTree :: Eq a => [a] -> Tree [a] -> Bool 
goodTree [] _    = False 
goodTree seed Empty   = False 
goodTree seed (Node [] _) = False 
goodTree seed (Node (h:_) _) = last seed == h 

makeTree :: Eq a => [a] -> [[a]] -> Tree [a] 
makeTree seed vals = Node seed children where 
    children = 
    filter (goodTree seed) 
    $ map (\(before, here, after) -> makeTree here (before ++ after)) 
    $ selectEach 
    $ vals 

그리고 selectEach이 목록 지퍼이라고 무엇을 makeTree가 Reader 모나드에서 작동하는 방법을 사용하는 방법에 독서 가치가있을 것입니다. 둘 다 내가 여기서 사용했던 방법을 응고시키는 중간 주제입니다.

Answer 2

제쳐두고, 이것이 제가 원래 생각한 접근법이었습니다. 이 목록을 집합으로 사용하고 시드 노드를 각각 x으로 설정 한 xs 목록에 매핑합니다. 그러면 최대 값이 계산됩니다. 결과

data Tree a = Node a [Tree a] deriving (Show, Eq, Read, Ord) 

follows seed hist count vals = foll where 
    foll = map (\x -> (x, Set.insert x hist, count+1)) next 
    next = Set.toList $ Set.filter (\x -> (head x) == (last seed)) 
          $ Set.difference vals hist 

mTree (seed,hist,count) vals = Node (seed,hist,count) children where 
    children = map (\x -> mTree x vals) (follows seed hist count vals) 

makeTree seed vals = mTree (seed, Set.singleton seed, 1) vals 

maxT (Node (_,_,c) []) = c 
maxT (Node (_,_,c) xs) = maximum (c : (map maxT xs)) 

maxTree xs = maximum $ map maxT trees where 
    trees = map (\x -> makeTree x vals) xs 
    vals = Set.fromList xs 

:

*Main> maxTree ["sip","sour","piss","rune","profit","today","rat"] 
5