The `Util' type

Stuff that has been useful to use in writing the compiler. Don't be too surprised if this stuff moves/gets-renamed/etc.

-- general list processing
forall          :: (a -> Bool) -> [a] -> Bool
exists          :: (a -> Bool) -> [a] -> Bool
zipEqual        :: [a] -> [b] -> [(a,b)]
nOfThem         :: Int -> a -> [a]
lengthExceeds   :: [a] -> Int -> Bool
isSingleton     :: [a] -> Bool

-- association lists
assoc       :: Eq a => String -> [(a, b)] -> a -> b

-- duplicate handling
hasNoDups    :: Eq a => [a] -> Bool
equivClasses :: (a -> a -> _CMP_TAG) -> [a] -> [[a]]
runs         :: (a -> a -> Bool)     -> [a] -> [[a]]
removeDups   :: (a -> a -> _CMP_TAG) -> [a] -> ([a], [[a]])

-- sorting (don't complain of no choice...)
quicksort          :: (a -> a -> Bool)     -> [a] -> [a]
sortLt             :: (a -> a -> Bool)     -> [a] -> [a]
stableSortLt       :: (a -> a -> Bool)     -> [a] -> [a]
mergesort          :: (a -> a -> _CMP_TAG) -> [a] -> [a]
mergeSort          :: Ord a => [a] -> [a]
naturalMergeSort   :: Ord a => [a] -> [a]
mergeSortLe        :: Ord a => [a] -> [a]
naturalMergeSortLe :: Ord a => [a] -> [a]

-- transitive closures
transitiveClosure :: (a -> [a])         -- Successor function
                  -> (a -> a -> Bool)   -- Equality predicate
                  -> [a] 
                  -> [a]                -- The transitive closure

-- accumulating (Left, Right, Bi-directional)
mapAccumL :: (acc -> x -> (acc, y))
                        -- Function of elt of input list and
                        -- accumulator, returning new accumulator and
                        -- elt of result list
          -> acc        -- Initial accumulator
          -> [x]        -- Input list
          -> (acc, [y]) -- Final accumulator and result list

mapAccumR :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

mapAccumB :: (accl -> accr -> x -> (accl, accr,y))
          -> accl -> accr -> [x]
          -> (accl, accr, [y])

-- comparisons
cmpString :: String -> String -> _CMP_TAG

-- this type is built-in
data _CMP_TAG = _LT | _EQ | _GT

-- pairs
applyToPair :: ((a -> c), (b -> d)) -> (a, b) -> (c, d)
applyToFst  :: (a -> c) -> (a, b) -> (c, b)
applyToSnd  :: (b -> d) -> (a, b) -> (a, d)
foldPair    :: (a->a->a, b->b->b) -> (a, b) -> [(a, b)] -> (a, b)
unzipWith   :: (a -> b -> c) -> [(a, b)] -> [c]