1

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

如何使用 tcl 8.6 features 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]]
    }
 }
4

2 回答 2

5

第一级适应已经让我们接近你想要去的地方，足以让这就是我认为的生产解决方案：

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

这使用了标准lmapand tcl::mathfunc::max（这是max()函数的实现）。请注意，扩展 和tcl::mathfunc::max是 Tcl 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]
    }
}

通过使用工作队列来完全无递归。lassign这是 8.5 的代码——不需要 8.6 的特性——你可以通过替换s将其写成适合 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 的功能对所有东西都没有意义。

于 2013-05-11T08:21:35.840 回答
0

这是一个简单的工作。它只是将列表展平，直到无法进一步展平为止。尝试的次数就是深度。不需要递归。

proc ldepth {lst} {
    set depth 1
    set fatter $lst
    set flatter [join $fatter]
    while {$flatter ne $fatter} {
        set fatter $flatter
        set flatter [join $fatter]
        incr depth
    }
    return depth
}

希望这可以帮助！

于 2019-09-08T17:57:54.757 回答