[haskell] 하스켈에서의 암기?

Edward Kmett의 답변에서 알 수 있듯이 작업 속도를 높이려면 값 비싼 계산을 캐시하고 빠르게 액세스 할 수 있어야합니다.

함수를 비 모노 딕 방식으로 유지하기 위해 무한 게으른 트리를 작성하는 방법은 (이전 게시물에서 볼 수 있듯이) 적절한 색인 방법으로 해당 목표를 달성합니다. 비 모나 딕 함수의 기능을 포기하면 Haskell에서 사용 가능한 표준 연관 컨테이너를 “상태 유사”모나드 (상태 또는 ST와 같은)와 함께 사용할 수 있습니다.

주요 단점은 비 모노 함수를 얻는다는 것인데, 더 이상 구조를 직접 색인화 할 필요가 없으며 표준 연관 컨테이너 구현을 사용할 수 있습니다.

그렇게하려면 먼저 모든 종류의 모나드를 허용하는 함수를 다시 작성해야합니다.

fm :: (Integral a, Monad m) => (a -> m a) -> a -> m a
fm _    0 = return 0
fm recf n = do
   recs <- mapM recf $ div n <$> [2, 3, 4]
   return $ max n (sum recs)

테스트를 위해 Data.Function.fix를 사용하여 메모를 작성하지 않는 함수를 정의 할 수 있지만 조금 더 장황합니다.

noMemoF :: (Integral n) => n -> n
noMemoF = runIdentity . fix fm

그런 다음 State monad를 Data.Map과 함께 사용하여 작업 속도를 높일 수 있습니다.

import qualified Data.Map.Strict as MS

withMemoStMap :: (Integral n) => n -> n
withMemoStMap n = evalState (fm recF n) MS.empty
   where
      recF i = do
         v <- MS.lookup i <$> get
         case v of
            Just v' -> return v'
            Nothing -> do
               v' <- fm recF i
               modify $ MS.insert i v'
               return v'

약간만 변경하면 코드를 Data.HashMap과 함께 작동하도록 조정할 수 있습니다.

import qualified Data.HashMap.Strict as HMS

withMemoStHMap :: (Integral n, Hashable n) => n -> n
withMemoStHMap n = evalState (fm recF n) HMS.empty
   where
      recF i = do
         v <- HMS.lookup i <$> get
         case v of
            Just v' -> return v'
            Nothing -> do
               v' <- fm recF i
               modify $ HMS.insert i v'
               return v'

영구 데이터 구조 대신 ST 모나드와 함께 가변 데이터 구조 (예 : Data.HashTable)를 시도 할 수도 있습니다.

import qualified Data.HashTable.ST.Linear as MHM

withMemoMutMap :: (Integral n, Hashable n) => n -> n
withMemoMutMap n = runST $
   do ht <- MHM.new
      recF ht n
   where
      recF ht i = do
         k <- MHM.lookup ht i
         case k of
            Just k' -> return k'
            Nothing -> do
               k' <- fm (recF ht) i
               MHM.insert ht i k'
               return k'

메모를 사용하지 않는 구현과 비교할 때 이러한 구현을 사용하면 큰 입력의 경우 몇 초 동안 기다리지 않고 마이크로 초 단위로 결과를 얻을 수 있습니다.

Criterion을 벤치 마크로 사용하면 Data.HashMap을 사용한 구현이 실제로 타이밍이 매우 유사한 Data.Map 및 Data.HashTable보다 약간 더 나은 성능 (약 20 %)을 관찰 할 수 있습니다.

벤치 마크 결과가 약간 놀랍습니다. 필자의 초기 느낌은 HashTable이 변경 가능하기 때문에 HashMap 구현을 능가한다는 것입니다. 이 마지막 구현에서 일부 성능 결함이 숨겨져있을 수 있습니다.

답변

dilate :: Int -> [x] -> [x]
dilate n xs = replicate n =<< xs

fs = f0 : zipWith max [1..] (tail $ fs#/2 .+. fs#/3 .+. fs#/4)
  where (.+.) = zipWith (+)
        infixl 6 .+.
        (#/) = flip dilate
        infixl 7 #/

data NatTrie v = NatTrie (NatTrie v) v (NatTrie v)

memo1 arg_to_index index_to_arg f = (\n -> index nats (arg_to_index n))
  where nats = go 0 1
        go i s = NatTrie (go (i+s) s') (f (index_to_arg i)) (go (i+s') s')
          where s' = 2*s
        index (NatTrie l v r) i
          | i <  0    = f (index_to_arg i)
          | i == 0    = v
          | otherwise = case (i-1) `divMod` 2 of
             (i',0) -> index l i'
             (i',1) -> index r i'

memoNat = memo1 id id 

fib = memoNat f
  where f 0 = 0
        f 1 = 1
        f n = fib (n-1) + fib (n-2)

memoInt = memo1 arg_to_index index_to_arg
  where arg_to_index n
         | n < 0     = -2*n
         | otherwise =  2*n + 1
        index_to_arg i = case i `divMod` 2 of
           (n,0) -> -n
           (n,1) ->  n

memoIntInt f = memoInt (\n -> memoInt (f n))