Преобразование в хвостовую рекурсию - PullRequest
Новая
       36

Преобразование в хвостовую рекурсию

0 голосов
/ 19 февраля 2011

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

В моем случае функция должна принимать один список в качестве параметра. Когда функция вызывается, я должен удалить первый элемент из списка, а затем повторить, используя оставшуюся часть списка. Затем мне нужно применить первый элемент, который я каким-то образом удалил, к результату рекурсии. Затем я удаляю второй элемент и делаю то же самое (Примечание: когда я говорю «удалить элемент seond», то есть из исходного списка, поэтому список, переданный в рекурсии, также включает первый элемент). Я делаю то же самое для третьего, четвертого и т. Д. Элементов списка.

Есть ли способ преобразовать описанную выше ситуацию в хвостовую рекурсивную функцию? Может, вложенные хвостовые рекурсивные функции ??? Спасибо за любые ответы.

Хорошо, вот мой основной код. Этот конкретный генератор генерации перестановок (хотя я не слишком озабочен перестановочной частью - это рекурсия, на которой я бы хотел остановиться): 

let permutationsOther str =
  match str with
  | value :: [] ->
    [[value]]
  | _ ->
    let list = (List.map (fun a -> // This applies the remove part for every element a
      let lst = (List.filter (fun b -> b <> a) str) // This part removes element a from the list
      let permutedLst = permutations lst // recursive call
      consToAll a permutedLst // constToAll this is my own function which performs "cons" operation with a and every element in the list permutedLst
    ) str)
    List.reduce (fun acc elem -> elem @ acc) list // flatten list of lists produce by map into a single list

Надеюсь, это достаточно ясно - я буду рад предоставить разъяснения, если это необходимо.

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

1 Ответ

5 голосов
/ 19 февраля 2011

Преобразование в CPS должно помочь:

ПРИМЕЧАНИЕ 1.: Источник образца набирается непосредственно в браузере, поэтому может содержать ошибки :(. Но я надеюсь, что он может продемонстрировать общую идею.

ПРИМЕЧАНИЕ 2: Функция consToAll также должна быть преобразована в CPS: consToAll: 'T ->' T list list -> ('T list list ->' R) -> 'R 

let remove x l = List.filter ((<>) x) l // from original post: should duplicates also be removed ???

let permute l =
    let rec loop k l = 
        match l with
        | [] -> k []
        | [value] -> k [[value]]
        | _ -> filter l [] l (fun r -> r |> List.reduce (fun acc elem -> elem @ acc) |> k )
    and filter l acc orig fk = 
        match l with
        | [] -> fk acc
        | x::xs ->
            remove x orig 
                |> loop (fun res ->
                    consToAll x res (fun rs -> filter xs (rs::acc) orig fk)                    
                    )
    loop id l
...