将列表拆分为两个

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)