2

特定の変数が特定のしきい値よりも小さいかどうかを while ループのすべての反復でチェックするアルゴリズムを実装するときに、これはよく発生します。

命令型言語では、次のようになります。

 while ( x < TRESHOLD ) {
      x = usefullStuff();
 }

もちろん、便利なスタッフが何らかの形で x に影響を与えている場所...

関数型プログラミングのパラダイムを利用して、この構造を haskell にどのように変換しますか?

4

4 に答える 4

6

あなたのプログラムが何をするのかはわかりませんが、ロジックを少し違った方法で構築したいと思うでしょう。Why Functional Programming Mattes - いくつかのアイデアについては、ペーパーのセクション 4 を参照してください。ニュートン法を使用して方程式の根を見つけることを含む、同様の状況を扱います。そこでは責任が分割され、ループ ロジックが逐次近似の生成から分離されます。

がモナド、つまり副作用のある関数の場合usefulStuff、次のようなものを使用する必要があります。

whileLoop x
  | x < THRESHOLD = return x
  | otherwise     = do x <- usefulStuff
                       whileLoop x
于 2012-11-30T23:33:13.060 に答える
5

Control.Monad.Loops から:

iterateWhile :: Monad m => (a -> Bool) -> m a -> m a
iterateWhile p x = do
    y <- x
    if p y
      then iterateWhile p x
      else return y

次に、 usefullStuff に副作用があると仮定します。

iterateWhile (< threshold) usefullStuff
于 2012-11-30T23:33:32.473 に答える
3

説明通りに

特定の変数が特定のしきい値よりも小さいかどうかを while ループのすべての反復でチェックするアルゴリズムを実装するときに、これはよく発生します。

usefullStuffコントロール値の新しい値を返す引数なしではxなく、パラメーターとして取る変換を意味していると思いxます。

それを直訳すると、

until (>= threshold) usefullStuff x

ただし、通常はループ制御以外にも状態があるため、次のようなものがあります。

until ((>= threshold) . getX) usefullStuff (someDataContaining x)

どこでusefullStuff :: RecordContainingX -> RecordContainingX。

一方、usefullStuff本当に引数を取らないことを意図している場合、それが純粋な場合、常に同じ結果が得られるため、ループに入ったり、ループから抜けたりすることはありません。それはあまり役に立ちません。usefullStuffでは、 が値を生成するIO-actionであると仮定しましょう。それで

while :: Ord a -> (a -> Bool) -> a -> IO a -> IO a
while test value action
    | test value = do
               newValue <- action
               while test newValue action
    | otherwise  = return value

パターンをキャプチャします。

于 2012-11-30T23:15:52.460 に答える
3

最初: 命令型言語では、通常、whilewho's body updates のループを記述しますx。Haskell では、これは起こりません。したがって、アルゴリズムを少し異なる構造にする必要があります。

通常行うことは、ループ本体を引数として取り、その結果として新しい値を返す関数に変えることです。その後、Prelude の関数を使用して、何らかの条件が満たされるまで関数を繰り返し適用できます。または、 を使用してすべての結果の無限リストを生成し、または同様の関数を使用して、そのリストをスキャンして目的の項目を探すこともできます。xxuntiliteratetakeWhile

では、ループ本体が実際にいくつかの変数を更新するとどうなるでしょうか? その場合、これらすべての変数を単一のデータ構造にパックすることができ、その後、上記の手順が適用されます。言うまでもなく、これらの変数が多数ある場合、これはおそらく非常に複雑になります。大規模で複雑なループを避けるようにしてください。(Haskell だけでなく、どの言語でも。)

あなたは「アルゴリズム」という言葉を使っていますが、これは、ダイクストラのシャント アルゴリズム、Barnes-Hut n-body シミュレーション アルゴリズム、またはその他の「純粋な」アルゴリズムなどについて話しているのではないかと私に思わせます。一方、ループ本体が非常に大きなデータ構造に対して更新を実行する必要がある場合、または実際の I/O 操作を実行する必要がある場合 (たとえば、ネットワーク サーバーのメイン ループ)、モナドで実行する必要があります。これは通常、インプレース更新が可能であることを意味し、より一般的な命令型アプローチに従うことができます。

于 2012-12-01T13:36:25.593 に答える