0_GSet.hs

module GSet where

import Prelude hiding (lookup)
import Test.Hspec

data GSet a = GSet [a]

emptySet :: GSet a
emptySet = GSet []

add :: a -> GSet a -> GSet a
add el (GSet ls) = GSet (el : ls)

lookup :: Eq a => a -> GSet a -> Bool
lookup el (GSet ls) = el `elem` ls

instance Eq a => Eq (GSet a) where
  (GSet ls) == (GSet lls) =
    all (\l -> l `elem` lls) ls &&
    all (\ll -> ll `elem` ls) lls

merge :: GSet a -> GSet a -> GSet a
merge (GSet xs) (GSet ys) = GSet (xs ++ ys)

-- tests
main :: IO ()
main = hspec $ do
  describe "GSet" $ do
    it "works" $ do
      let a = add 1 emptySet
      lookup 1 a `shouldBe` True
      lookup 2 a `shouldBe` False

      let b = add 5 a
      lookup 1 b `shouldBe` True
      lookup 5 b `shouldBe` True
      lookup 2 b `shouldBe` False

      let c = add 1 (add 1 emptySet)
      a == c `shouldBe` True
      a == b `shouldBe` False

      let d = merge c (add 7 (add 8 emptySet))
      lookup 1 d `shouldBe` True
      lookup 7 d `shouldBe` True
      lookup 2 d `shouldBe` False

1_TwoPSet.hs

module TwoPSet where

import Prelude hiding (lookup)
import Test.Hspec

data TwoPSet a = TwoPSet [a] [a]

emptySet :: TwoPSet a
emptySet = TwoPSet [] []

add :: a -> TwoPSet a -> TwoPSet a
add el (TwoPSet ls rs) = TwoPSet (el : ls) rs

remove :: a -> TwoPSet a -> TwoPSet a
remove el (TwoPSet ls rs) = TwoPSet ls (el : rs)

lookup :: Eq a => a -> TwoPSet a -> Bool
lookup el (TwoPSet ls rs)
  | el `elem` rs = False
  | el `elem` ls = True
  | otherwise = False

instance Eq a => Eq (TwoPSet a) where
  (TwoPSet ls rs) == (TwoPSet lls rrs) =
    all (\l -> l `elem` lls) ls &&
    all (\ll -> ll `elem` ls) lls &&
    all (\r -> r `elem` rrs) rs &&
    all (\rr -> rr `elem` rs) rrs

merge :: TwoPSet a -> TwoPSet a -> TwoPSet a
merge (TwoPSet ls rs) (TwoPSet lls rrs) = TwoPSet (ls ++ lls) (rs ++ rrs)

-- tests
main :: IO ()
main = hspec $ do
  describe "TwoPSet" $ do
    it "works like a GSet" $ do
      let a = add 1 emptySet
      lookup 1 a `shouldBe` True
      lookup 2 a `shouldBe` False

      let b = add 5 a
      lookup 1 b `shouldBe` True
      lookup 5 b `shouldBe` True
      lookup 2 b `shouldBe` False

      let c = add 1 (add 1 emptySet)
      a == c `shouldBe` True
      a == b `shouldBe` False

      let d = merge c (add 7 (add 8 emptySet))
      lookup 1 d `shouldBe` True
      lookup 7 d `shouldBe` True
      lookup 2 d `shouldBe` False

    it "supports removing elements" $ do
      let a = remove 1 (add 1 emptySet)
      lookup 1 a `shouldBe` False

      let b = add 1 a
      lookup 1 b `shouldBe` False

      let c = merge (remove 1 emptySet) (add 1 emptySet)
      lookup 1 c `shouldBe` False