haskell中的cps

cps全称叫continuation passing style，简要来讲就是告诉函数下一步做什么的递归方式，由于普通递归有栈溢出的问题，而cps都是尾递归(tail recursion)，尾递归则是没有栈溢出问题的，所以haskell推荐都用cps的方式去编写代码。

当然，相对于普通递归方式，cps也有着非常不便于理解的问题。

def fact(n):

    if (n==0):

        return 1

    else:

        return n* fact(n-1)

print fact(400)

这是一段递归求阶乘的python代码。用cps改写就是

def fact_cps(n,ret):

    if (n==0):

        ret(1)

    else:

        fact_cps(n-1, lambda x:ret(n*x))

def ret2(x):

    print x

fact_cps(400,ret2)

这里要注意的是，我们在传参数的时候多了一个ret，而这个ret其实是一个函数，函数的作用就是传入一个值并打印他。在实际运行过程中，其实是这样子的

以fact_cps(3,ret2)求3的阶乘为例，第一步我们是执行fact_cps(3,ret2)，到第五行的地方，我们执行的是fact_cps(2, lambda x:ret2(3*x))，这里的ret即最外层的ret2

fact_cps中的lambda x:ret (3*x)其实是一个函数的简单写法，也就是说这是一个输入x的函数，然后运算ret(3*x)

第二步调用以后，fact_cps的输入值是2以及一个叫做lambda x:ret(3*x)的函数，也就是说ret函数变成了ret(x): print (3*x) 然后到第五行调用fact_cps(1,lambda x:ret(2*x))即fact_cps(1,lambda x:ret2(3*2*x))

第三布调用的就是fact_cps(0,lambda x:ret2(3*2*1*x))，然后到第三行结束，所以总的一个计算其实就是lambda x:ret2(3*2*1*x)然后将最后一次调用的1带入，得到6。

这中间我们可以看到，和普通递归传递的是参数不同，cps调用每一步都产生一个新的函数，传递给下一步调用，这个传递的函数告诉了被递归函数下一步做的是什么。

用haskell写cps更难懂点先写一个简单点的

mysqrt :: Floating a => a -> a

mysqrt a = sqrt a

print (mysqrt 4) :: IO ()

这是一个普通的开根号，用cps写则是

mysqrtCPS :: a -> (a -> r) -> r

mysqrtCPS a k = k (sqrt a)

mysqrtCPS 4 print :: IO ()

这里把print函数传递进了mysqrtCPS并且用print函数调用sqrt a的结果，达到了cps的目的

普通的阶乘是这么写的

fact :: (Num a, Eq a)=>a->a

fact 0=1

fact n=n*(fact (n-1))

print (fact 40)

815915283247897734345611269596115894272000000000

cps方式是这么写的

factCPS :: (Num a, Eq a)=>a->(a->IO ())->IO ()

factCPS 0 ret=ret 1

factCPS n ret=factCPS (n-1) (\x->ret (n*x))

factCPS 40 print :: IO ()

815915283247897734345611269596115894272000000000

对于Fibonacci数列，普通的方法是这么写的

fib :: (Num a,Eq a)=>a->a

fib 0=0

fib 1=1

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

print (fib 30)

832040

CPS方式的Fibonacci数列是这么写的

fibCPS :: (Num a, Eq a)=>a->(a->IO ())->IO ()

fibCPS 0 f=f 0

fibCPS 1 f=f 1

fibCPS n f=fibCPS (n-1) (\f1->fibCPS (n-2) (\f2->f (f1+f2)))

fibCPS 30 print :: IO ()

832040

参考

http://www.haskell.org/haskellwiki/Continuation

http://www.haskell.org/haskellwiki/Tail_recursion

http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style

http://people.csail.mit.edu/meyer/6001/continuations.txt