使用tcl 8.6改进proc以计算列表的深度.特征

Question

我找到了一个关于如何计算列表深度的维基页面:http: //wiki.tcl.tk/11602

如何使用tcl 8.6功能lmap和apply将上述代码重写为单个proc？也许并非真正需要"应用".

proc max list {
    set res [lindex $list 0]
    foreach e [lrange $list 1 end] {if {$e>$res} {set res $e}}
    set res
}

# llmap perhaps can be replaced with lmap from Tcl 8.6
proc llmap {func list} {
    set res {}
    foreach e $list {lappend res [$func $e]}
    set res
 }

proc ldepth list {
    expr {
        [llength $list] == 0? 1:
        [expr {[lindex $list 0] eq $list}]?       0:
           1+[max [llmap ldepth $list]]
    }
 }

Answer 1

第一级的适应性已经让我们接近您想要去的地方,足以使我们将其视为生产解决方案:

proc ldepth {list} {
    expr {
        [llength $list] == 0 ? 1 :
        [lindex $list 0] eq $list ? 0 :
        1 + [tcl::mathfunc::max {*}[lmap e $list {
            ldepth $e
        }]]
    }
}

这使用标准lmap和tcl::mathfunc::max(这是max()函数的实现).请注意,扩展和tcl::mathfunc::maxTcl 8.5的功能,但它们在这里非常有用.

消除扩张

让我们看看我们是否可以摆脱对tcl::mathfunc::max扩展的呼吁.

proc ldepth {list} {
    set m -inf
    expr {
        [llength $list] == 0 ? 1 :
        [lindex $list 0] eq $list ? 0 :
        1 + [lindex [lmap e $list {
            set m [expr { max($m, [ldepth $e]) }]
        }] end]
    }
}

嗯,这只是一个丑陋的触摸.我们不妨这样做:

proc ldepth {list} {
    set m -inf
    expr {
        [llength $list] == 0 ? 1 :
        [lindex $list 0] eq $list ? 0 :
        [foreach e $list {
             set m [expr { max($m,[ldepth $e]) }]
         }
         expr {$m + 1}]
    }
}

这肯定没有变得更好,除了它没有保持这么多的状态(只是一个运行的最大值,而不是深度列表).让我们回到版本lmap!(对于真正的美丽来说真正需要的是lfold,但是有时候你不得不停止添加功能并调用一个版本.)

"消除"递归

我们可以采取的另一种方法是看看删除外部递归.我们不能完全消除递归 - 我们正在处理递归结构的递归操作 - 但是我们不需要将它放在rename ldepth fred会导致问题的外层.我们这样做是apply为了创建一个类似于内部过程的东西,因为我们正在进行递归调用,所以我们将lambda术语传递给它自己.(你可以做一些技巧来获得这个价值,而不是明确地传递它,但它们很丑陋,我们可能在这里说实话.)

proc ldepth {list} {
    set ldepth {{ldepth list} {expr {
        [llength $list] == 0 ? 1 :
        [lindex $list 0] eq $list ? 0 :
        1 + [tcl::mathfunc::max {*}[lmap e $list {
            apply $ldepth $ldepth $e
        }]]
    }}
    apply $ldepth $ldepth $list
}

全字节码版本

仍在进行递归调用.

proc ldepth {list} {
    expr {
        [llength $list] == 0 ? [return 1] :
        [lindex $list 0] eq $list ? [return 0] :
        [set m -inf
         foreach e $list {
             set m [expr {[set d [ldepth $e]]+1>$m ? $d+1 : $m}]
         }
         return $m]
    }
}

通过使用工作队列来完全无递归.这是8.5代码 - 不需要8.6功能 - 您可以通过替换lassigns 来将其写为8.4适合:

proc ldepth {list} {
    set work [list $list 0]
    set maxdepth 0
    while {[llength $work]} {
        ### 8.4 version
        # foreach {list depth} $work break
        # set work [lrange $work 2 end]
        set work [lassign $work[unset -nocomplain work] list depth]
        if {[llength $list] == 0} {
            incr depth
        } elseif {[lindex $list 0] ne $list} {
            incr depth
            foreach e $list {
                lappend work $e $depth
            }
            continue
        }
        set maxdepth [expr {$maxdepth<$depth ? $depth : $maxdepth}]
    }
    return $maxdepth
}

这个故事的主旨？8.6功能对一切都没有意义.