SetGist.hs

module Set where

import Data.List (nub)
--import qualified Data.List.NonEmpty as NE
--import Bag

-- a set is a functor with a splitter

class Applicative f => Set f where
  split :: f a -> (f a, f a) -- non-deterministic (instance-defined) monotonic splitter
  join :: Eq a => f a -> f a -> f a
  empty :: f a -> Bool

-- Laws:
--  a) uncurry join . split == id
--  b) join a a = a
--  c) empty . snd . split implies that it was either empty or singleton

singleton :: Set f => f a -> Bool
singleton s = case split s of
                (some, rest) -> empty rest && not (empty some)


instance Set [] where
  empty [] = True
  empty _ = False
  split [] = ([], [])
  split (h:t) = ([h], t)
  join as bs = nub (as ++ bs)


--instance Set Bag