函数式语言的不动点技巧应该什么时候以什么方式使用为好？

love_wisdom

函数式语言的不动点技巧应该什么时候以什么方式使用为好？

OwnWaterloo

例如： That About Wraps it Up: Using FIX to Handle Errors Without Exceptions, and Other Programming Tricks

大概是讲这么个事情。。。
1. 把需要递归的函数f写成非递归的形式f'
2. 用fix把非递归的f'再转换成与原始f类似的函数

然而在1到2之间， 可以插入很多步骤， 将f'进行各种转换， 最终在2里面用fix把它再转换成与原始f类似， 但有一些新功能的函数。

1. 
   
2. fun fact i = if i = 0 then 1 else i * fact (i-1) ;
   

复制代码

这是个求阶乘的函数， 它的函数体中直接调用自己。
于是一旦开始调用这个函数， 它就会一直重复不断地调用自己， 直到i为0。

1. 现在先将它写成非递归形式：

1. 
   
2. val fact_ = fn fact => fn i => if i = 0 then 1 else i * fact (i-1) ;
   

复制代码

fact_ 没有直接调用自己， 它调用的只是自己的一个参数。

2. "FIX fact_" 就得到一个与fact类似的函数。


将 fact 写成 fact_ 后， 因为不再直接调用自己， 所以就可以在每一个调用上作一些事情。

比如打印出中间结果：

1. 
   
2. val wrap = fn f => fn f’ => fn p =>
   
3.   let
   
4.     val result = f f’ p
   
5.   in
   
6.     print (Int.toString result); print "\n"; result
   
7.   end ;
   
8. val fact_’ = wrap fact_ ;
   
9. val fact’ = FIX fact_’ ;
   
10. > fact’ 10;
    
11. 1 1 2 6
    
12. 24
    
13. 120
    
14. 720
    
15. 5040
    
16. 40320
    
17. 362880
    
18. 3628800
    
19. val it : int = 3628800
    

复制代码

论文里面还有很多类似的应用， 比如记忆化， 比如将produce/consume拆开让它们交替执行， 等等。。。

love_wisdom

=>是什么意思？

love_wisdom

wrap函数是干什么的？