0

Haskell で単純な反復アルゴリズムを作成しようとしていますが、エレガンスとスピードの点で最適なソリューションを見つけるのに苦労しています。

任意の関数を使用して状態を記録し、停止条件に達するまで、何度も反復して状態に操作を適用する必要があるアルゴリズムがあります。iterateM のような関数を定義することで、このようなスキームを実装する方法を既に知っています。

ただし、この場合、各ステップで実行する操作は状態に依存し、「ステップ タイプ」条件をチェックして次の反復タイプを決定し、次の 10 反復で操作 A を実行するか、操作 B を実行することになります。条件を再度チェックする前に、次の反復のために。

命令型のスタイルで次のように書くことができます。

c=0
while True:
    if c>0:
        x=iterateByA(x)
        c=c-1
    else:
        if stepCondition(x)==0:
            x=iterateByA(x)
            c=9
        else:
           x=iterateByB(x)
    observeState(x)
    if stopCondition(x):
        break

もちろん、これを Haskell にコピーすることもできますが、もっとエレガントなことをしたいと思います。

私の考えは、反復で関数のリストを使用してポップして状態に適用し、そのリストが空になったら(「ステップタイプ」条件に基づいて)新しいリストで更新することです。ただし、これは非効率になるのではないかと少し心配しています。これを行い、次のようなものを使用しますか

take 10 (repeat iterateByA)

上記の命令型のように、カウンターのみを使用するタイトなループにすべてのリスト割り当てなどをコンパイルしますか?

これを行う別のきちんとした効率的な方法はありますか?

これが適応型確率シミュレーション アルゴリズムの場合、反復ステップによって状態が更新され、(最適なシミュレーション スキームを決定する) ステップ条件が現在の状態の関数になります。実際には 3 つの異なる反復スキームがありますが、2 つの例の方が説明しやすいと思いました。

(それが問題かどうかはわかりませんが、haskell では iterateByX 関数は乱数を使用するためモナディックであることも指摘しておく必要があります。)

4

1 に答える 1

1

直訳はそれほど悪くはありません。

loop c x
    | stopCondition x = observe x
    | c > 0           = observe x >> iterateByA x >>= loop (c-1)
    | stepCondition x = observe x >> iterateByA x >>= loop 9
    | otherwise       = observe x >> iterateByB x >>= loop c

の繰り返しがobserve気に入らない場合は、さまざまなトリックを使用して削除できます。

ただし、おそらく物事を再考する必要があります。これは非常に必須のアプローチです。おそらくもっと良いことができるでしょう（しかし、ここで与えられたいくつかの詳細からその方法を言うのは難しいです）.

于 2012-04-04T19:31:19.663 に答える