1

リストの深さを計算する方法に関する wiki ページを見つけました: 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]]
    }
 }
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、機能の追加をやめてリリースを呼び出さなければならない場合があるという理由で、それは実現しませんでした。)

再帰の「排除」

もう 1 つの方法は、外部再帰の削除について確認することです。再帰を完全に排除することはできません — 再帰構造に対する再帰操作を扱っています — しかし、arename ldepth fredが問題を引き起こす外側のレベルに再帰を配置する必要はありません。内部プロシージャのようなものを作成するために使用してこれをapply行います。再帰呼び出しを行っているため、ラムダ項をそれ自体に渡します。(明示的に値を渡さずにその値を取得するためにできるトリックがありますが、それらは醜いものであり、ここでは正直に言う必要があります。)

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 の機能は必要ありません — s を置き換えることで 8.4 に適したものにすることができますlassign:

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 に答える