0

次のプログラムがあるとします。

foo x y = let l1 = foo 0 x
              l2 = foo 0 y
          in l1 + l2

これは単純な例ですが、デモンストレーション目的には十分だと思います。fooを新しく (再帰的に) 呼び出すたびに、 l1とl2の式の評価順序を変更するにはどうすればよいでしょうか? それらが宣言されたときではなく、式（この場合は演算子内の式）内で遅延評価されることはわかっていますが、プログラムが無限ループに入る場合があるため、述べたように行う方法が必要です。この無限再帰が 2 番目に評価される引数l2で発生する場合、 l1は常に*l2の前に評価されるため問題はありませんが、その逆、つまりl1式を無限に評価する場合、*l2*** は評価する機会がありません。したがって、新しいfoo関数の呼び出しごとに ***l1*式とl2式の評価をうまくやりくりできれば、問題は解決します。素敵な/一般的な解決策を探しています。

編集: xまたはyまたはその両方が無限の構造 (リスト) である可能性があることを忘れており、そこに問題があります。

4

1 に答える 1

1

問題

良い答えを得るには、まず具体的な質問が必要です。ゼロまたは別の自然数Zの後継である自然数を考えてみましょう。S nn

data Nat = Z | S Nat

zero = Z
one  = S Z
two  = S $ S Z

Haskell では、次のような無限の再帰的データ構造を書くこともできます。

infinity = S infinity

Nat偶数でない限り、infinity偶数か奇数かを判断できます。

even :: Nat -> Bool
even  Z    = True
even (S n) = odd n

odd :: Nat -> Bool
odd  Z    = False
odd (S n) = even n

有限Natの s の場合、evenはTrueまたはFalseであり、even infinityはundefinedです。これは問題ありませんが、2 つの数値のどちらかが であるかどうかを確認するにはどうすればよいevenでしょうか。素朴な実装を書くことができます:

eitherEven :: Nat -> Nat -> Bool
eitherEven x y = even x || even y

これは、最初の引数が有限である場合はいつでも非常にうまく機能します。以下、evenは任意の偶数、oddは任意の奇数です。

eitherEven even even     == True
eitherEven even odd      == True
eitherEven even infinity == True
eitherEven odd  even     == True
eitherEven odd  odd      == False
eitherEven odd  infinity == undefined

Trueしかし、第一引数が無限大の場合、第二引数が無限大の場合でも戻りません。Even

eitherEven infinity even     == undefined -- this should be True
eitherEven infinity odd      == undefined
eitherEven infinity infinity == undefined

簡単な解決策

この問題の簡単な解決策は、最初の引数のテストと 2 番目の引数のテストを交互に行うことです。関数を再帰的に呼び出すときは、引数を交換して、2 つの引数のどちらをテストするかを切り替えます。

eitherEven :: Nat -> Nat -> Bool
eitherEven Z         _ = True
eitherEven (S Z)     y = even y 
eitherEven (S (S x)) y = eitherEven y x

これには、最初の引数が有限でない場合でも、目的の出力があります。

> eitherEven infinity two
True

引数が対称的に扱われないより複雑な問題については、Boolフラグを渡して各ステップで反転させることができます。一般に、作業中の場所を追跡するために、任意のステート マシンを使用できます。

3 つの数値のいずれかが偶数かどうかをテストしたいときに何をすべきかをすぐには解決できないため、この解決策はあまり満足のいくものではありません。そのためには、新しい関数を作成する必要があります。

anyEven3 :: Nat -> Nat -> Nat -> Bool
anyEven3 Z         _ _ = True
anyEven3 (S Z)     y z = eitherEven y z
anyEven3 (S (S x)) y z = anyEven3 y z x

再試行する前に両方をx試したいので、最後に置きます。行列を作っています。キューの最初のものが結果 を生成することを証明できれば、完了です。キュー内の最初のもので結果が生成されないことを証明できれば、それをキューから削除し、より小さな入力セットで機能するバージョンを使用します。キューの最初のものの結果を決定できない場合は、最後に置きます。同じパターンは、引数を 2 つ取る場合や、引数を1 つしか取る場合にも見られます。yzxTrueeitherEveneven

anyEven :: [Nat] -> Bool
anyEven = go []
    where
        go [] [] = False
        go r  [] = go [] (reverse r)
        go r (      Z  :_ ) = True
        go r (    S Z  :ns) = go r     ns
        go r ((S (S x)):ns) = go (x:r) ns
于 2015-02-07T19:05:32.833 に答える