Как добиться оптимизации хвостового вызова при перемещении древовидной структуры с использованием метода продолжения прохождения

Question

Я пытаюсь реализовать оптимизацию хвостового вызова, чтобы пересечь структуру линии дерева, используя стиль продолжения прохождения в scala. К сожалению, мой предыдущий опыт работы с fsharp не очень помогает. У меня есть рекурсивный вызов без оптимизации хвостового:

def traverseTree(tree: Tree)(action: Int => Unit): Unit = { 
    def traverseTreeRec(tree: Tree, continuation:() => Unit, action: Int => Unit): Unit = tree match { 
    case Leaf(n) => { 
     action(n) 
     continuation() 
    } 
    case Node(n1, n2) => { 
     traverseTreeRec(n1,() => traverseTreeRec(n2, continuation, action), action) 
    } 
    } 
    traverseTreeRec(tree,() =>(), action) 
} 

Затем я пытаюсь переписать с помощью @annotation.tailrec и TailCalls, но до сих пор не уверен, что как украсить продолжение

def traverseTree(tree: Tree)(action: Int => Unit): Unit = { 
    @annotation.tailrec 
    def traverseTreeRec(tree: Tree, continuation:() => TailRec[Unit], action: Int => Unit): TailRec[Unit] = tree match { 
    case Leaf(n) => { 
     action(n) 
     continuation() 
    } 
    case Node(n1, n2) => 
     // how to properly implement tail call here? 
     // ERROR: it contains a recursive call not in tail position 
     traverseTreeRec(n1,() => tailcall(traverseTreeRec(n2, continuation, action)), action) 
    } 
    traverseTreeRec(tree,() => done(), action) 
} 

Заранее спасибо

ps: full sample on gist

Answer 1

У меня недостаточно знаний о Scala, но в коде я предполагаю, что вы можете сделать:

tailcall(traverseTreeRec(n1,() => tailcall(traverseTreeRec(n2, continuation, action)), action)) 

С tailcall, которые были там на самом деле были в другой анонимной функции она будет вызывать при попадании в лист. Возможно, вам это нужно во всех положениях хвоста:

def traverseTree(tree: Tree)(action: Int => Unit): Unit = { 
    @annotation.tailrec 
    def traverseTreeRec(tree: Tree, continuation:() => TailRec[Unit], action: Int => Unit): TailRec[Unit] = tree match { 
    case Leaf(n) => { 
     action(n) 
     tailcall(continuation()) 
    } 
    case Node(n1, n2) => 
     tailcall(traverseTreeRec(n1,() => tailcall(traverseTreeRec(n2, continuation, action)), action)) 
    } 
    tailcall(traverseTreeRec(tree,() => done(), action)) 
} 

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

Answer 2

Наконец, у меня есть ответ от Coursera дискуссионного форума:

def traverseTree(tree: Tree)(action: Int => Unit): Unit = { 
    def traverseTreeRec(tree: Tree, continuation:() => TailRec[Unit]): TailRec[Unit] = tree match { 
    case Leaf(n) => { 
     action(n) 
     continuation() 
    } 
    case Node(n1, n2) => 
     tailcall(traverseTreeRec(n1, 
     () => traverseTreeRec(n2, 
     () => tailcall(continuation())))) 
    } 
    traverseTreeRec(tree,() => done(())).result 
} 

пс: suggested question by @rob-napier содержит некоторые детали, почему она должна применяться таким образом