把 Haskell 写出 C++ 的感觉

不想把 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 。这样就可以在 MaybeT 的 do block 里使用 IO action 了。

ST Ref & IO Ref

变量

（可变的）全局变量

循环

Monad Transformer

`ST Ref` & `IO Ref`