как сделать эти простые функции хвостовой рекурсией в f#

У меня есть эти две функции

//Remove all even indexed elements from a list and return the rest
let rec removeEven l =
match l with
| x0::x1::xs -> x1::removeEven (xs)
| [] -> []
| [_] -> []

//combine list members into pairs
let rec combinePair l =
match l with
| x0::x1::xs -> (x0,x1) :: combinePair(xs)
| [] -> []
| [_] -> []

Та работа.

Но я подумал, что теперь, когда я был в этом, я мог бы также немного узнать о хвостовой рекурсии, с которой мне трудно разобраться.

Вот почему я подумал, что если бы я мог получить помощь в создании функций, которые я сделал для себя хвостовой рекурсией, возможно, стало бы более понятно, как это работает, вместо того, чтобы читать где-то пример, который я мог бы не понять, а также мой собственный код (помните, Я полный F# новичок :))

Любые другие конструктивные комментарии о моем коде, конечно же, только приветствуются!


list recursion f# tail-recursion
person PNS    schedule 21.02.2012    source источник
comment
Я думаю, это правильно. Предполагается удалить элементы с четным индексом, а не элементы с четным значением, и в этом случае 1 имеет индекс 0, а 2 имеет индекс 1.   -  person PNS    schedule 21.02.2012
comment
Почему removeEven [1;2] возвращает [2]? Я скопировал его поведение в своем ответе, но, похоже, его следует называть returnEven или removeOdd или что-то в этом роде.   -  person Daniel    schedule 21.02.2012
comment
Извините, что удалил свой комментарий. Я перефразировал это. Итак, even относится к индексу? Хорошо.   -  person Daniel    schedule 21.02.2012
comment
@Daniel: комментарий в верхней части кода говорил об этом все время. ;-]   -  person ildjarn    schedule 21.02.2012
comment
@ildjarn: Кто читает комментарии к коду?!? :-)   -  person Daniel    schedule 21.02.2012

Ответы (2)


arrow_upward
4
arrow_downward

Типичный способ сделать функции хвостовой рекурсией в F# — использовать список (в данном случае acc) для накопления результатов и обращения его для получения правильного порядка:

let removeEven l =
    let rec loop xs acc =
        match xs with        
        | [] | [_] -> acc
        | _::x1::xs' -> loop xs' (x1::acc)
    loop l [] |> List.rev

let combinePair l =
    let rec loop xs acc =
        match xs with        
        | [] | [_] -> acc
        | x0::x1::xs' -> loop xs' ((x0, x1)::acc)
    loop l [] |> List.rev

Поскольку мы просто возвращаем результаты после каждого рекурсивного вызова loop, эти функции являются хвостовыми рекурсивными.

Ваши функции выглядят неплохо, но у меня все же есть несколько замечаний:

  • Отступы важны в F#. Я бы предпочел, чтобы match... with стояло через несколько пробелов после объявления lec rec.
  • Случаи сопоставления шаблонов должны следовать последовательному порядку. Рекомендуется сначала начать с базовых случаев.
  • Ключевое слово function естественно использовать для сокращения функций всякий раз, когда у вас есть шаблон fun t -> match t with.
  • От ненужных скобок лучше избавиться, особенно в функциях с одним аргументом.

Применяя приведенные выше комментарии, ваши функции становятся следующими:

// Remove all even indexed elements from a list and return the rest
let rec removeEven = function
    | [] | [_] -> []
    | _::x1::xs -> x1::removeEven xs

// Combine list members into pairs
let rec combinePair = function
    | [] | [_] -> []
    | x0::x1::xs -> (x0, x1)::combinePair xs
person pad    schedule 21.02.2012
comment
Действительно мило! большое спасибо, это именно то, что я искал. Не совсем уверен, что понимаю, что делает строка loop l [] |› List.rev. Я имею в виду, что я знаю, что список должен перевернуться, но почему цикл l []? и когда будет достигнут этот код записи? - person PNS; 21.02.2012
comment
| [] -> [] | [_] -> [] также можно свернуть в | [] | [_] -> [], сохранив две строки. - person ildjarn; 21.02.2012
comment
@ildjarn: Ваше предложение было применено :). - person pad; 21.02.2012
comment
@PNS: эта строка такая же, как List.rev (loop l []). Начинаем накапливать из пустого списка. Когда во входном списке меньше 2 элементов, мы возвращаем список аккумуляторов и обращаем его. - person pad; 21.02.2012

arrow_upward
4
arrow_downward

Если вам нужен более медленный, менее удобный способ сделать это, который использует больше памяти, вы можете использовать продолжение.

let removeEven items = 
  let rec loop f = function
    | _::h::t -> loop (fun acc -> f (h::acc)) t
    | [] | [_] -> f []
  loop id items

Но эй, это хвостовая рекурсия.

person Daniel    schedule 21.02.2012
comment
Я думаю, что результат должен быть отменен - person Tyson Williams; 25.02.2020
comment
@TysonWilliams Нет, сэр. Это не. - person Daniel; 26.02.2020
comment
О, да. Вы правы. Извините за мою ошибку. (Я знал, что должен был проверить это, прежде чем делать этот комментарий: P) - person Tyson Williams; 26.02.2020