Возможно ли преобразовать эту рекурсивную функцию в хвостовую рекурсию, используя стиль передачи продолжения? - PullRequest
Новая
       47

Возможно ли преобразовать эту рекурсивную функцию в хвостовую рекурсию, используя стиль передачи продолжения?

0 голосов
/ 14 февраля 2019

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

Итак, я задал связанный вопрос несколько месяцев назад.Кто-то заметил, что мою рекурсивную функцию можно сделать хвостовой рекурсией, используя стиль передачи продолжения.Я не могу понять, как это сделать.

Пример кода: 

type In1 = int
type In2 = int
type Out1 = int
type Out2 = int

type FaceInstruction<'a> =
| Member1 of (In1 * (Out1 -> 'a))
| Member2 of (In2 * (Out2 -> 'a))

let private mapI f = function
    | Member1 (x, next) -> Member1 (x, next >> f)
    | Member2 (x, next) -> Member2 (x, next >> f)

type FaceProgram<'a> =
| Free of FaceInstruction<FaceProgram<'a>>
| Pure of 'a

let rec bind f = function
| Free x -> x |> mapI (bind f) |> Free
| Pure x -> f x

Функция, которую я пытаюсь сделать так, чтобы хвост был восстановлен, это bind

Myпопытки выглядят примерно так: 

let rec bind2 (f: 'a -> FaceProgram<'b>) k  z : FaceProgram<'b> = 
    match z with
    |Pure x -> x |> f |> k
    |Free x -> bind2 ???

Я начинаю думать, что на самом деле невозможно сделать этот хвост рекурсивным.Тип FaceInstruction<'a> уже включает в себя продолжение, а функция mapI изменяет это продолжение, поэтому теперь попытка добавить другое продолжение k является одним из двух дополнительных продолжений, которые я не могу обработать прямо сейчас!

1 Ответ

0 голосов
/ 14 февраля 2019

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

Причина в том, что ни bind, ни mapI не вызывают bind.Обратите внимание, как они оба сразу выходят, не углубляясь в стек.bind вызывает mapI, но mapI вообще не вызывает никакой функции (кроме Member1 или Member2, которые являются функциями конструктора).Они создают новый экземпляр Free monad, используя bind и next.bind должен быть объявлен как rec, потому что ему нужна собственная ссылка для передачи себя в качестве параметра mapI.

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

...