Difference in GHC versions

I was practicing my Haskell and I came across a weird problem which I was unable to find a solution to on the Internet. I decided to solve this problem:

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

In as many ways I can think of. One way is to perform recursion with memoization where I want to use State monad as a cache. I have GHC 7.10.2 on my Windows 10 and GHC 7.6.2 on my Ubuntu 14.04. This code below compiles (and runs very well) on 7.6.2 and doesn't compile on 7.10.2 giving error wherever I type 'Map', for example:

Not in scope: type constructor or class: 'Map.Map'

Not in scope: '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)

Does anybody know why am I facing this problem? It's very disturbing.

Additional question As you can see I didn't perform exactly recursion with memoization. However leaving one of those lines uncommented can change approach:

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

The problem is that using the second line performs terrible. I don't know where I made a mistake, but I think it should run in linear time with memoization. However with this line my algorithm is clearly exponential (I couldn't even get the answer for 50-th Fib number - that long). What did I do wrong in this case?

UPDATE Thanks to your comments I fixed my code. Obviously there was a problem with mod function (I completely don't know how did this compile on GHC 7.6.2). Also I changed:

import qualified Data.Map as Map

to:

import qualified Data.Map.Strict as Map

and now this code below works as intended:

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)

So now the question comes down to: Why did I need to use Data.Map.Strict, how is it different and why GHC 7.6.2 didn't need it?

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

上一篇: 在产卵和查杀过程中，F＃真的比Erlang快吗？

下一篇: GHC版本的差异