使用fold_left从列表创建元组列表

Question

如何从一个列表创建元组列表，如下所示：

[1; 2; 4; 6] -> [(1, 2); (4, 6)]

我想使用函数

List.fold_left

来做到这一点，因为我目前正在尝试学习它，但不知道如何......有办法吗？或者我应该就这样留下吗？

这是一个不使用

List.fold_left

的工作代码：

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

Answer 1

List.fold_left

逐个读取元素。没有直接的方法让它两两读取元素。

这确实是毫无意义的复杂化（不过对于教学来说非常有用），但是如果你绝对想在这里使用

List.fold_left

，你的累加器需要以某种方式记录遍历的状态：

• 到目前为止，您已经阅读了偶数个元素，
• 或者你读了一个奇数，然后你必须记录你读到的最后一个元素是什么，这样，在阅读下一个元素时，你可以将它们配对。

这是一种方法。我使用代数数据类型来表示状态。

(* 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

还要注意我如何避免我在评论中概述的复杂性错误：我以相反的顺序添加元素（即在累积列表的head），并在最后我反转该列表。

Answer 2

@Maëlan 的答案很漂亮，但是如果我们想要得到三元组而不是对呢？有没有一种方法可以使用

List.fold_left

来更通用地处理这个问题？

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

使用它，

chunks 2 [1; 2; 4; 6]

返回

[[1; 2]; [4; 6]]

。我们可以使用一个非常简单的函数将其映射到您正在寻找的结果，该函数接受一个包含两个元素的列表并创建一个包含两个元素的元组。

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

我们得到：

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

这可以用来实现三元组函数。

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

现在

create_triples [1; 2; 3; 4; 5; 6; 7; 8; 9]

返回

[(1, 2, 3); (4, 5, 6); (7, 8, 9)]

。

我们还可以创建一个函数来创建给定长度的“块”的序列。

# let chunks_seq n lst =
    let rec aux acc n' lst () =
      match lst with
      | [] when n <> n' + 1 -> invalid_arg "List can't be broken into equal chunks."
      | [] -> Seq.Cons (List.rev acc, Seq.empty)
      | x::xs when n = n' -> Seq.Cons (List.rev acc, aux [x] 0 xs)
      | x::xs -> aux (x :: acc) (n' + 1) xs ()
    in
    aux [] 0 lst ;;
val chunks_seq : int -> 'a list -> 'a list Seq.t = <fun>
# [1; 2; 3; 4] 
  |> chunks_seq 2 
  |> List.of_seq;;
- : int list list = [[1; 2]; [3; 4]]
# [1; 2; 3; 4; 5; 6] 
  |> chunks_seq 3 
  |> List.of_seq;;
- : int list list = [[1; 2; 3]; [4; 5; 6]]
# [1; 2; 3; 4; 5; 6] 
  |> chunks_seq 3 
  |> Seq.take 1 
  |> List.of_seq;;
- : int list list = [[1; 2; 3]]

Answer 3

我尝试了这个问题（使用 List.fold_left），这是我能想到的最好的：

type 'a node = First of 'a | Second of ('a * 'a)

let ans =
  List.fold_left
    (
      fun a e ->
        match a with
        | [] -> (First e)::a
        | (First f)::tl -> Second(f, e)::tl
        | (Second n)::tl -> (First e)::(Second n)::tl
    )
    []
    [1; 2; 3; 4; 5; 6; ]

let () =
  List.iter
    (
      fun e ->
        match e with
        | First f ->
          print_endline(string_of_int f)
        | Second (f, s) ->
          Printf.printf "(%d, %d)" f s
    )
    (List.rev ans)

只是为了让我的答案都在那里......

type 'a node = One of 'a | Two of ('a * 'a)

let ans =
  (List.map
     (
       fun e ->
         match e with
         | One _ -> failwith "Should only be Two's"
         | Two (f, s) -> (f, s)
     )
     (List.filter
        (
          fun e ->
            match e with
            | One _ -> false
            | Two _ -> true
        )
        (List.rev 
           (List.fold_left
              (
                fun a e ->
                  match a with
                  | [] -> (One e)::[]
                  | (One o)::tl -> (Two (o, e))::tl
                  | (Two t)::tl -> (One e)::(Two t)::tl
              )
              []
              (List.init 10 (fun x -> x + 1))
           )
        )
     )
  )

let () =
  List.iter
    (fun (f, s) -> Printf.printf "(%d, %d) " f s)
    ans