FixPointDemo.hs

{-#LANGUAGE FlexibleInstances, FlexibleContexts #-}

--This could be sort of amusing in a presentation.

module Sets where

import Data.Set as S

data Fix f = Fix (f (Fix f))

type V = Fix Set

instance Show (Fix Set) where
        show (Fix x) = show x

instance Eq (Fix Set) where
        (Fix x) == (Fix y) = x == y

instance Ord (Fix Set) where
        (Fix x) <= (Fix y) = x <= y

ev :: V
ev = Fix empty

sv :: V -> V
sv x = Fix $ singleton x

uv :: V -> V -> V
uv (Fix x) (Fix y) = Fix $ union x y

elv :: V -> V -> Bool
elv x (Fix y) = x `elem` y

omegaList :: [V]
omegaList = ev : Prelude.map sv omegaList

omega :: V
omega = Fix (fromList omegaList)

omegaPlus :: V
omegaPlus = sv omega

aczel :: V
aczel = sv aczel

newtype DoublePowerSet a = Dps (a -> Bool -> Bool)

type NotASet = Fix DoublePowerSet