Haskell Tree construction

Question

문자열을 취하여 이진 트리를 만드는 Haskell 함수를 작성하는 데 도움이 필요합니다. 나를위한 약간의 구멍을 채우고 이것이 왜 나를위한 학습 경험이기 때문에 이유를 기술하기 위해 조금 더 나은 하스켈 경험을 가진 누군가로부터 도움을 필요로합니다.

하스켈 프로젝트의 단일 문자열로 인코딩 된 트리가 있습니다 (예제 **B**DECA). 별표는 다른 문자가 잎을 나타내는 노드를 나타냅니다. 입력에서 읽은 정보로이 데이터 구조를 채우려고합니다. 나는 수학 및 필수 프로그램 사람을 더 해요

data Trie = Leaf Char | Branch Trie Trie

그래서 내가 왼쪽에서 오른쪽으로 분석하여 하위 트리를 정의 할 수 있습니다 관찰했다. 적절한 나무는 *보다 1 문자 더 많이 가질 것입니다. 수학적으로 재귀 구조를 생각할 것입니다.

첫 번째 문자가 *이 아닌 경우 솔루션이 첫 번째 문자입니다. 다른 솔루션은 지점입니다. 여기서 하위 분기는 함수로 다시 입력됩니다. 여기서 왼쪽 분기는 문자의 첫 번째 집합이며 문자는 숫자 *이며 오른쪽 분기는 그 밖의 모든 것입니다.

대부분 왼쪽 및 오른쪽 하위 트리를 정의하는 데 도움이 필요하며이 방법을 정의하는 데 문제가있는 경우 도움이 필요합니다.

Answer 1

!! (이는 어쨌든 0 -indexed입니다)은 보통 no-go입니다. 그것은 매우 "필수적인"일이며, 여기에서와 같이 항상 일정한 지수로 악취가납니다. 즉, 패턴 일치가 실제로 필요합니다. 또한 색인에서 목록 (type String = [Char])을 분리하고 두 부분으로 나누어 조작하는 것은 나쁜 아이디어입니다. 이러한 목록은 연결되어 있고 불변이므로 첫 번째 부분 전체를 복사하게됩니다. 문자열이 비어

• 경우, 실패 다음과 같이

  당신이하고 싶은 방법입니다.

• *으로 시작하는 경우 어떻게 든 왼쪽 하위 트리를 구문 분석하고 한 단계에서 나머지 목록을 가져온 다음 나머지 부분 중 올바른 하나를 구문 분석하여 Branch을 만듭니다.
• 다른 문자 인 경우 Leaf으로 만드십시오.

문자열을 분할 할 위치를 파악하고 실제로 문자열을 분할 한 다음 절반을 구문 분석 할 필요가 없습니다. 당신이 더 이상 할 수 없게 될 때까지 목록을 분석하고, 남은 것이 무엇이든 (또는 내가 올바르게 말할까요?) 다시 파싱 될 수 있습니다.

그래서 : 함수 Trie에 String의 시작을 소비하고 뒤에 구문 분석되지 않은 비트 잎 (그리고 그냥 구문 분석하는 데 실패 할 경우 Nothing을 제공합니다) constructTrie' :: String -> Maybe (Trie, String)을 정의합니다. 이 함수는 재귀 적입니다. 따라서 추가 출력 값을 얻을 수 있습니다. 목록의 나머지 부분을 이동하려면 여분의 배관이 필요합니다. constructTrie 자체는 다음 래퍼로 정의 할 수있다 :

-- Maybe Trie because it's perfectly possible that the String just won't parse 
constructTrie :: String -> Maybe Trie 
constructTrie s = do (t, "") <- constructTrie' s 
        -- patmat failure in a monad calls fail; fail @Maybe _ = Nothing 
        return t 

-- can make this local to constructTrie in a where clause 
-- or leave it exposed in case it's useful 
constructTrie' :: String -> Maybe (Trie, String) 
constructTrie' "" = Nothing -- can't parse something from nothing! 
constructTrie' ('*':leaves) = do (ln, rs) <- constructTrie' leaves 
           -- Parse out left branch and leave the right part 
           -- untouched. Doesn't copy the left half 
           (rn, rest) <- constructTrie' rs 
           -- Parse out the right branch. Since, when parsing 
           -- "**ABC", the recursion will end up with 
           -- constructTrie' "*ABC", we should allow the slop. 
           return (Branch ln rn, rest) 
constructTrie' (x:xs) = return (Leaf x, xs) 

이것은 매우 일반적인 패턴 : 어떤 상태를 해결 통과 별도 배관으로 재귀 함수를 정의하고, 더 좋은 하나에 배치. 나는 명령형 루프가 대개 그들의 상태를 유지하기 위해 변수를 돌연변이시키는 방법에 해당한다고 생각합니다.