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

Question

我正在努力理解Statemonad，并编写了著名的斐波那契数列的两个简单版本来记忆该函数。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)不共享任何工作；它们每个都使用已知结果的相同起始映射mp，因此该映射中尚未存在的任何内容都必须由两个分支计算。

但实际上情况比这更糟糕。查看 的类型evalState：

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

State它的返回类型中没有。这意味着它实际上并不是有状态的。它不与任何周围的状态相互作用；实际上，它启动了一个新的状态线程，运行它直到完成¹，之后状态被丢弃。

evalState通过查看稍微不同（但等效）的类型，您可以很容易地看出这一点：

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

evalState将 a 转换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仍然完全等于mp。我们的已计算结果的状态图中没有保存任何内容。因此，我们不仅不会在两个单独的递归调用之间共享任何工作，而且它们甚至不会在每个调用内的更深层次的递归中共享工作！

为了证明这一点，请尝试fibLet使用runState而不是运行evalState，这样您就可以看到最终的地图是什么：

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

映射中只有一个条目，在返回之前添加为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)

您可以清楚地看到它记住了所有中间结果，而不仅仅是最终结果。

底线：您通常不想在 monad中运行的函数内部evalState使用（以及类似的函数，如runState和execState）。这些函数旨在运行整个有状态计算，因此通常从状态单子上下文“外部”运行。当您碰巧在状态 monad 上下文“内部”运行它们时，它们不会与其交互；相反，它们通过普通参数传递和函数返回来接收（并返回，在和 的情况下）状态，而不是通过 提供的隐式状态线程。StaterunStateexecStateState

如果您想调用“有状态子计算”（即在State _ _返回的函数内部调用 a State _ _），那么您需要将子计算绑定为外部计算的一部分。块内的箭头语句do执行此操作；该let语句没有，它只为普通表达式提供名称。这就是为什么你发现自己必须使用evalState来获取结果并显式地提供数据mp，即使你已经处于一个应该隐式可用的有状态上下文中；事情的混乱暗示着有些事情不对劲。

¹好吧，它“运行直到完成”，假设结果值是完全需要的。