Стиль продолжения прохождения в Scala

Question

Я поверхностно прочитал пару статей в блоге/Wikipedia о стиле продолжения прохождения. Моя цель на высоком уровне состоит в том, чтобы найти системный метод, чтобы сделать любую рекурсивную функцию (или, если есть ограничения, будучи в курсе их) хвост-рекурсивный. Тем не менее, мне трудно сформулировать свои мысли, и я не уверен, насколько мои попытки этого имеют смысл.

В целях примера я предложу простую проблему. Цель состоит в том, чтобы отсортировать список уникальных символов для вывода всех возможных слов, сделанных из этих символов в алфавитном порядке. Например, sol("op".toList, 3) должен вернуть ooo,oop,opo,opp,poo,pop,ppo,ppp.

Мой рекурсивной решение заключается в следующем:

def sol(chars: List[Char], n: Int) = { 
    def recSol(n: Int): List[List[Char]] = (chars, n) match { 
     case (_ , 0) => List(Nil) 
     case (Nil, _) => Nil 
     case (_ , _) => 
      val tail = recSol(n - 1) 
      chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _) 
    } 
    recSol(n).map(_.mkString).mkString(",") 
} 

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

Поэтому вопрос в основном: как функция, описанная выше, в CPS?

Answer 1

Попробуйте это:

import scala.annotation.tailrec 
def sol(chars: List[Char], n: Int) = { 
    @tailrec 
    def recSol(n: Int)(cont: (List[List[Char]]) => List[List[Char]]): List[List[Char]] = (chars, n) match { 
    case (_ , 0) => cont(List(Nil)) 
    case (Nil, _) => cont(Nil) 
    case (_ , _) => 
     recSol(n-1){ tail => 
     cont(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _)) 
     } 
    } 
    recSol(n)(identity).map(_.mkString).mkString(",") 
} 

Answer 2

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

type Cont[Hole,Result] = Hole => Result 

Здесь Hole представляет тип отверстия, которое должно быть заполнено, и Result представляет тип значения вычисления в конечном счете вычисляет.

Теперь, когда у нас есть способ представления продолжений, мы можем беспокоиться о самом преобразовании CPS. В основном это включает в себя следующие этапы:

• Преобразование применяется рекурсивно к выражению, останавливаясь при «тривиальных» выражениях/вызовах функций. В этом контексте «тривиальный» включает функции, определенные Scala (поскольку они не преобразуются в CPS и, следовательно, не имеют параметра продолжения).
• К каждой функции необходимо добавить параметр типа Cont[Return,Result], где Return - это тип возврата нетрансформированной функции, а Result - это тип конечного результата вычисления в целом. Этот новый параметр представляет собой текущее продолжение. Тип возврата для преобразованной функции также изменяется на Result.
• Каждый вызов функции должен быть преобразован для соответствия новому параметру продолжения. Все после вызов необходимо поместить в функцию продолжения, которая затем добавляется в список параметров.

Например, функция:

def f(x : Int) : Int = x + 1 

становится:

def fCps[Result](x : Int)(k : Cont[Int,Result]) : Result = k(x + 1) 

и

def g(x : Int) : Int = 2 * f(x) 

становится:

def gCps[Result](x : Int)(k : Cont[Int,Result]) : Result = { 
    fCps(x)(y => k(2 * y)) 
} 

Теперь gCps (5) возвращает (через currying) функцию, которая представляет частичное вычисление. Мы можем извлечь значение из этого частичного вычисления и использовать его, предоставив функцию продолжения. Например, мы можем использовать функцию тождества для извлечения значения без изменений:

gCps(5)(x => x) 
// 12 

Или, мы можем напечатать его с помощью println вместо:

gCps(5)(println) 
// prints 12 

Применяя это к вашему коду, мы получим:

def solCps[Result](chars : List[Char], n : Int)(k : Cont[String, Result]) : Result = { 
    @scala.annotation.tailrec 
    def recSol[Result](n : Int)(k : Cont[List[List[Char]], Result]) : Result = (chars, n) match { 
    case (_ , 0) => k(List(Nil)) 
    case (Nil, _) => k(Nil) 
    case (_ , _) => 
     recSol(n - 1)(tail => 
         k(chars.map(ch => tail.map(ch :: _)).fold(Nil)(_ ::: _))) 
    } 

    recSol(n)(result => 
       k(result.map(_.mkString).mkString(","))) 
} 

Как вы можете видеть, хотя recSol теперь хвостовой рекурсией, он приходит со стоимостью строительства более сложное продолжение на каждой итерации. Таким образом, все, что мы действительно сделали, - это торговое пространство в стеке управления JVM для пространства в куче - преобразование CPS не волшебным образом уменьшает пространственную сложность алгоритма.

Кроме того, recSol является только хвостовым рекурсивным, потому что рекурсивный вызов recSol является первым (нетривиальным) выражением recSol. В общем, однако, рекурсивные вызовы будут иметь место в продолжении. В случае, когда есть один рекурсивный вызов, мы можем обойти это, преобразовывая только, обращаясь к рекурсивной функции в CPS. Тем не менее, в общем, мы все равно будем торговать стеком для пространства кучи.