Блог

Я новичок в 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 . Разве cut не принимает только один параметр?

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

Интересной частью кода является только вложенная (рекурсивная) функция, потому что единственное назначение внешней функции — вызвать вложенную функцию и передать ей указанный список два раза. Вложенная 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 ]
  

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

 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)
  

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

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

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