잎의리스트를 입력으로하는 불변 트리 데이터 구조에서 작동하는 알고리즘을 작성하겠습니다. 나뭇잎에서 위쪽으로 올라가는 오래된 나무의 변화로 새로운 나무를 되 찾을 필요가 있습니다.순수 함수 bottom up tree 알고리즘
내 문제는 작업의 결과로 항상 완전한 새 트리를 반환해야하기 때문에 목록에있는 경우 전체 트리 검사가 전체 트리를 재구성하지 않고 순전히 기능을 수행 할 수 없다는 것입니다. 기존 트리를 변경할 수는 없습니다.
더 적합한 알고리즘을 사용하여 피할 수있는 함수 프로그래밍의 기본적인 문제입니까? 아니면 뭔가 빠졌습니까?
편집 : 만하지 전체 트리를 다시 피하기 위해뿐만 아니라 기능적인 알고리즘은 돌연변이 변종보다 같은 시간 복잡도를 가져야한다.
내가 (틀림없이 매우 긴 ...하지 않은) 지금까지 본 가장 유망한가 Zipper data structure 독서 즐길 수 있습니다 : 그것은 기본적으로 유지 별도의 구조, 노드에서 루트로의 역 경로 및이 개별 구조에 대한 로컬 편집을 수행합니다.
많은 로컬 편집을 할 수 있으며 그 중 대부분은 일정한 시간이 소요되며 트리에 다시 작성합니다 (변경해야하는 유일한 노드 인 루트 경로를 재구성).
지퍼는 standard library in Clojure입니다 (표제 지퍼 - 기능 트리 편집 참조).
그리고 OCaml에서 구현 된 the original paper by Huet이 있습니다.
면책 조항 : 저는 오랫동안 프로그래밍을 해왔지만 몇 주 전에 기능 프로그래밍을 시작했으며 지난 주까지 나무의 기능적 편집 문제를 전혀 들어 본 적이 없었습니다. 내가 모르는 솔루션.
그래도 지퍼가 원하는대로 할 수있는 것처럼 보입니다. O (log n) 이하에 다른 대안이 있다면, 나는 그것들을 듣고 싶습니다.
이것은 함수 프로그래밍 언어에 따라 다릅니다. 예를 들어 함수 프로그래밍 언어 Lazy 인 Haskell의 경우 결과는 마지막 순간에 계산됩니다. 때 그들은 acutally 필요합니다.
예를 들어, 함수가 새 트리를 작성하기 때문에 전체 트리가 처리되어야하지만 실제로는 함수가 다음 함수로 전달되고 필요한 경우에만 실행된다는 가정이 있습니다.
게으른 평가의 좋은 예는 번호 목록에 현재 수의 배수를 제거하여 소수를 생성 하스켈에있는 sieve of erastothenes입니다. 숫자 목록은 무한합니다. here
primes :: [Integer]
primes = sieve [2..]
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
계산 복잡도를 프로그램의 나중 시점으로 옮기는 것이 아니라면 새 트리의 모든 노드에 액세스 할 가능성이 있습니까? –
실제로 함수의 실행을 프로그램의 나중 지점으로 이동합니다.그러나 필요할 때만 새로운 트리를 즉석에서 생성합니다. – Ruben
이 기사는 나무 아래로 내려가는 전체 하위 트리를 제외 할 수있는 톱 다운 알고리즘에 관한 것이므로 오래된 트리의 큰 부분을 재사용 할 수 있기 때문에 이것이 도움이되지는 않는다고 생각합니다. 루트에서 내려 가서 잎이 영향을받을 곳을 모르므로 오래된 하위 트리를 다시 사용할 수 없습니다. –
아니요, 그렇지 않습니다. 전체 트리를 잎으로 이동하여 변경해야하는 부분을 찾은 다음 트리의 변경된 부분 만 다시 만들고 새 트리가 올라갈 때 변경되지 않은 부분을 유지합니다. – Brian
당신 말이 맞습니다. 나는 그것을 더 조심스럽게 읽어야했다. 그러나 그것은 시간 복잡성이 여전히 동일하기 때문에 나를 돕지 않습니다. 그 시점에서 더 정확한 질문을 편집했습니다. –
그게 해결책 인 것 같습니다. 고마워요 :) –
당신은 환영합니다 :) –