在 Groovy 中将递归闭包更改为 TrampolineClosure

Question

我需要从仅包含字符 0、1 和 V（通配符）的字符串构造所有可能的二进制表示形式。字符串可以是任意长度（超过 1000 个字符），但通配符的数量少于 20 个。

例如，对于输入 V1V，输出将是 [010, 011, 110, 111]

我当前的实现可以工作，但会因少量通配符而溢出堆栈。代码是 running here 如下所示。

def permutts
permutts =
{
  if (!it.contains('V'))
    return [it]

  def target = it
  def res = []

  ['0', '1'].each
  {
    def s = target.replaceFirst(~/V/, it)
    if (s.contains('V'))
    {
      res += permutts(s)
    }
    else
    {
      res << s
    }
  }
  res
}
println permutts('V1V')

我尝试遵循一些使用 trampoline() 的示例，但我什至不确定这是否是正确的方法。 The API says，“...该函数应该执行计算的一个步骤...”但每个步骤执行两个操作：用 0 和 1 替换 V.

这是我的一个尝试，可以是run here。

def permutts

permutts =
{ it, res = [] ->
  println "entering with " + it + ", res=" + res
  if (it.contains('V'))
  {
    def s = it.replaceFirst(~/V/, '1')
    permutts.trampoline(s, res)

    s = it.replaceFirst(~/V/, '0')
    permutts.trampoline(s, res)
  }
  else
  {
    res << it
  }
}.trampoline()
println permutts('VV')

输出为：

entering with VV, res=[]
entering with 0V, res=[]
entering with 00, res=[]
[00]

至少它在做一些事情，但我不明白为什么它没有继续下去。任何人都可以解释我做错了什么或提出不同的方法来解决这个问题吗？

Answer 1

Groovy的trampoline()提供了tail call optimization，所以它应该用于closures/methods在最后执行的指令（tail）中调用自己。

因此，更好的解决方案是经典的 "head/tail" 处理（添加 println 以跟踪调用）：

def permutts
permutts = { s, res ->   
    if (s.length() == 0) {
        println "s = $s, res = $res"
        res
    } else {
        println "s = $s, res = $res"
        if (s[0] == 'V') { // s[0] ~ list.head()
            res = res.collect({ it = it + '0' }) + res.collect({ it = it + '1' })
        } else {
            res = res.collect({ it = it + s[0] })
        }

        permutts.trampoline(s.substring(1), res) // s.substring(1) ~  list.tail()
    }
}.trampoline()

示例：

permutts('VV', [''])     
  s = VV, res = []
  s = V, res = [0, 1]
  s = , res = [00, 10, 01, 11]
  Result: [00, 10, 01, 11]

permutts('0V0', ['']) 
  s = 0V0, res = []
  s = V0, res = [0]
  s = 0, res = [00, 01]
  s = , res = [000, 010]
  Result: [000, 010]

关于您的代码，来自 TrampolineClosure javadoc:

A TrampolineClosure wraps a closure that needs to be executed on a functional trampoline. Upon calling, a TrampolineClosure will call the original closure waiting for its result. If the outcome of the call is another instance of a TrampolineClosure, created perhaps as a result to a call to the TrampolineClosure.trampoline() method, the TrampolineClosure will again be invoked. This repetitive invocation of returned TrampolineClosure instances will continue until a value other than TrampolineClosure is returned. That value will become the final result of the trampoline.

即在尾调用优化中进行的替换。在您的代码中，TrampolineClosures returns 的整个链，只要其中一个不 return TrampolineClosure。

从groovy2.3开始，可以使用@TailRecursive尾调用优化的AST转换：

import groovy.transform.TailRecursive

@TailRecursive
List permutts(String s, List res = ['']) {   
    if (s.length() == 0) {
        res
    } else {
        res = (s[0] == 'V') ? res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + s[0] })       
        permutts(s.substring(1), res)
    }
}

编辑：

为了完成我的回答，上面的内容可以用 functional fold, which in Groovy is inject 在一行中完成（使用集合的头部作为初始值并遍历尾部）：

assert ['000', '010'] == ['0', 'V', '0'].inject([''], { res, value -> (value == 'V') ?  res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + value }) })
assert ['00', '10', '01', '11'] == ['V', 'V'].inject([''], { res, value -> (value == 'V') ?  res.collect({ it = it + '0' }) + res.collect({ it = it + '1' }) : res.collect({ it = it + value }) })

在 Groovy 中将递归闭包更改为 TrampolineClosure

Changing recursive Closure to TrampolineClosure in Groovy

recursion

groovy