Вырезать список по индексу n в F#

Question

Попытка написать рекурсивную функцию, которая будет сокращать список по n. Затем верните 2 списка. Так что, если я пройду

cut(2, [5;10;4;2;7]);;
  val it : int list * int list = ([5; 10], [4; 2; 7])

Я хотел бы получить что-то подобное.

let rec cut (n, xs) = 
        match n, xs with 
        | 0, xt -> (n, xs)
        | n, x::xt -> cut(n, xt), xs;;

Пожалуйста помоги.

Answer 1

Я приведу объяснение рекурсивной функции @MisterMetaphors.

Функция cut не является рекурсивной, но aux есть, она работает путем обратного отсчета от n и удаления элементов из заголовка списка, переданного в cut.

Скажем, вы называете вырезать, как это cut 2 [ 3; 4; 5; 7; 8 ], aux - это функция сопоставления с шаблоном, принимающая три аргумента: n, раздел 1, раздел 2. Раздел 1 начинается с пустого списка, а раздел 2 начинается с полного списка, передаваемого в cut.

Первый раз aux будет соответствовать второму предложению, затем он будет вызывать себя с аргументами (1, [3], [4; 5; 7; 8]). В следующий раз он также будет соответствовать второму предложению, теперь он вызывает себя с помощью (0, [4; 3], [5; 7; 8]). В третий и последний раз он соответствует первому предложению (n=0) и вернет кортеж, содержащий xs и ys.

Однако обратите внимание, что элементы xs расположены в обратном порядке, так как каждый элемент был добавлен (с помощью оператора cons::). Причина, по которой это делается, заключается в том, что это операция O(1) по сравнению с оператором добавления @, который в левой части равен O(n).

Поскольку xs находится в обратном порядке, последнее выражение в функции является обращением xs.

Альтернативное и немного короткое определение может быть:

let cut n xs =
    let rec aux = function
        | 0, xs, ys -> List.rev xs, ys
        | n, xs, y :: ys -> aux (n - 1, y :: xs, ys)
        | _ -> failwith "invalid arguments"
    aux (n, [], xs)

Answer 2

Вероятно, для достижения этого лучше объединить встроенные функции в списках или последовательностях:

let cut' (n, xs) =
    Seq.take n xs, Seq.skip n xs

Рекурсивно, ваша функция может быть определена так:

let cut (n, xs) =
    let rec aux = function
        | 0, xs, ys -> xs, ys
        | n, xs, y :: ys -> aux (n - 1, y :: xs, ys)
        | _ -> failwith "invalid arguments"
    let l, r = aux (n, [], xs)
    (List.rev l, r)