module Feldspar.Set where
class Eq a => Set a
where
empty :: a
universal :: a
(\/) :: a -> a -> a
(/\) :: a -> a -> a
instance Set ()
where
empty = ()
universal = ()
() \/ () = ()
() /\ () = ()
instance (Set a, Set b) => Set (a,b)
where
empty = (empty,empty)
universal = (universal,universal)
(a1,a2) \/ (b1,b2) = (a1 \/ b1, a2 \/ b2)
(a1,a2) /\ (b1,b2) = (a1 /\ b1, a2 /\ b2)
instance (Set a, Set b, Set c) => Set (a,b,c)
where
empty = (empty,empty,empty)
universal = (universal,universal,universal)
(a1,a2,a3) \/ (b1,b2,b3) = (a1 \/ b1, a2 \/ b2, a3 \/ b3)
(a1,a2,a3) /\ (b1,b2,b3) = (a1 /\ b1, a2 /\ b2, a3 /\ b3)
instance (Set a, Set b, Set c, Set d) => Set (a,b,c,d)
where
empty = (empty,empty,empty,empty)
universal = (universal,universal,universal,universal)
(a1,a2,a3,a4) \/ (b1,b2,b3,b4) = (a1 \/ b1, a2 \/ b2, a3 \/ b3, a4 \/ b4)
(a1,a2,a3,a4) /\ (b1,b2,b3,b4) = (a1 /\ b1, a2 /\ b2, a3 /\ b3, a4 /\ b4)
unions :: Set a => [a] -> a
unions = foldr (\/) empty
intersections :: Set a => [a] -> a
intersections = foldr (/\) universal
fixedPoint :: Set a => (a -> a) -> a -> a
fixedPoint f a | fa == a = fa
| otherwise = fixedPoint f fa
where fa = f a \/ a
indexedFixedPoint :: Set a => (Int -> a -> a) -> a -> (a,Int)
indexedFixedPoint f a = go 0 f a
where go i f a | fa == a = (fa,i)
| otherwise = go (i+1) f fa
where fa = f i a \/ a
type Widening a = (Int -> a -> a) -> (Int -> a -> a)
cutOffAt :: Set a => Int -> Widening a
cutOffAt n f i a | i >= n = universal
| otherwise = f i a