我如何在OCaml中跟踪函数(fold)中的两个列表?

Question

我这段代码的目标是基于一个简单的条件将一个列表拆分为两个列表，我在一个函数中遇到了麻烦。

目前，我折叠传入的列表，并说，如果条件为真，添加到列表1。然后我再次折叠，如果条件为假，添加到列表2。对于较大的列表，这是非常低效的，我不知道如何将它合并到一个折叠中。

我的工作，低效的代码目前看起来像这样:

let function test old_list_one original_list =
  let list_one = (fold (fun a elt -> 
      if condition = true then elt::a
        else a) old_list_one original_list) in
  let list_two = (fold (fun a elt -> 
      if condition = false then elt::a
            else a) [] original_list) in
do_something list_one list_two

这适用于较小的集合，但在较大的集合上会耗尽资源。我试着像这样组合这些折叠:

let function test old_list_one = 
  let list_two = [] in
  let list_one = (fold (fun a elt -> 
      if (condition) = true then elt::a
        else elt::list_two) old_list_one original) in
do_something list_one list_two

OCaml不跟踪list_two，它仍然是[]…我怎样才能在一个函数中跟踪list_two和list_one ?

另外，对于那些不熟悉fold的人来说，它是一个遍历original中的每个元素并将结果累加到old_list_one(在本例中)的函数

编辑:使用元组作为累加器是有效的!

Answer 1

使用一对列表作为累加器参数。累积值可以是您喜欢的任何值。

这是它可能的样子的草图:

let f (a, b) x =
    let a' = <calculate> in
    let b' = <calculate> in
    (a', b')
let (list1, list2) = List.fold_left f ([],[]) original_list