list - F# 拆分列表

Question

我是 F# 和元组的新手，我正在尝试使用递归和匹配将一个列表拆分为三个元组列表。

例如，[1; 2； 3] 会返回:

l1 = [1] 
l2 = [2]
l3 = [3]

或

[1;2;3;4;5;6;7]:

l1 = [1;2;3]
l2 = [4; 5]
l3 = [6; 7]

到目前为止，我的代码开始于

let rec split x =
    match x with
    | _ -> [], [], []

在将元素插入每个列表时，我不确定从哪里开始。

Answer 1

最基本的方法是遍历列表，递归处理其余部分，然后将当前元素附加到三个返回列表之一。您需要在函数中添加一个额外的参数 i 以跟踪您在列表中的位置(然后使用它来确定当前元素的位置)。最基本形式的一般结构是:

let split l =
  let length = List.length l
  let rec loop i l = 
    match l with 
    | [] -> 
        // Empty list just becomes a triple of empty lists
        [], [], []
    | x::xs ->
        // Process the rest of the list recursively. This 
        // gives us three lists containing the values from 'xs'
        let l1, l2, l3 = loop (i + 1) xs
        // Now comes the tricky bit. Here you need to figure out
        // whether 'x' should go into 'l1', 'l2' or 'l3'. 
        // Then you can append it to one of them using something like:
        l1, x::l2, l3
  // Walk over the list, starting with index 'i=0'
  loop 0 l

如何处理棘手的问题？我没有完全符合您要求的解决方案，但以下内容很接近 - 它只是查看 i 是否大于长度的 1/3 或长度的 2/3:

let split l =
  let length = List.length l
  let rec loop i l = 
    match l with 
    | [] -> [], [], []
    | x::xs ->
        let l1, l2, l3 = loop (i + 1) xs
        if i >= length / 3 * 2 then l1, l2, x::l3
        elif i >= length / 3 then l1, x::l2, l3
        else x::l1, l2, l3
  loop 0 l

这将始终创建 length/3 组并将剩余元素放在最后一个列表中:

split [1..3] // [1], [2], [3]
split [1..4] // [1], [2], [3; 4]
split [1..5] // [1], [2], [3; 4; 5]
split [1..6] // [1; 2], [3; 4], [5; 6] 

您应该能够使其适应您需要的行为 - 您需要进行一些繁琐的计算才能准确确定截止点的位置，但这是正确设置 +/-1 的问题!