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

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

3 голосов
/ 21 февраля 2012

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

//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 # новичок :))

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

Ответы [ 2 ]

3 голосов
/ 21 февраля 2012

Типичным способом сделать функции хвостовой рекурсивной в 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
2 голосов
/ 21 февраля 2012

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

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

Но, эй, это хвост-рекурсивный.

...