초등 중급 하스켈 해시 테이블

Question

간단한 해시 테이블 algorithm을 실험하는 것은 Data.HashMap을 사용하여 저에게 효과가있는 것처럼 보였습니다. 나는 빠른 성능을 가능하게하는 가변적 인 해쉬 테이블 (Data.HashTable.IO 일까?)을 구현하는 방법을 더 잘 이해하기를 희망한다. 나는 완전히 잃어 버렸습니다 ... 예제 here을 수정하려했으나 반환 된 (말장난 의도 된) IO 유형을 통해 자신의 길을 찾을 수 없었습니다 ... 어떤 종류의 워크 스루 또는 참조에 대해 미리 감사드립니다.

예를 들어, 변경 가능한 해시 테이블을 사용하여이 간단한 연습을 구현하는 방법은 무엇입니까?

import qualified Data.HashMap as HM (toList,lookup,insert,empty) 

f list = g list HM.empty where 
    g []  h = HM.toList h 
    g (x:xs) h = case HM.lookup (x-1) h of 
       Just _ -> g xs (HM.insert x (x + 1) h) 
       Nothing -> g xs (HM.insert x x h) 

Answer 1

HM.insert의 유형 서명은

insert :: IOHashTable h k v -> k -> v -> IO()이 서명에서

우리가 insert 삽입 한 요소와 새로운 해시 맵을 반환하지 않는 것을 알 수 있습니다, 그것은 실제로 않는 IO 행동입니다 우리를 위해 삽입, 오래된 해시 맵을 제자리에 돌연변이시키는 것.

마찬가지로, HM.lookup 너무 IO 모나드에 그 결과를 반환합니다

lookup :: IOHashTable h k v -> k -> IO (Maybe v)

그래서 우리는 이러한 기능을 반환 IO 작업을 바인딩 몇 가지 작업을 수행해야합니다. 나는 당신이 이런 것을 원한다고 생각합니다.

f xs = g xs HM.empty 
    where g [] h  = HM.toList h 
      g (x:xs) h = do 
       res <- HM.lookup (x-1) h 
       case res of 
        Nothing -> HM.insert h x x 
        Just _ -> HM.insert h x (x+1) 
       g xs h