Не понимаю этот код

Question

Я новичок в F # и нашел какой-то код, который хотел бы использовать. Этот код берет список и возвращает вторую половину списка. Я надеюсь, что кто-то может построчно рассказать о том, что он делает. Я хочу изменить его, чтобы он возвращал первую половину списка. Вот код после того, как это мои вопросы.

let cut l = 
   let rec cut = function
       | xs, ([] | [_]) -> xs  
       | [], _ -> []
       | x::xs, y::y'::ys -> cut (xs, ys)
   cut (l, l)

Что делает = function?

Я почти уверен, что | xs, ([] | [_]) -> xs, если есть xs, добавить его в список

Я не понимаю, что это делает | [], _ -> []

| x::xs, y::y'::ys -> cut (xs, ys): я понимаю первую половину, она создает два подсписка, меня смущает, почему cut отправляет хвост xs и ys Разве вырезать только один параметр?

Answer 1

Функция возвращает вторую половину заданного списка.

Интересной частью кода является только вложенная (рекурсивная) функция, поскольку единственная цель внешней функции - вызвать вложенную функцию и дважды передать ей указанный список. Вложенная функция cut имеет два аргумента (в виде кортежа), поэтому ее тип:

cut : 'a list * 'a list -> 'a list

При рекурсивном вызове этой функции вызывается эта функция (которая объясняет, почему она вызывается с двумя аргументами). Вот код комментария:

// The 'function' syntax means that the arguments of the function are matched against 
// several clauses. When the arguments (lists) match the clause, the clause is selected
// and its body will be executed. 
let rec cut = function
  // When the second list is empty or contains a single element,
  // the function return all elements of the first list
  | xs, ([] | [_]) -> xs  
  // When the first list is empty, return empty list
  | [], _ -> []
  // When first list is non-empty and second contains at least two elements,
  // the function takes one element from the first list and two elements from 
  // the second list (x, y, y'), ignores them and calls itself with the 
  // remaining lists as arguments.
  | x::xs, y::y'::ys -> cut (xs, ys)

cut ([ 1 .. 10 ], [ 1 .. 10 ])

Идея функции заключается в том, что она выполняет итерации по двум копиям одного и того же списка. На каждом рекурсивном шаге он пропускает два элемента из второго и один элемент из первого. К тому времени, когда он достигает конца второго списка, первый содержит вторую половину списка (поскольку функция пропускала свои элементы в 2 раза медленнее).

Чтобы получить первую половину списка , вам необходимо добавить дополнительный параметр к вашей внутренней рекурсивной функции cut. Вы можете использовать его для накопления элементов из первого списка. Опять же, вам нужно пропустить элементы одного из списков в два раза быстрее. Вместо того, чтобы пропускать первые элементы другого списка, вам нужно взять их и добавить в свой аккумулятор.

Я не дам вам полного решения, но, чтобы дать вам некоторое представление, вот псевдокод:

  | x::xs, _::_::ys -> 
      // Call 'cut' recursively to process 'xs' and 'ys'
      // and add the element 'x' to the accumulator.

Другой способ написать функцию - использовать match вместо function и записать два аргумента как стандартные множественные аргументы (вместо использования кортежа). При игнорировании элементов в последнем предложении также можно использовать _, поскольку их имена не нужны:

let rec cut l1 l2 = 
  match l1, l2 with
  | xs, ([] | [_]) -> xs  
  | [], _ -> []
  | _::xs, _::_::ys -> cut xs ys

cut [ 1 .. 10 ] [ 1 .. 10 ]

Answer 2

Самый простой способ увидеть, что делает функция вырезания, это понять, что строка ниже

| x::xs, y::y'::ys -> cut (xs, ys)

опустошает 2-й список в два раза быстрее, чем 1-й список.Это потому, что он вытягивает 2 элемента из заголовка списка ys и один элемент из заголовка списка xs и отбрасывает их.Если он делает это непрерывно, то ys завершится первым, а когда это произойдет, xs будет содержать нижнюю половину исходного списка.

Answer 3

Самый простой способ изменить его так, чтобы он возвращал первую половину списка: передать перевернутый список во внутреннюю функцию и сторнировать результат.

let cut l = 
  let rec cut = function
    | xs, ([] | [_]) -> xs  
    | [], _ -> []
    | x::xs, y::y'::ys -> cut (xs, ys)
  let k = List.rev l
  cut (k, k) |> List.rev

Без List.rev

let cut l = 
  let rec cut f = function
    | x::_, [_] -> f [x]
    | _, [] -> f []
    | [], _ -> []
    | x::xs, _::_::ys -> cut (fun acc -> f (x::acc)) (xs, ys)
  cut id (l, l)