小编jer*_*iah的帖子

这是展平二叉搜索树的一种方法.它的问题是当它构建的大函数最终应用于[]时,堆栈会溢出.我想知道是否有一种合理的方法来修复此代码片段而不完全改变它的工作方式.例如,构建一个构建函数树的自定义组合器,然后使用显式堆栈对它们进行评估(因为问题已经是扁平化树),这无济于事.

let flatten_k t =

    let rec f t (k:(list<'a>->list<'a>)->list<'a>) =
        match t with
        | Leaf -> 
            k (fun xs -> xs)

        | Bin (l,x,r) ->
            f l (fun fl -> f r (fun fr -> k (fl << (fun xs -> x::xs) << fr)))

    f t (fun g -> g [])

可能最好考虑一个简化的实例,尽管可能更难以令人信服地展示它的修复(因为它确实几乎没有,但至少它表明函数组合确实溢出了堆栈):

let test_composition () =
   let mutable f = id
   for i=0 to 1000000 do
       f <- id << f // >> works fine for me
   printf "Functions …