How can I keep track of two lists in a function (fold) in OCaml?

Question

The goal of my this code is two split one list into two lists based on a simple condition and I'm having trouble doing this in just one function.

Currently, I fold over the list passed in and say if the condition is true, add to list one. Then I fold again and say if the condition is false, add to list two. This is horribly inefficient for larger lists and I don't know how to combine it into one fold.

My working, inefficient code currently looks like this:

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

This works for smaller sets but runs out of resources on larger sets. I tried combining the folds like this:

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 doesn't keep track of list_two and it remains []...how can I can keep track of list_two and list_one in ONE function?

Also, for those unfamiliar with fold - it's a function that iterates over every element in original and accumulates the result to old_list_one (in this example)

Edit: Using a tuple as the accumulator did the trick!

That's not a "crash", it's a compiler error. BTW, there is a function included in the OCaml StdLib that does just this. List.partition. — nlucaroni
Not allowed to use anything except pervasives, thanks for the response though. — John Dough

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2014-03-26T15:35:31

Use a pair of lists as your accumulator parameter. The accumulated value can be anything you like.

Here's a sketch of what it might look like:

let f (a, b) x =
    let a' = <calculate> in
    let b' = <calculate> in
    (a', b')

let (list1, list2) = List.fold_left f ([],[]) original_list

How can I keep track of two lists in a function (fold) in OCaml?

1 Answers