将列表一分为二

Question

我想实现一个函数，该函数以大小n和列表作为输入。此函数将把列表剪切为两个列表，一个大小为n，其余的在另一个列表中。我是这门语言的新手，学习语法很困难。

我面临的主要问题是找到一种方法来表达列表的大小，而不使用任何循环或可变变量。

有人能给我一些建议吗？

Answer 1

让我们从函数的类型签名开始。由于它获取n和一个列表作为参数并返回一对列表，因此您有一个函数split:

val split : int -> 'a list -> 'a list * 'a list

以下是实现此功能的一种方法：

let split n xs =
  let rec splitUtil n xs acc =
    match xs with
    | [] -> List.rev acc, []
    | _ when n = 0 -> List.rev acc, xs
    | x::xs' -> splitUtil (n-1) xs' (x::acc)
  splitUtil n xs []

这个想法是使用累加器acc来保存您遍历过的元素，并将n长期递减。因为元素是以acc为前缀的，所以最终必须反转它才能获得正确的顺序。

该函数有两种基本情况可终止：

• 没有任何元素可以遍历（此时为xs = []）
• 您已经浏览了列表的第一个n元素（此时n减少为0）

以下是split如何计算结果的简短说明：

   split 2 [1; 2; 3] // call the auxiliary function splitUtil
~> splitUtil 2 [1; 2; 3] [] // match the 3rd case of x::xs'
~> splitUtil 1 [2; 3] [1] // match the 3rd case of x::xs'
~> splitUtil 0 [3] [2; 1] // match the 2nd case of n = 0 (base case)
~> List.rev [2; 1], [3] // call List.rev on acc
~> [1; 2], [3]

Answer 2

let split n list =
  let rec not_a_loop xs = function
    | (0, ys) | (_, ([] as ys)) -> (List.rev xs), ys
    | (n, x::ys) -> not_a_loop (x::xs) (n-1, ys)
  not_a_loop [] (n, list)

Answer 3

新的解决方案-splitAt现已内置到List和Array中。请参阅github上2014年前后的提交。我今天在VS.2015 中使用F#时注意到了这一点

现在你可以简单地这样做。。。

let splitList n list = 
    List.splitAt n list

正如你所期望的，签名是…

n: int -> list: 'a list -> 'a list * 'a list

示例用法：

let (firstThree, remainder)  = [1;2;3;4;5] |> (splitList 3)
printfn "firstThree %A" firstThree
printfn "remainder %A" remainder

输出：

firstThree [1; 2; 3]
remainder [4; 5]

Github适用于感兴趣的用户：https://github.com/dsyme/visualfsharp/commit/1fc647986f79d20f58978b3980e2da5a1e9b8a7d

Answer 4

还有一种方法，使用fold:

let biApply f (a, b) = (f a, f b)
let splitAt n list = 
  let splitter ((xs, ys), n') c =
    if n' < n then
      ((c :: xs, ys), n' + 1)
    else
      ((xs, c :: ys), n' + 1)
  List.fold splitter (([], []), 0) list 
  |> fst 
  |> biApply List.rev

这里有一个关于折叠的精彩系列，你可以跟随它来了解更多关于这个主题的信息。