book
归档: Haskell 
flag
mode_edit

不想把 Haskell 写成 C++ 的 mgt 不是好咸鱼

ST Ref & IO Ref

变量

这个功能可以为我们提供「变量」,它们的功能几乎是完全一样的,但是 ST Ref 可以通过 runST 函数来得到一个纯的值,这点可以在纯函数中实现内部的状态,例:

setRanges :: Int -> [(Int, Int)] -> [Bool]
setRanges _ [] = []
setRanges n xs = elems $ runSTUArray $ do
  res <- newArray (0, n) True
  for_ xs $ \(l, r) ->
    for_ ([l..r]::[Int]) $ \i ->
      writeArray res i False
  return res

这个函数的第一个参数代表线段的长度,第二个参数是一系列区间的列表,返回值是用这些区间覆盖这条线段后的结果。可以注意到,虽然这个函数内部有可变的状态,但是它是一个纯函数。

IO Ref 的用法和 ST Ref 基本一样。

(可变的)全局变量

写记忆化搜索没有全局变量可怎么行呢?那么全局变量究竟该怎么实现呢?我们如果可以搞到一个 IORef a 的全局变量,那么我们就成功了。可是,newIORef 的返回值的类型却是 IO (IORef a) ,我们该怎么办呢?也就说, 我们需要一个 IO a -> a 的函数,实际上就是 unsafePerformIO

mem :: IORef (Map.Map (Int64, Int64, Int64) Int64)
mem = unsafePerformIO $ newIORef Map.empty

循环

单看循环好像并不是很难,我们一下就能写出个 while 来:

while :: (Monad m) => m Bool -> m a -> m ()
while cond_ stat = do
  cond <- cond_
  when cond $ do
    _ <- stat
    while cond_ stat

看上去好像不错!但是如果我们想要 break 掉循环该怎么办呢?实际上用 CPS 那一套操作是可以实现各种奇奇怪怪的控制流的,但是鉴于我目前还没学会,所以我们换一种方法。

Monad Transformer

我们主要使用 MaybeT 来实现可以 break 的循环。Monad Transformer 可以将两个 Monad 组合到一起,假设我们现在有一个返回值类型是 IO (Maybe a) 的东西,我们如果想要在 do block 里处理它其实是不容易的:

main = do
  res <- func
  case res of Nothing -> -- do something
    Just  t -> -- do something

分类讨论这种糟粕是不应该出现的。于是我们可以使用 MaybeT 把两个 Monad 组合起来:

newtype MaybeT (m :: * -> *) a = MaybeT {runMaybeT :: m (Maybe a)}

MaybeT :: m (Maybe a) -> MaybeT m a
runMaybeT :: MaybeT m a -> m (Maybe a)

instance (Monad m) => Monad (MaybeT m) where
  return = lift . return
  x >>= f = MaybeT $ do
    v <- runMaybeT x
      case v of
        Nothing -> return Nothing
        Just y  -> runMaybeT (f y)

instance MonadTrans MaybeT where
    lift m = MaybeT (liftM Just m)

于是我们就可以用 forever 来实现循环,用 mzero 来实现 break

loop :: Monad m => MaybeT m a -> m ()
loop stat = (runMaybeT $ forever stat) >> return ()

这是怎么回事呢?我们首先来考虑 forever 的实现:

forever :: Applicative f => f a -> f b
forever a = a >> forever a

它会先运行 a 然后丢掉结果,再去递归调用自己。但是,如果 a 的结果失败了(mzero)后面的内容就不会被执行了。

于是可以这样写来筛素数:

isPrime :: (Integral a) => a -> Bool
isPrime 2 = True
isPrime x = runST $ do
  rx  <- newSTRef 2
  res <- newSTRef True
  loop $ do
    v <- lift $ readSTRef rx
    when (x `mod` v == 0) $ do
      lift $ writeSTRef res False
      mzero
    lift $ modifySTRef' rx (+ 1)
    when (v * v >= x) mzero
  readSTRef res

其中,lift 可以把一个 IO () 先提升为 IO (Maybe a) ,再包装成 MaybeT IO a 。这样就可以在 MaybeTdo block 里使用 IO action 了。