ocaml - 懒惰列表的 `partition` 实现良好吗？

Question

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

实现分区功能的最佳/有效方法是什么？

这是我的实现。

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);;