F#如何将列表拆分？

Question

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

例如，列表[1; 2; 3]将返回：

[(1, null, null); (2, null, null); (3, null, null)]

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
    | _ -> [], [], []

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

- Alpha

---

我有一些混淆的印象，而且我不完全确定这只是我的问题。[1, 2, 3] 是一个包含单个元素的列表，该元素是一个三元组。[1,2,3,4,5,6,7] 是一个包含单个元素的列表，该元素是一个七元组。同样，l1、l2 和 l3 都是仅包含单个元素的列表，这些元素是各种元组。匹配返回列表的元组。我怀疑您将分号的使用与冒号的使用混淆了。我不确定您是否理解元组的含义。具有不同元数的元组不兼容。 - Bent Tranberg

简单来说，如果你想做的是一个和 List.splitInto 功能相同的函数，那么元组根本不需要参与，现在先忘记它们。你需要将所有逗号替换为分号，这样你就可以得到你想要的实际列表元素，然后从那里开始处理。 - Bent Tranberg

@BitTickler 哦，是的，那是个笔误。我确实是指分号。谢谢。 - Alpha

附带说明：来自命令式语言的人通常通过变异方法来解决这个问题（从计数空列表开始，然后开始填充它们）。这使得他们很难看到在函数式语言中如何完成：构建一个块列表，其中每个块是输入列表的第一个n、第二个n、第三个n等元素。 - BitTickler

修改过的问题仍然似乎存在对列表和元组的混淆。最好的做法可能是将问题恢复为先前的状态（这样评论和答案才有意义），然后根据您的新理解提出一个新的问题。 - phoog

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是否大于长度的三分之一或者二分之一：

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正确的问题！

- Tomas Petricek

Answer 2

在List模块中有一个相关的函数。你可以在F#交互式环境（fsi）中轻松测试它。

let input = [1;2;3];;
let output = List.splitInto 3 input;;

输出;;
val it : int list list = [[1]; [2]; [3]]

因此它返回一个列表的列表。

如果您想手动完成此操作，仍然可以使用其他列表函数（这本身可能是很好的练习）：

let manualSplitInto count list =
    let l = List.length list
    let n = l / count
    let r = l % count
    List.append
        [(List.take (n+r) list)]
        (List.unfold (fun rest ->
                      match rest with
                      | [] -> None
                      | _ ->  let taken = min n (List.length rest)
                              Some (List.take taken rest, List.skip taken rest))
                     (List.skip (n+r) list))

在这里，List.unfold为您完成了迭代（递归）部分。 因此，如果您真的想训练使用递归函数，您最终将编写自己的List.unfold替换或更适合您具体用例的内容。

let pedestrianSplitInto count list =
    let l = List.length list
    let n = l / count
    let r = l % count
    let rec step rest acc =
        match rest with
        | [] -> acc
        | _ ->
            let taken = min n (List.length rest)
            step (List.skip taken rest) ((List.take taken rest) :: acc)
    List.rev (step (List.skip (n+r) list) [List.take (n+r) list])

请注意函数step的实现与manualSplitInto中提供给List.unfold的lambda表达式非常相似。

如果您也不想使用像List.take或List.skip这样的函数，那么您将不得不更低级别地进行元素操作，例如：

let rec splitAtIndex index front rear =
    match index with
    | 0 -> (List.rev front, rear)
    | _ -> splitAtIndex (index - 1) ((List.head rear) :: front) (List.tail rear)
    
let stillLivingOnTreesSplitInto count list =
    let l = List.length list
    let n = l / count
    let r = l % count
    let rec collect result (front,rear) =
        match rear with
        | [] -> (front :: result)
        | _ -> collect (front :: result) (splitAtIndex n [] rear)
    let x = splitAtIndex (n+r) [] list
    collect [] x |> List.rev

- BitTickler

---

对不起，我忘记提到我想要使用递归进行匹配练习，而不是使用已经在F#中实现的函数。 - Alpha

@Alpha，这正是BitTickler在他的答案中所解决的问题。您想要手动实现splitInto或splitAt，并可以使用递归和模式匹配来完成此操作，就像这个答案中一样！ - Martin Freedman

Answer 3

如果您知道它始终是三元组，那么这应该可行。

let xs = [1..7]
let n = List.length xs
let y = List.mapi (fun i x -> (x, 3 * i / n)) xs
List.foldBack (fun (x, i) (a,b,c) -> match i with 0 -> (x::a,b,c) | 1 -> (a,x::b,c) | 2 -> (a,b,x::c)) y (([],[],[]))

- mazin