하스켈의 무한한지도

Question

나는 몇 가지 코드를 작성했으며 무한한 튜플 목록에서 무한지도를 만들 수있을 것이라고 생각했습니다. 다음의 내용을 따라 뭔가가 있습니다 : Map.fromList [(i,i+1)|i<-[1..]]

물론 Data.Map과 Data.Set은 무한지도와 세트를 각각 지원하지 않습니다. 나는 Data에 대해서 비슷한 질문을했다. 욕심 많은 구현은 fromList이며, 대답 here을 읽은 후에는, 욕심 많고 욕심 많은 구현이 가능하다. 욕심 많은 것들이 더 잘 작동한다는 것이 분명하다. 그러나 실제로는 Map.fromList의 게으른 구현이 작동하지 않는다는 것을 이해하지 못합니다. 키 저장 방법과 관련이 있습니까?

Answer 1

Data.Map은 균형 잡힌 트리로 구현됩니다 (약 2 진수라고 생각합니다). 입력에 대한 예지력없이 무한한 이진 트리를 느리게 생성하고 균형을 맞추기가 어렵습니다! 그러나 MemoTrie 패키지와 같이 무한 무한 시도 (비트 수)를 사용하는 것이 좋습니다.

> let x = trie (\x -> x+1) 
> untrie x 72 
73 
> untrie x 37 
38