フォルダーに関するフィルターの定義について、健全な等価推論を使用していますか?

Question

これは、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 関数。
ここに定義があります step の中で myFilter 関数、上から:

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, 、 そして 2 奇数ではないので戻ります ys, 、つまり [3], したがって、次のようになります。

step 1 [3]

そしていま、 x = 1, 、 そして 1 奇数なので戻ります x : ys, 、つまり 1 : [3], 、つまり [1,3].

終わり ：-）。

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

追記の定義 myFilter 本からです 現実世界のハスケル, 、第4章。

Answer 1

最初のリードで右私にはこのルックスます。

しかし覚えておくべき重要なことは、遅延評価を実現するために、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が怠惰になる「の外」から評価されているためように私には直感に反しました。しかし、あなたはそれを私が上記で概説したように考えるならば、それは（とにかく、私には）理にかなっています。

Answer 2

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

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

myFilter odd [1,2,3,4]

まず、 myFilter 関数が評価されます:

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

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

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

今 step を生み出して評価される 1, 、 以来 1 奇数です:

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

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

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

の評価 step 2 は偶数なので、新しい要素は生成されません。

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 : []

Answer 3

は一見すると、あなたは特定の例を見に撮影した手順を個別に修正します。あなたのステップの順序ははるかハスケルが懸念しているとして誤っていることを示しているはずである。のfilterとfoldrの両方が有効にの無限リストに適用することができることを指摘したいと思います。 P>