在Groovy中将递归Closure更改为TrampolineClosure

Question

我需要构建一个字符串只包含字符的所有可能的二进制表示0,1和V(通配符).字符串可以是任意长度(超过1000个字符),但通配符的数量小于20.

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

我当前的实现工作正常,但是使用适量的通配符溢出堆栈.代码在这里运行,如下所示.

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()但我甚至不确定这是否是正确的方法. API说,"...函数应该执行计算的一个步骤..."但每个步骤执行两个动作:替换in 0和1for V.

这是我的一次尝试,可以在这里运行.

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()提供尾调用优化,因此它应该用于在最后执行的指令(尾部)中调用自己的闭包/方法.

因此,更好的解决方案是经典的"头/尾"处理(添加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]

关于你的代码,来自TrampolineClosurejavadoc:

TrampolineClosure包裹一个需要在功能蹦床上执行的闭包.在调用时,TrampolineClosure将调用原始闭包等待其结果.如果调用的结果是TrampolineClosure的另一个实例,可能是因为调用TrampolineClosure.trampoline()方法而创建的,则将再次调用TrampolineClosure.返回的TrampolineClosure实例的重复调用将继续,直到返回TrampolineClosure以外的值.这个价值将成为蹦床的最终结果.

也就是说,尾调用优化中的替换.在你的代码中,TrampolineClosure只要其中一个链没有返回TrampolineClosure ,整个s 链就会返回.

从groovy 2.3开始,您可以使用@TailRecursiveAST转换进行尾调用优化:

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)
    }
}

编辑:

为了完成我的回答,上面的内容可以在功能折叠的一行中完成,在Groovy中注入(使用集合的头部作为初始值并迭代尾部):

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 }) })