函数式内功心法-01: 流程控制神器之callcc浪子回头

本人是一个函数式爱好者，苦于网上资料贫乏以及术语理论性太强久矣。
故本人决定用白话文讲述函数式技术，当然会不那么准确，但是便于理解其基本概念。

在函数式世界里，每个函数语句都要有返回值。

一个函数里面进行各种操作的时候，怎样能够在特定情况下提前返回呢？
当然在面向过程语言里面，比较相似的就是return语句了。
比如下面的例子:

whatsYourName :: String -> String
whatsYourName name =
  (`runCont` id) $ do                      -- 1
    response <- callCC $ \exit -> do       -- 2
      validateName name exit               -- 3
      return $ "Welcome, " ++ name ++ "!"  -- 4
    return response                        -- 5

validateName name exit = do
  when (null name) (exit "You forgot to tell me your name!")

对名称进行验证，验证失败后则直接返回。

这里在函数式是怎么做到的呢？居然直接忽略后面的语句提前结束!

在函数式世界里面，正常情况下是不可能发生的。
除非我们有多通道，正常走正常的通道，特殊走VIP通道。
没说，我们就是可以这么干！

1. 首先我们引入CPS(continuation passing style)的概念。

什么是CPS？CPS就像一场接力比赛。
来看看简单的例子: 1 * 2 + 3 * 4
首先我们计算 1 * 2，然后计算3 * 4, 最后累加.
这里就涉及三次传递过程。
1 * 2 -> 3 * 4 -> a1 + a2 -> ?
每一次结果都往后传递处理，带上自己一直传递下去，这就是CPS风格。
谁来接最后一棒呢？最后一棒有个特殊的名字，叫做终级continuation。

2. 我们再来看前面的问题

假如我们共有五次接力。假设第二次接力可能出现问题。
我们对第二次接力进行验证，如果没有问题，则继续往下接力。
如果有问题，直接找终级ccontinuation最后一棒！
所以问题似乎很简单了。。。

既然思想通了，那么就该开始练习内功心法了！

这里涉及haskell的两个库: transformer以及mtl。
mtl在transformer上对monad transformer做了增强。
mtl上面有个Control.Monad.Cont提供了callcc接口，用于实现VIP通道功能。
底层均由transformer的Control.Monad.Trans.Cont实现

mtl本质上没干啥活，主义功能就是定义了一个MonadCont的接口(即typeclass)。其它的就是实现了底层Cont库的MonadReader跟MonadState接口。
所以，我们主要看transformer库。

1. 首先我们定义传递，这个传递主要由ContT定义

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

这里定义了ContT类型，主要有三个类型变量r, m, a
a是当前的传递值， m是对返回结果r进行隔离的另一层数据结构
整个过程就是对于已有的传递值a，等待一个传递函数a->m r，最终生成结果m r。
对于函数类型来说，输入参数为等待值。这里等待a-> m r传递函数。
通过将自己的传递值a移交给传递函数，完成了传递功能。
这里的ConT仅仅是一种函数类型封装，使用过程中则需要拆解以及再次封装过程。

2. 传递是如何组合的呢?

    m >>= k  = ContT $ \ c -> runContT m (\ x -> runContT (k x) c)

首先m传递\x值后，运行下一棒传递函数runContT (k x) c
k绑定m的返回结果x后生成新的ContT，继续等待参数c传递函数
因此，整个过程比较简单，就是把当前结果\x传递给下一次调用(k x)后, 生成新的ConT继续等待终极传递函数。

3. 那么Cont又是如何构造的呢?

看一个简单的例子:
参见https://en.wikipedia.org/wiki/Continuation-passing_style

pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)

add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)

sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)

pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
  a2 <- pow2_m a
  b2 <- pow2_m b
  anb <- cont (add' a2 b2)
  r <- cont (sqrt' anb)
  return r

两种Cont构造:

instance Monad (ContT r m) where
    return x = ContT ($ x)

cont :: ((a -> r) -> r) -> Cont r a
cont f = ContT (\ c -> Identity (f (runIdentity . c)))

pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)
pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)

通过return构造, 调用$等待传递函数即得Cont Monad
通过cont函数调用，将a -> m r传递函数作为参数调用并进行等待

4. 传递函数如何传递呢?

newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

runCont
    :: Cont r a         -- ^ continuation computation (@Cont@).
    -> (a -> r)         -- ^ the final continuation, which produces
                        -- the final result (often 'id').
    -> r
runCont m k = runIdentity (runContT m (Identity . k))

evalContT :: (Monad m) => ContT r m r -> m r
evalContT m = runContT m return

evalCont :: Cont r r -> r
evalCont m = runIdentity (evalContT m)

主要分为两种，
一种是runCount系列，就是接受一个终极传递函数即可
另一种是evalCont系列，即是将最后传递的值返回

callcc登场

前面的基础知识有了，让我们重新来回顾一下callcc的过程。

whatsYourName :: String -> String
whatsYourName name =
  (`runCont` id) $ do                      -- 1
    response <- callCC $ \exit -> do       -- 2
      validateName name exit               -- 3
      return $ "Welcome, " ++ name ++ "!"  -- 4
    return response                        -- 5

validateName name exit = do
  when (null name) (exit "You forgot to tell me your name!")

先看一下callcc是如何实现的

callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT $ \ c -> runContT (f (\ x -> ContT $ \ _ -> c x)) c

首先通过runCount运行一个callcc Cont, 并使用id作为终极传递函数返回Cont的传递值
callcc调用一个函数，传递VIP通道(a -> ContT r m b)逃逸Continuation作为函数参数
逃逸Continuation接受一个传递值，直接调用终极传递函数后结束传递。
(\ x -> ContT $ \ _ -> c x)
callcc函数里面接受逃逸continuation之后进行CPS传递过程
正常逻辑一直通过monad组合传递下去，特殊通道接受参数直接完成传递链