recursion - Understanding the performance difference of two tail recursive map functions

Question

From Introduction to Objective Caml by Jason Hickey , we have a tail recursive map function:

let rec rev_accum result = function  
    h::tl -> rev_accum (h :: result) tl
    | [] -> result

let rec rec_map f result = function
    h :: tl -> rec_map  f (f h :: result)   tl 
    | [] -> result 

let map1 f l = rev_accum  [] ( rec_map f [] l )

It will traverse the list twice. Consider this alternative:

let rec rec_map2 f result = function
    h :: tl -> rec_map2  f ( result @[f h]) tl 
    | [] -> result 

let map2 f l = rec_map2 f [] l ; 

Will the second one be faster than the first?

Answer 1

重复添加到列表末尾需要的时间是列表最终长度的二次方。另一种说法是它遍历列表n次，很容易超过两次。所以第二个实现通常会慢得多。第一个实现是线性的，即使它遍历列表两次。

（当然你不知道函数的性能f。）