tail recursion

ML尽管是一门函数式语言,但是在使用的时候要万分注意自己所写的rec函数是否能被编辑器优化成普通的loop。我现在唯一所知的就是tail recursion可以被优化掉。

我刚开始写了这样两个函数,

(* 生成一个长度为length的list,其每个元素是n *)
let rec gen_list length n = 
    match length with
    0 -> []
    |_ -> n::(gen_list (length-1) n);;

(* 对list求和*)    
let rec sum = function
  [] -> 0
  | a::l -> a+(sum l) ;;

运行发现,只要list的长度很大,就会报告“Fatal error: exception Stack_overflow”

let rec gen_list2 length n = 
    let rec append l length n =
        if(length=0) then l else append (n::l) (length-1) n
    in append [] length n;;


let sum2 l =     
        let rec myloop l total=
            match l with
            [] -> total
            | a::other -> myloop other (total+a) in
            myloop l 0;;

规则就是:从rec调用得到值不要再进行任何运算,立刻返回!

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥