Haskellにおけるメモ化再帰の実装

combination.hs

import qualified Data.Map as Map

type Memo = Map.Map (Int,Int) Int

combination :: Memo -> Int -> Int -> (Int, Memo)
combination memo n r
  | r == 0    = (1, memo)
  | n == r    = (1, memo)
  | otherwise =
      case Map.lookup (n,r) memo of
        Just x  -> (x, memo)
        Nothing -> (nx, nmemo)
      where
        (x1, memo')  = combination memo  (n-1) r
        (x2, memo'') = combination memo' (n-1) (r-1)
        nx = (x1 + x2) `mod` _mod
        nmemo = Map.insert (n, r) nx memo''

_mod = 1000000007