haskell - Haskell で無限リストをフィルタリングする方法

Question

重複の可能性:
無限リストの有限理解

なぜ ghci がこのコードを正しく計算できないのか理解できませんか?

[x | x <- [1..], x < 1000]

Ghci は最後の番号で停止するだけで、コマンド ラインでこのプロセスを中断して通常の状態に戻す必要があります。どうしたの？Haskell の遅延評価により、このコードが機能するはずです。

Answer 1

[x | x <- [1..], x < 1000]と同等filter (< 1000) [1..]です。あなたがtakeWhile (< 1000) [1..]代わりに欲しい。

filterでは、との違いは何takeWhileですか?

結果全体を評価しようとすると --- そしてそれを表示するために ghci が行うのは ---filter入力リストのすべての要素をテストして、出力リストに含めるかどうかを決定します。最初の千の要素の後？それはテストを続けます。filter突然遭遇しないとは知りません..., 12345, 12346, -7, 12348, ...。

別の見方をfilterすれば、入力リストの最後に到達すると、「出力リストはここで終了します」としか言えないということです。無限リストをフィードすると、出力リストのすべての要素が生成されたことを確認できません。そのため、ハングしているように見えます。

takeWhile一方、条件を満たさない要素に到達するとすぐに、出力リストを停止して終了します。

Answer 2

リスト内の 1000 未満のすべての数値を要求しただけです。リストがソートされていることはわかっていますが、アルゴリズムはこれを利用していません。コンパイラは、並べ替えられたデータを操作していることを自動的には認識しません。また、少なくとも 1000 の数値が表示されると、それ未満の数値は二度と表示されないと推測できません。

他の人が指摘しているようにtakeWhile (< 1000) [1..]、述語が要素に対して失敗した場合 (この場合は、少なくとも 1000 の数値が検出された場合) にリストの検査を具体的に停止することにより、リストがどれほど特別であるかについての知識を活用します。「単なるリスト」ではないため、これが利用可能な最適化であることに注意してください。[1..]これは特別なプロパティを持つリストです (特に、ソートされています)。

Answer 3

で無限を生成するため、[1..]このリストのすべての要素が条件でチェックされますx < 1000。これは、このリストの 1000 を超えるすべての要素がこの条件でチェックされることも意味します。

しかし、次のように関数を書くことができます:

myFilteredList :: [Int] -> [Int]
myFilteredList [] = []
myFilteredList (x:xs) = if x < 1000 then x: myFilteredList xs else []

より一般的な動作については、条件を引数として使用することもできます。

myFilteredList :: (a -> Bool) -> [a] -> [a]
myFilteredList cond [] = []
myFilteredList cond (x:xs) = if cond x then x: myFilteredList cond xs else []

myFilteredList (< 1000) [1..]

そして、これはまさに定義済み関数takeWhileが行うことです。(a -> Bool)条件とリストを引数として取り、条件[a]に適合するリストのプレフィックスを返します。の定義と同様に、myFilteredListリスト全体を処理した場合、または条件を保持しないリストの最初の要素に到達した場合、関数は終了します。

Answer 4

チェック x<1000 は、評価を停止するためではなく、フィルタリングされたリストに何を含めるかを決定するために使用されます。つまり、ghci に無限リストを指定すると、リストのすべての要素に対して x<1000 が実行されます。述語が True になるまで要素を取りたい場合は、takeWhile を使用します。Haskell が怠け者であることは問題ではありません。ghci が出力するため、フィルタリングされたリストが評価されます。これを回避したい場合は、let を使用します。

let l = [x | x <- [1..], x < 1000]