haskell - 对 Haskell 中的 Do 语句中的箭头感到困惑

Question

我正在努力理解 State monad 并编写了两个简单版本的著名斐波那契来内存函数。带有 let 的那个在体内跑得很慢。带有 <- 的那个跑得非常快。我的问题:为什么？让 <- 以某种方式引起全面评估允许 M.lookup通过 Data.Map去工作？

-- using state monad and let

-- very slow

fibLet :: Int -> State (M.Map Int Integer) Integer
fibLet n = do
   case n of 0 -> return 0
             1 -> return 1
             n -> do 
                  mp <- get
                  if M.member n mp 
                  then return $ fromJust (M.lookup n mp)
                  else do
                       let s1 = evalState (fibLet (n - 1)) mp                        
                       let s2 = evalState (fibLet (n - 2)) mp
                       let s3 = s1+s2
                       modify $ M.insert n s3
                       return s3


fibonacciLet :: Int -> Integer
fibonacciLet n = evalState (fibLet n) M.empty

-- using state monad and <-

-- very fast

fibArrow :: Int -> State (M.Map Int Integer) Integer
fibArrow n = do
    case n of 0 -> return 0
              1 -> return 1
              n -> do
                   mp <- get
                   if M.member n mp
                   then return $ fromJust (M.lookup n mp)
                   else do
                        s1 <-fibArrow (n - 1)
                        s2 <-fibArrow (n - 2)
                        let s3 = s1+s2
                        modify $ M.insert n s3
                        return s3


fibonacciArrow :: Int -> Integer
fibonacciArrow n = evalState (fibArrow n) M.empty

Answer 1

fibLet实际上根本没有使用它的状态!这就是它如此缓慢的原因；它本质上是一种非常复杂的方式来编写经典的 Haskell 斐波那契定义:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

仔细看看这里发生了什么:

-- from earlier: mp <- get
do
   let s1 = evalState (fibLet (n - 1)) mp                        
   let s2 = evalState (fibLet (n - 2)) mp
   let s3 = s1+s2
   modify $ M.insert n s3
   return s3

mp是 Map目前已知的结果。您使用 evalState运行 fibLet (n - 1) ，以 mp 开始其状态.然后你使用 evalState再次运行fibLet (n - 2) ，以 mp 开始其状态再次。这意味着 fibLet (n - 1)和 fibLet (n - 2)不分享任何工作；他们每个人都使用相同的已知结果的起始 map mp ，因此该 map 中尚未包含的任何内容都必须由两个分支计算。
然而实际上比这还要糟糕。查看evalState的类型:

evalState :: State s a -> s -> a

它没有 State在它的返回类型中。这意味着它实际上不是有状态的。它不与任何周围的状态交互；实际上，它启动了一个新的状态线程，将其运行到完成1，之后状态被丢弃。
通过查看 evalState 的类型，您可以很容易地看出这一点。略有不同(但等效):

evalState :: State s a -> (s -> a)

evalState变成 State s a输入一个简单的函数 s -> a .显然，一个普通的旧函数不能改变 do 的隐式状态。阻止它的调用(这就是在类型中明确声明状态的全部意义)。所以这意味着:

evalState (fibLet (n - 1)) :: M.Map Int Integer -> Integer

evalState (fibLet (n - 1))只是一个从映射到整数的普通旧函数。它既不访问也不影响任何类型的状态。
这意味着在 let s1 = evalState (fibLet (n - 1)) mp 之后外部状态do block 仍然完全等于 mp . 没有已保存在我们已计算结果的状态图中。因此，我们不仅没有在两个单独的递归调用之间共享任何工作，而且它们甚至没有在每个调用内部的更深层递归中共享工作!
为了证明这一点，请尝试运行 fibLet使用 runState而不是 evalState ，所以你可以看到最终的 map 是什么:

ghci> runState (fibLet 20) M.empty
(6765,fromList [(20,6765)])
it :: (Integer, M.Map Int Integer)

map 中只有一个条目，作为 do 的最后一步添加阻止在最外层调用 fibLet ，就在它返回之前。
如果你对 fibArrow 做同样的事情你得到这个:

ghci> runState (fibArrow 20) M.empty
(6765,fromList [(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21),(9,34),(10,55),(11,89),(12,144),(13,233),(14,377),(15,610),(16,987),(17,1597),(18,2584),(19,4181),(20,6765)])
it :: (Integer, M.Map Int Integer)

您可以清楚地看到它记住了所有中间结果，而不仅仅是最终结果。
底线:您通常不想使用 evalState (以及类似的函数，如 runState 和 execState )在 State 中运行的函数中单子(monad)。这些函数旨在运行整个有状态计算，因此通常从状态单子(monad)上下文“外部”运行。当你碰巧在一个状态单子(monad)上下文中运行它们时，它们不会与之交互；相反，它们通过普通的参数传递和函数返回接收(并返回，在 runState 和 execState 的情况下)状态，而不是通过 State 提供的隐式状态线程。 .
如果要调用“有状态子计算”(即在返回 State _ _ 的函数内调用 State _ _)，则需要将子计算绑定(bind)为外部计算的一部分。 do 内的箭头语句 block 这样做； let声明没有，它 仅限 为普通表达式命名。这就是为什么你发现自己不得不使用 evalState获得结果并明确提供 mp即使你已经在一个有状态的上下文中，它应该是隐式可用的；这种困惑是在暗示某些事情是不对的。

1 好吧，假设完全需要结果值，它会“运行到完成”。