6

さて、これはfoldrを使用したフィルター関数の定義です。 

myFilter p xs = foldr step [] xs
    where step x ys | p x       = x : ys
                    | otherwise = ys

たとえば、私がこの関数を持っているとしましょう：

myFilter odd [1,2,3,4]

したがって、次のようになります。

foldr step [] [1,2,3,4]

そしてこれは

step 1 (foldr step [] [2,3,4])

そしてこれは

step 1 (step 2 (foldr step [] [3,4]))

そしてこれは

step 1 (step 2 (step 3 (foldr step [] [4])))

そしてこれは

step 1 (step 2 (step 3 (step 4 (foldr step [] []))))

そしてそうfoldr step [] []です[]：

step 1 (step 2 (step 3 (step 4 [])))

ここで、実際にstep関数に入ります。上から見た関数内
の定義は次のとおりです。stepmyFilter

step x ys | p x       = x : ys
          | otherwise = ys

pまた、それが実際にはoddこの例の関数であることを思い出してください。

さて、再び、私たちはここにいます：

step 1 (step 2 (step 3 (step 4 [])))

と

x = 4最も内側stepにあり、4奇妙ではないので、を返しysます。[]

だから今私たちはこれを手に入れます：

step 1 (step 2 (step 3 []))

さて、最も内側のstep、、x = 3は3奇数なので、を返しx:ysます。これは3 : []、です[3]。そして今、次のようになります。

step 1 (step 2 [3])

そして今、内側のstep、、は奇数ではないので、を返しx = 2ます。これは、であるため、次のようになります。2ys[3]

step 1 [3]

そして今x = 1、、、1は奇数なので、を返します。x : ysこれは1 : [3]、です[1,3]。

終わり ：-）。

私はすべての動きで正しいですか？
どうもありがとう ：-）。

psの定義は、第4章myFilterの本RealWorldHaskellからのものです。

4

3 に答える 3

6

これは、最初に読んだときに私には正しく見えます。

ただし、覚えておくべき重要なことは、遅延評価を達成するために、Haskellは実際には別の方法で物事を見るということです。言い換えれば、実際のシーケンスはより似ています

step 1 (step 2 (step 3 (step 4 [])))

になります

step 1 <block1>

これは

[1, <block1>]

次に、そのリストから次の要素をプルしようとすると、評価されます

[1, step 2 <block2>]

これは

[1, <block2>]

そして評価しようとしています

[1, step 3 (step 4 [])]

になる

[1, step 3 <block3>]

これは

[1, 3, <block3>]

など。これは私が理解するのに少し時間がかかりました。foldr「裏返し」から評価されているように見えますが、「裏返し」から評価されてfoldlいるのでfoldr、（それは）怠惰であるのに対し、foldl厳密であるというのは私には直感に反していました。しかし、私が上で概説したようにそれを考えるならば、それは理にかなっています（とにかく、私には）。

于 2010-02-02T16:32:43.177 に答える
4

遅延評価の順序を拡張するために：基本的に、Haskellは常に最初に関数を評価し、必要になるまで引数を調べません。

toの呼び出しの結果myFilterが使用される場合（たとえば、印刷される場合）、関数は次の順序で評価されます。

myFilter odd [1,2,3,4]

最初にmyFilter関数が評価されます。

foldr step [] [1,2,3,4]

foldrこれが最も外側の関数であり、評価されます。

step 1 (foldr step [] [2,3,4])

が奇数であるため、stepを生成して評価されます。11

1 : foldr step [] [2,3,4]

これで、結果リストの最初の要素が使用可能になり、呼び出し元の関数で使用できるようになりました。呼び出し元の関数が次の要素も使用している場合、評価は次のように続行されますfoldr。

1 : step 2 (foldr step [] [3,4])

2は偶数であるため、nowの評価ではstep新しい要素は生成されません。

1 : foldr step [] [3,4]

もう一度foldr：

1 : step 3 (foldr step [] [4])

今評価することstepは生成します3：

1 : 3 : foldr step [] [4]

評価foldr;

1 : 3 : step 4 (foldr step [] [])

そしてstepもう一度：

1 : 3 : foldr step [] []

最後foldrに、空のリストに評価されます。

1 : 3 : []
于 2010-02-02T19:34:51.503 に答える
2

一見すると、特定の例で実行した手順は、個々に正しく見えます。filterただし、両方とも無限のリストfoldrに有効に適用できることを指摘したいと思います。これは、Haskellに関する限り、ステップの順序が正しくないことを示しているはずです。

于 2010-02-02T16:33:56.700 に答える