懶惰列表的好分區實現？

Question

type 'a lazy_list_t = Cons of 'a * (unit -> 'a lazy_list_t) 

什麼是實現partition函數的最佳/有效方法？

這是我的實現。

let rec filter f (Cons (x, tl_f)) = 
    if f x then Cons (x, fun() -> filter f (tl_f())) 
    else filter f (tl_f()) 

let partition f ll = filter f ll, filter (fun x -> f x |> not) ll 

我認爲它很簡單，但缺點是對於每個元素，f實際上應用了兩次。

有沒有更好的辦法？

Answer 1

我會在這方面努力：

let rec fold_right f ll b = 
    match ll with 
    [] -> b 
    | x :: xs -> f x (fold_right f xs b);; 

let partition f ll = 
    let f_split v (tt, ff) = 
    if f v = true then (v::tt,ff) else (tt,v::ff) in 
    fold_right f_split ll ([], []);; 

，讓您可以寫下一個懶惰fold_right並最終慵懶的分區功能。 例如什麼樣的：

let rec fold_right f (Cons(x, xs)) b = 
    f x (fold_right f (xs()) b);;