как да направите тези прости функции рекурсивни в 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)
| [] -> []
| [_] -> []

Тази работа.

Но си помислих, че сега, когато се занимавах с това, бих могъл да науча малко за рекурсията на опашката, която ми е трудно да разбера.

Ето защо си помислих, че ако мога да получа малко помощ за създаване на функции, които бях направил рекурсивни на опашка, може би щеше да стане по-ясно как работи, вместо да чета някъде пример, който може да не разбирам толкова добре, колкото собствения си код (помнете, Аз съм пълен е# новак :))

Всички други конструктивни коментари относно моя код, разбира се, са добре дошли!


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
Съжалявам, че изтрих коментара си. Перифразирах го. Значи дори се отнася до индекса? Добре.   -  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
Много хубаво! thx много, това е точно това, което търсих. Не съм напълно сигурен, че разбирам какво прави цикълът 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