OCaml: create a tuple list from a list using fold

How to create a tuple list from one single list, like so: [1; 2; 4; 6] -> [(1, 2); (4, 6)]

I want to do it using function List.fold_left since I'm trying to learn that currently but don't know how... Is there a way? Or should I leave it like that?

This is a working code that doesn't use List.fold_left:

let rec create_tuple acc l = match l with
  | [] -> acc
  | x :: y :: l' -> create_tuple (acc @ [(x, y)]) l'
  | _ -> acc

CodePudding user response：

List.fold_left reads elements one by one. There is no direct way to make it read elements two by two.

It really is pointless complication (great for teaching, though), but if you absolutely want to use List.fold_left here, your accumulator needs to somehow record the state of the traversal:

either you have read an even number of elements so far,
or you have read an odd number and then you have to record what was the last element you read, so that, upon reading the following one, you can pair them.

Here is a way to do it. I use an algebraic datatype to represent the state.

(* This is the type that we’ll use for the accumulator;
   the option component is the state of the traversal.
   (None, acc) means that we have read an even number of elements so far;
   (Some x, acc) means that we have read an odd number of elements so far,
   the last of which being x. *)
type 'a accumulator = 'a option * ('a * 'a) list

let folder (state, acc) x =
  match state with
  | None   -> (Some x, acc)
  | Some y -> (None, (y,x)::acc)

let create_pairs l =
  let (_, acc) = List.fold_left folder (None, []) l in
  List.rev acc

Also notice how I avoid the complexity bug that I outlined in a comment: I add elements in reverse order (i.e. at the head of the accumulating list), and at the very end I reverse that list.

CodePudding user response：

@Maëlan's answer is beautiful, but what if we want to get triples rather than pairs? Is there a way we can use List.fold_left to handle this more generically?

let chunks n lst =
  let (_, _, acc) = List.fold_left 
    (fun (counter, chunk, lst') x ->
       if counter = n - 1 then
         (0, [], List.rev (x :: chunk) :: lst')
       else
         (counter   1, x :: chunk, lst'))
    (0, [], [])
    lst 
  in
  List.rev acc

Using this, chunks 2 [1; 2; 4; 6] returns [[1; 2]; [4; 6]]. We can map this to the result you're looking for with a very simple function that takes a list with two elements and creates a tuple with two elements.

chunks 2 [1; 2; 4; 6] |> List.map (fun [x; y] -> (x, y))

And we get:

[(1, 2), (4, 6)]

This could be used to implement a triples function.

let create_triples lst =
  chunks 3 lst |> List.map (fun [x; y; z] -> (x, y, z));;

And now create_triples [1; 2; 3; 4; 5; 6; 7; 8; 9] returns [(1, 2, 3); (4, 5, 6); (7, 8, 9)].