なぜHaskellのData.Setは無限集合をサポートしていないのですか？次のスニペットで

Question

：

import qualified Data.Set as Set 

data Nat = Zero | Succ Nat deriving (Eq, Show, Ord) 

instance Enum Nat where 
    pred (Succ x)  = x 
    succ x   = Succ x 
    toEnum 0   = Zero 
    toEnum x   = Succ (toEnum (x-1)) 
    fromEnum Zero  = 0 
    fromEnum (Succ x) = 1 + (fromEnum x) 

nats :: [Nat] 
nats = [Zero ..] 

natSet :: Set.Set Nat 
natSet = Set.fromList nats 

なぜ：

• elem (toEnum 100) nats == True

しかし

• Set.member (toEnum 100) natSet決して終わりませんか？

Answer 1

Set.fromListは怠惰ではないため、無限のリストを渡すと終了しません。しかし、natSetは必要になるまで構築されないので、Set.memberを実行したときにのみ通知されます。

たとえば、Set.null $ Set.fromList [0..]でも終了しません。

Answer 2

無限のセットを持つことはできません。これはSet.memberに影響するだけでなく、natSetが1つのステップ（さらにはSet.null）でも評価されるような操作を行うたびに、無限ループに入ります。

Answer 3

既存の回答で十分ですが、私はSetの動作について少し詳しく説明します。

あなたがすべての怠け者のセットを望んでいるように見えますNat s;あなたはすべてNatの無限のリストをとり、それにSet.toListを使用します。それはいいね;数学者はしばしば「すべての自然数の集合」という言葉で話します。問題は、Setの実装は、リストと同じように怠惰に対応していないことです。

セットの実装は、サイズに基づいて平衡二分木（または有界バランスの 木）

The docs for Data.Set

は、あなたが遅延し、リストからバイナリツリーを構築したいとし。ツリーのより深いトラバーサルが必要な場合にのみ、リストの要素がツリーに挿入されます。だから、あなたは100が木の中にあるかどうか尋ねる。一度に1つずつ、ツリーに1〜99の数字を追加します。そして最後に100をツリーに追加し、100が実際にツリーの要素であることを発見します。しかし、私たちがしたことに気づく。私たちはちょうど怠け者リストの順序通りのトラバーサルを実行しました！だから最初の想像上のLazyTree.containsは、とほぼ同じ複雑さを持ちます（O（1）の挿入を仮定します）。これは、単純なバイナリツリーの悪い仮定であり、O（log n） ）。バランスを取らないと、私たちのツリーは非常に片寄ってしまいます（1から100までの数字を順番に追加するので、各ブランチの右の子の下に大きなリンクリストが表示されます）。しかし、トラバーサルの間にツリーバランシングを使用すると、再びトラバーサルを開始する場所を知ることは難しくなります。少なくともそれは直ちに直感的ではありません。

tl; dr：nobody（afaik）はまだ良い怠惰なセットを作っています。無限の集合は今のところ無限リストとして表現されやすくなります。

Answer 4

のは、我々は無限のセットに対応するためにGHC's Set codeを適応させるときに何が起こるか見てみましょう：

module InfSet where 

data InfSet a = Bin a (InfSet a) (InfSet a) 

-- create an infinite set by unfolding a value 
ofUnfold :: (x -> (x, a, x)) -> x -> InfSet a 
ofUnfold f x = 
    let (lx,a,rx) = f x 
     l = ofUnfold f lx 
     r = ofUnfold f rx 
    in Bin a l r 

-- check for membership in the infinite set 
member :: Ord a => a -> InfSet a -> Bool 
member x (Bin y l r) = case compare x y of 
         LT -> member x l 
         GT -> member x r 
         EQ -> True  

-- construct an infinite set representing a range of numbers 
range :: Fractional a => (a, a) -> InfSet a 
range = ofUnfold $ \(lo,hi) -> 
      let mid = (hi+lo)/2 
      in ((lo, mid), mid, (mid, hi)) 

注意私が代わりに単一の値を展開する機能ofUnfoldをどう定義するか、代わりに無限のリストから無限集合を構築する、 無限のリストに。 これは、両方のブランチを遅延並列に構築することを可能にします（別のブランチを構築する前に、ブランチを完成させる必要はありません。 ）。

のは、それに旋回を与えてみましょう：

ghci> :l InfSet 
[1 of 1] Compiling InfSet   (InfSet.hs, interpreted) 
Ok, modules loaded: InfSet. 
ghci> let r = range (0,128) 
ghci> member 64 r 
True 
ghci> member 63 r 
True 
ghci> member 62 r 
True 
ghci> member (1/2) r 
True 
ghci> member (3/4) r 
True 

まあ、それが動作しているようです。 Setの外で値を試してみたらどうでしょうか？

ghci> member 129 r 
^CInterrupted. 

これは実行され、実行され、終了しません。 inifiniteセットには停止するブランチがありません。 検索が終わることはありません。私たちは、何とか元の範囲を確認することができ、それが個別素子の無限集合のための実用的ではありません。

ghci> let ex = ofUnfold (\f -> (f . (LT:), f [EQ], f . (GT:))) id 
ghci> :t ex 
ex :: InfSet [Ordering] 
ghci> member [EQ] ex 
True 
ghci> member [LT,EQ] ex 
True 
ghci> member [EQ,LT] ex 
^CInterrupted. 

だから、無限のセットが可能ですが、私は彼らが便利しているかわかりません。

Answer 5

同じように感じたので、無限リストで動作するセットを追加しました。しかし、彼らはソートする必要があるので、私のアルゴリズムは、いつもっと探しを止めることが知られていました。

Prelude> import Data.Set.Lazy 
Prelude Data.Set.Lazy> natset = fromList [1..] 
Prelude Data.Set.Lazy> 100 `member` natset 
True 
Prelude Data.Set.Lazy> (-10) `member` natset 
False 

それがハックします。 http://hackage.haskell.org/package/lazyset-0.1.0.0/docs/Data-Set-Lazy.html