5

lapplyやReduceなどの関数で機能する関数の評価を短絡するためのRのcallCC関数を取得する方法を理解しようとしています。

動機

これにより、計算を早期に終了できるようになるため、Reduce と lapply は O(n) を超える漸近効率になります。

たとえば、リスト内の値を検索している場合、「ファインダー」関数をリスト全体にマップできます。2 番目に見つかった場合、lapply は実行を停止し、その値が返されます (ループを壊したり、 return ステートメントで早期に発生します)。

問題は、callCC が必要とするスタイルを使用して、lapp と Reduce が取る関数を書くのに問題があることです。

例

リスト内の値「100」を見つける関数を作成しようとしているとします。

imperativeVersion <- function (xs) {
    for (val in xs) if (val == 100) return (val)
}

lapply に渡す関数は次のようになります。

find100 <- function (val) { if (val == 100) SHORT_CIRCUIT(val)  }
functionalVersion <- function (xs) lapply(xs, find100)

短絡機能がまだ定義されていないため、これは (明らかに) クラッシュします。

callCC( function (SHORT_CIRCUIT) lapply(1:1000, find100) )

問題は、find100 が定義されたときに短絡機能が存在しなかったため、これもクラッシュすることです。これに似たものが機能することを望みます。

以下は、lapply に渡された関数が作成された時点で SHORT_CIRCUIT IS が定義されているため機能します。

callCC(
    function (SHORT_CIRCUIT) {
        lapply(1:1000, function (val) {
             if (val == 100) SHORT_CIRCUIT(val)
        })
)

上記のようにインラインで定義せずに、lapply に渡される関数で SHORT_CIRCUIT を定義するにはどうすればよいですか?

この例は、ループ、リデュース、またはその他の方法を使用して実現できることを認識しています。具体的には、lapply および Reduce で callCC を使用する際の問題の解決策を探しています。

私が漠然としていたり​​、説明が必要な場合は、下にコメントを残してください。誰かがこれを手伝ってくれることを願っています:)

編集1：アプローチは「生産品質」でなければなりません。逆解析機能や同様の黒魔術はありません。

4

3 に答える 3

3

この問題の解決策を見つけました：

find100 <- function (val) {
    if (val == 100) SHORT_CIRCUIT(val)
}

short_map <- function (fn, coll) {


    callCC(function (SHORT_CIRCUIT) {

        clone_env <- new.env(parent = environment(fn))
        clone_env$SHORT_CIRCUIT <- SHORT_CIRCUIT

        environment(fn) <- clone_env
        lapply(coll, fn)

    })
}

short_map(find100, c(1,2,100,3))

高階関数を callCC で動作させる秘訣は、プログラムの残りの部分を実行する前に、短絡関数を入力関数環境に割り当てることです。意図しない副作用を避けるために、環境のクローンを作成しました。

于 2013-10-29T03:43:05.840 に答える
0

使えるかどうかわかりませんが、

    find100 <- "function (val) { if (val == 100) SHORT_CIRCUIT(val)  }"
    callCC( function (SHORT_CIRCUIT) lapply(1:1000, eval(parse(text = find100))) )
    #[1] 100
于 2013-10-17T19:10:42.363 に答える