GHC版本的差异

我正在练习我的Haskell，遇到了一个奇怪的问题，我无法在Internet上找到解决方案。 我决定解决这个问题：

https://www.hackerrank.com/challenges/fibonacci-fp

我能想到的方式有很多种。 一种方法是在memoization中执行递归，我希望使用State monad作为缓存。 我在我的Windows 10上安装了GHC 7.10.2，在我的Ubuntu 14.04上安装了GHC 7.6.2。 下面的代码在7.6.2上编译（并且运行得很好），并且不会在7.10.2上编译，在我输入'Map'的地方给出错误，例如：

不在范围内：类型构造函数或类：'Map.Map'

不在范围内：'Map.lookup'

module Main (
    main
) where

import qualified Data.Map as Map
import Control.Monad.State

type CacheState = Map.Map Int Int
type IOState a = StateT CacheState IO a

modNum :: Int
modNum = 100000007

fibsMod :: [Int]
fibsMod = 0 : 1 : zipWith (x y -> (x + y) mod modNum ) fibsMod (tail fibsMod)

-- | calculate Fibs with memoization in map
memoizedFib :: Int -> IOState Int
memoizedFib n = do
    state <- get
    let x = Map.lookup n state
    case x of
        Just y ->
            return y
        Nothing -> do
            n1 <- memoizedFib (n - 1)
            n2 <- memoizedFib (n - 2)
            let n3 = mod (n1 + n2) modNum
            put (Map.insert n n3 state)
            return n3


query :: [Int] -> IOState ()
query [] = return ()
query (n:ns) = do
    fibNum <- memoizedFib n
    liftIO $ print fibNum
    query ns


main :: IO ()
main = do
    inputdata <- getContents
    let intList = (map (read :: String -> Int) . tail . words) inputdata

    evalIOState $ query intList
    where
        initState :: Int -> Map.Map Int Int
        initState upTo = Map.fromList $ zip [0 .. upTo] $ take upTo fibsMod
        --initState upTo = Map.fromList $ [(0, 0), (1, 1)]

        evalIOState :: IOState a -> IO a
        evalIOState m = evalStateT m (initState 10001)

有人知道我为什么面临这个问题吗？ 这非常令人不安。

额外的问题正如你所看到的，我没有执行与memoization完全递归。 然而，留下其中一条线可以改变方法：

initState upTo = Map.fromList $ zip [0 .. upTo] $ take upTo fibsMod
--initState upTo = Map.fromList $ [(0, 0), (1, 1)]

问题是使用第二行表现糟糕。 我不知道我在哪里犯了一个错误，但我认为它应该与记忆一起在线性时间内运行。 然而，使用这条线我的算法显然是指数型的（我甚至无法得到第50个Fib数的答案 - 那么长）。 在这种情况下我做错了什么？

更新感谢您的意见我修复了我的代码。 很明显， mod函数存在一个问题（我完全不知道如何编译GHC 7.6.2）。 另外我改变了：

import qualified Data.Map as Map

至：

import qualified Data.Map.Strict as Map

现在下面的代码按照预期工作：

module Main (
    main
) where

import qualified Data.Map.Strict as Map
import Control.Monad.State

type CacheState = Map.Map Int Int
type IOState a = StateT CacheState IO a

modNum :: Int
modNum = 100000007

fibsMod :: [Int]
fibsMod = 0 : 1 : zipWith (x y -> (x + y) `mod` modNum) fibsMod (tail fibsMod)

-- | calculate Fibs with memoization in map
memoizedFib :: Int -> IOState Int
memoizedFib n = do
    state <- get
    let x = Map.lookup n state
    case x of
        Just y ->
            return y
        Nothing -> do
            n1 <- memoizedFib (n - 1)
            n2 <- memoizedFib (n - 2)
            state <- get
            let n3 = mod (n1 + n2) modNum
            put (Map.insert n n3 state)
            return n3


query :: [Int] -> IOState ()
query [] = return ()
query (n:ns) = do
    fibNum <- memoizedFib n
    liftIO $ print fibNum
    query ns


main :: IO ()
main = do
    inputdata <- getContents
    let intList = (map (read :: String -> Int) . tail . words) inputdata

    evalIOState $ query intList
    where
        initState :: Int -> Map.Map Int Int
        --initState upTo = Map.fromList $ zip [0 .. upTo] $ take upTo fibsMod
        initState upTo = Map.fromList [(0, 0), (1, 1)]

        evalIOState :: IOState a -> IO a
        evalIOState m = evalStateT m (initState 10001)

所以现在问题归结为：为什么我需要使用Data.Map.Strict，它有什么不同，为什么GHC 7.6.2不需要它？

链接地址: http://www.djcxy.com/p/43189.html

上一篇: Difference in GHC versions

下一篇: An option to make memoization the default behaviour of Haskell