-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Generic support for list-like structures -- @package ListLike @version 4.2.0 -- | Generic tools for data structures that can be folded. -- -- Written by John Goerzen, jgoerzen@complete.org module Data.ListLike.FoldableLL -- | This is the primary class for structures that are to be considered -- foldable. A minimum complete definition provides foldl and -- foldr. -- -- Instances of FoldableLL can be folded, and can be many and -- varied. -- -- These functions are used heavily in Data.ListLike. class FoldableLL full item | full -> item where foldl' f a xs = foldr f' id xs a where f' x k z = k $! f z x foldl1 f xs = fromMaybe (error "fold1: empty structure") (foldl mf Nothing xs) where mf Nothing y = Just y mf (Just x) y = Just (f x y) foldr' f a xs = foldl f' id xs a where f' k x z = k $! f x z foldr1 f xs = fromMaybe (error "foldr1: empty structure") (foldr mf Nothing xs) where mf x Nothing = Just x mf x (Just y) = Just (f x y) foldl :: FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl' :: FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl1 :: FoldableLL full item => (item -> item -> item) -> full -> item foldr :: FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr' :: FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr1 :: FoldableLL full item => (item -> item -> item) -> full -> item -- | Combine the elements of a structure using a monoid. fold = -- foldMap id fold :: (FoldableLL full item, Monoid item) => full -> item -- | Map each element to a monoid, then combine the results foldMap :: (FoldableLL full item, Monoid m) => (item -> m) -> full -> m -- | Monadic version of left fold, similar to foldM. foldM :: (Monad m, FoldableLL full item) => (a -> item -> m a) -> a -> full -> m a -- | Evaluate each action, ignoring the results. Same as mapM_ -- id. sequence_ :: (Monad m, FoldableLL full (m item)) => full -> m () -- | A map in monad space, discarding results. mapM_ :: (Monad m, FoldableLL full item) => (item -> m b) -> full -> m () instance FoldableLL [a] a -- | Generic operations over list-like structures -- -- Written by John Goerzen, jgoerzen@complete.org module Data.ListLike.Base -- | The class implementing list-like functions. -- -- It is worth noting that types such as Map can be instances of -- ListLike. Due to their specific ways of operating, they may not -- behave in the expected way in some cases. For instance, cons -- may not increase the size of a map if the key you have given is -- already in the map; it will just replace the value already there. -- -- Implementators must define at least: -- -- class (FoldableLL full item, Monoid full) => ListLike full item | full -> item where empty = mempty cons item l = append (singleton item) l snoc l item = append l (singleton item) append = mappend last l = case genericLength l of { (0 :: Integer) -> error "Called last on empty list" 1 -> head l _ -> last (tail l) } init l | null l = error "init: empty list" | null xs = empty | otherwise = cons (head l) (init xs) where xs = tail l null x = genericLength x == (0 :: Integer) length = genericLength map func inp | null inp = empty | otherwise = cons (func (head inp)) (map func (tail inp)) rigidMap = map reverse l = rev l empty where rev rl a | null rl = a | otherwise = rev (tail rl) (cons (head rl) a) intersperse sep l | null l = empty | null xs = singleton x | otherwise = cons x (cons sep (intersperse sep xs)) where x = head l xs = tail l concat = fold concatMap = foldMap rigidConcatMap = concatMap any p = getAny . foldMap (Any . p) all p = getAll . foldMap (All . p) maximum = foldr1 max minimum = foldr1 min replicate = genericReplicate take = genericTake drop = genericDrop splitAt = genericSplitAt takeWhile func l | null l = empty | func x = cons x (takeWhile func (tail l)) | otherwise = empty where x = head l dropWhile func l | null l = empty | func (head l) = dropWhile func (tail l) | otherwise = l dropWhileEnd func = foldr (\ x xs -> if func x && null xs then empty else cons x xs) empty span func l | null l = (empty, empty) | func x = (cons x ys, zs) | otherwise = (empty, l) where (ys, zs) = span func (tail l) x = head l break p = span (not . p) group = groupBy (==) inits l | null l = singleton empty | otherwise = append (singleton empty) (map (cons (head l)) theinits) where theinits = asTypeOf (inits (tail l)) [l] tails l | null l = singleton empty | otherwise = cons l (tails (tail l)) isPrefixOf needle haystack | null needle = True | null haystack = False | otherwise = (head needle) == (head haystack) && isPrefixOf (tail needle) (tail haystack) isSuffixOf needle haystack = isPrefixOf (reverse needle) (reverse haystack) isInfixOf needle haystack = any (isPrefixOf needle) thetails where thetails = asTypeOf (tails haystack) [haystack] elem i = any (== i) notElem i = all (/= i) find f l = case findIndex f l of { Nothing -> Nothing Just x -> Just (index l x) } filter func l | null l = empty | func (head l) = cons (head l) (filter func (tail l)) | otherwise = filter func (tail l) partition p xs = (filter p xs, filter (not . p) xs) index l i | null l = error "index: index not found" | i < 0 = error "index: index must be >= 0" | i == 0 = head l | otherwise = index (tail l) (i - 1) elemIndex e l = findIndex (== e) l elemIndices i l = findIndices (== i) l findIndex f = listToMaybe . findIndices f findIndices p xs = map snd $ filter (p . fst) $ thezips where thezips = asTypeOf (zip xs [0 .. ]) [(head xs, 0 :: Int)] sequence l = foldr func (return empty) l where func litem results = do { x <- litem; xs <- results; return (cons x xs) } mapM func l = sequence mapresult where mapresult = asTypeOf (map func l) [] rigidMapM = mapM nub = nubBy (==) delete = deleteBy (==) deleteFirsts = foldl (flip delete) union = unionBy (==) intersect = intersectBy (==) sort = sortBy compare insert = insertBy compare toList = fromListLike fromList [] = empty fromList (x : xs) = cons x (fromList xs) fromListLike = map id nubBy f l = nubBy' l (empty :: full) where nubBy' ys xs | null ys = empty | any (f (head ys)) xs = nubBy' (tail ys) xs | otherwise = let y = head ys in cons y (nubBy' (tail ys) (cons y xs)) deleteBy func i l | null l = empty | otherwise = if func i (head l) then tail l else cons (head l) (deleteBy func i (tail l)) deleteFirstsBy func = foldl (flip (deleteBy func)) unionBy func x y = append x $ foldl (flip (deleteBy func)) (nubBy func y) x intersectBy func xs ys = filter (\ x -> any (func x) ys) xs groupBy eq l | null l = empty | otherwise = cons (cons x ys) (groupBy eq zs) where (ys, zs) = span (eq x) xs x = head l xs = tail l sortBy cmp = foldr (insertBy cmp) empty insertBy cmp x ys | null ys = singleton x | otherwise = case cmp x (head ys) of { GT -> cons (head ys) (insertBy cmp x (tail ys)) _ -> cons x ys } genericLength l = calclen 0 l where calclen !accum cl = if null cl then accum else calclen (accum + 1) (tail cl) genericTake n l | n <= 0 = empty | null l = empty | otherwise = cons (head l) (genericTake (n - 1) (tail l)) genericDrop n l | n <= 0 = l | null l = l | otherwise = genericDrop (n - 1) (tail l) genericSplitAt n l = (genericTake n l, genericDrop n l) genericReplicate count x | count <= 0 = empty | otherwise = map (\ _ -> x) [1 .. count] empty :: ListLike full item => full singleton :: ListLike full item => item -> full cons :: ListLike full item => item -> full -> full snoc :: ListLike full item => full -> item -> full append :: ListLike full item => full -> full -> full head :: ListLike full item => full -> item last :: ListLike full item => full -> item tail :: ListLike full item => full -> full init :: ListLike full item => full -> full null :: ListLike full item => full -> Bool length :: ListLike full item => full -> Int map :: (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' rigidMap :: ListLike full item => (item -> item) -> full -> full reverse :: ListLike full item => full -> full intersperse :: ListLike full item => item -> full -> full concat :: (ListLike full item, ListLike full' full, Monoid full) => full' -> full concatMap :: (ListLike full item, ListLike full' item') => (item -> full') -> full -> full' rigidConcatMap :: ListLike full item => (item -> full) -> full -> full any :: ListLike full item => (item -> Bool) -> full -> Bool all :: ListLike full item => (item -> Bool) -> full -> Bool maximum :: (ListLike full item, Ord item) => full -> item minimum :: (ListLike full item, Ord item) => full -> item replicate :: ListLike full item => Int -> item -> full take :: ListLike full item => Int -> full -> full drop :: ListLike full item => Int -> full -> full splitAt :: ListLike full item => Int -> full -> (full, full) takeWhile :: ListLike full item => (item -> Bool) -> full -> full dropWhile :: ListLike full item => (item -> Bool) -> full -> full dropWhileEnd :: ListLike full item => (item -> Bool) -> full -> full span :: ListLike full item => (item -> Bool) -> full -> (full, full) break :: ListLike full item => (item -> Bool) -> full -> (full, full) group :: (ListLike full item, ListLike full' full, Eq item) => full -> full' inits :: (ListLike full item, ListLike full' full) => full -> full' tails :: (ListLike full item, ListLike full' full) => full -> full' isPrefixOf :: (ListLike full item, Eq item) => full -> full -> Bool isSuffixOf :: (ListLike full item, Eq item) => full -> full -> Bool isInfixOf :: (ListLike full item, Eq item) => full -> full -> Bool elem :: (ListLike full item, Eq item) => item -> full -> Bool notElem :: (ListLike full item, Eq item) => item -> full -> Bool find :: ListLike full item => (item -> Bool) -> full -> Maybe item filter :: ListLike full item => (item -> Bool) -> full -> full partition :: ListLike full item => (item -> Bool) -> full -> (full, full) index :: ListLike full item => full -> Int -> item elemIndex :: (ListLike full item, Eq item) => item -> full -> Maybe Int elemIndices :: (ListLike full item, Eq item, ListLike result Int) => item -> full -> result findIndex :: ListLike full item => (item -> Bool) -> full -> Maybe Int findIndices :: (ListLike full item, ListLike result Int) => (item -> Bool) -> full -> result sequence :: (ListLike full item, Monad m, ListLike fullinp (m item)) => fullinp -> m full mapM :: (ListLike full item, Monad m, ListLike full' item') => (item -> m item') -> full -> m full' rigidMapM :: (ListLike full item, Monad m) => (item -> m item) -> full -> m full nub :: (ListLike full item, Eq item) => full -> full delete :: (ListLike full item, Eq item) => item -> full -> full deleteFirsts :: (ListLike full item, Eq item) => full -> full -> full union :: (ListLike full item, Eq item) => full -> full -> full intersect :: (ListLike full item, Eq item) => full -> full -> full sort :: (ListLike full item, Ord item) => full -> full insert :: (ListLike full item, Ord item) => item -> full -> full toList :: ListLike full item => full -> [item] fromList :: ListLike full item => [item] -> full fromListLike :: (ListLike full item, ListLike full' item) => full -> full' nubBy :: ListLike full item => (item -> item -> Bool) -> full -> full deleteBy :: ListLike full item => (item -> item -> Bool) -> item -> full -> full deleteFirstsBy :: ListLike full item => (item -> item -> Bool) -> full -> full -> full unionBy :: ListLike full item => (item -> item -> Bool) -> full -> full -> full intersectBy :: ListLike full item => (item -> item -> Bool) -> full -> full -> full groupBy :: (ListLike full item, ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full' sortBy :: ListLike full item => (item -> item -> Ordering) -> full -> full insertBy :: ListLike full item => (item -> item -> Ordering) -> item -> full -> full genericLength :: (ListLike full item, Num a) => full -> a genericTake :: (ListLike full item, Integral a) => a -> full -> full genericDrop :: (ListLike full item, Integral a) => a -> full -> full genericSplitAt :: (ListLike full item, Integral a) => a -> full -> (full, full) genericReplicate :: (ListLike full item, Integral a) => a -> item -> full -- | An extension to ListLike for those data types that are capable -- of dealing with infinite lists. Some ListLike functions are -- capable of working with finite or infinite lists. The functions here -- require infinite list capability in order to work at all. class ListLike full item => InfiniteListLike full item | full -> item where iterate f x = cons x (iterate f (f x)) repeat x = xs where xs = cons x xs cycle xs | null xs = error "ListLike.cycle: empty list" | otherwise = xs' where xs' = append xs xs' iterate :: InfiniteListLike full item => (item -> item) -> item -> full repeat :: InfiniteListLike full item => item -> full cycle :: InfiniteListLike full item => full -> full -- | Takes two lists and returns a list of corresponding pairs. zip :: (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result -- | Takes two lists and combines them with a custom combining function zipWith :: (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result -- | Evaluate each action, ignoring the results. Same as mapM_ -- id. sequence_ :: (Monad m, FoldableLL full (m item)) => full -> m () instance ListLike [a] a -- | String-like functions -- -- Written by John Goerzen, jgoerzen@complete.org module Data.ListLike.String -- | An extension to ListLike for those data types that are similar -- to a String. Minimal complete definition is toString and -- fromString. class StringLike s where lines = myLines words = myWords unlines = myUnlines unwords = myUnwords toString :: StringLike s => s -> String fromString :: StringLike s => String -> s lines :: (StringLike s, ListLike full s) => s -> full words :: (StringLike s, ListLike full s) => s -> full unlines :: (StringLike s, ListLike full s) => full -> s unwords :: (StringLike s, ListLike full s) => full -> s -- | Utilities for ListLike and friends. More functions similar to -- List but not part of the main typeclass. -- -- Written by John Goerzen, jgoerzen@complete.org module Data.ListLike.Utils -- | Returns True if all elements are True and :: ListLike full Bool => full -> Bool -- | Returns True if any element is True or :: ListLike full Bool => full -> Bool -- | The sum of the list sum :: (Num a, ListLike full a) => full -> a -- | The product of the list product :: (Num a, ListLike full a) => full -> a -- | Takes two lists and returns a list of corresponding pairs. zip :: (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result -- | Takes two lists and combines them with a custom combining function zipWith :: (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result -- | Converts a list of pairs into two separate lists of elements unzip :: (ListLike full (itema, itemb), ListLike ra itema, ListLike rb itemb) => full -> (ra, rb) -- | Evaluate each action, ignoring the results. Same as mapM_ -- id. sequence_ :: (Monad m, FoldableLL full (m item)) => full -> m () -- | Converts to a MonadPlus instance toMonadPlus :: (MonadPlus m, ListLike full a) => full -> m (a, full) -- | List-like destructor (like Data.Maybe.maybe) list :: ListLike full a => b -> (a -> full -> b) -> full -> b -- | String-like functions -- -- Written by John Goerzen, jgoerzen@complete.org module Data.ListLike.IO -- | An extension to ListLike for those data types that support I/O. -- These functions mirror those in System.IO for the most part. -- They also share the same names; see the comments in -- Data.ListLike for help importing them. -- -- Note that some types may not be capable of lazy reading or writing. -- Therefore, the usual semantics of System.IO functions regarding -- laziness may or may not be available from a particular implementation. -- -- Minimal complete definition: -- -- class ListLike full item => ListLikeIO full item | full -> item where hPutStrLn fp x = do { hPutStr fp x; hPutStrLn fp "" } getLine = hGetLine stdin getContents = hGetContents stdin putStr = hPutStr stdout putStrLn = hPutStrLn stdout interact func = do { c <- getContents; putStr (func c) } readFile fn = do { fp <- openFile fn ReadMode; hGetContents fp } writeFile fn x = do { fp <- openFile fn WriteMode; hPutStr fp x; hClose fp } appendFile fn x = do { fp <- openFile fn AppendMode; hPutStr fp x; hClose fp } hGetLine :: ListLikeIO full item => Handle -> IO full hGetContents :: ListLikeIO full item => Handle -> IO full hGet :: ListLikeIO full item => Handle -> Int -> IO full hGetNonBlocking :: ListLikeIO full item => Handle -> Int -> IO full hPutStr :: ListLikeIO full item => Handle -> full -> IO () hPutStrLn :: ListLikeIO full item => Handle -> full -> IO () getLine :: ListLikeIO full item => IO full getContents :: ListLikeIO full item => IO full putStr :: ListLikeIO full item => full -> IO () putStrLn :: ListLikeIO full item => full -> IO () interact :: ListLikeIO full item => (full -> full) -> IO () readFile :: ListLikeIO full item => FilePath -> IO full writeFile :: ListLikeIO full item => FilePath -> full -> IO () appendFile :: ListLikeIO full item => FilePath -> full -> IO () -- | Newtype wrapper for ByteString to enable a Char-based interface -- Re-exported by Data.ListLike. -- -- Written by John Lato, jwlato@gmail.com module Data.ListLike.CharString -- | Newtype wrapper around Data.ByteString.Char8.ByteString, this allows -- for ListLike instances with Char elements. newtype CharString CS :: ByteString -> CharString unCS :: CharString -> ByteString -- | Newtype wrapper around Data.ByteString.Lazy.Char8.ByteString, this -- allows for ListLike instances with Char elements. newtype CharStringLazy CSL :: ByteString -> CharStringLazy unCSL :: CharStringLazy -> ByteString instance Read CharString instance Show CharString instance Eq CharString instance Ord CharString instance Read CharStringLazy instance Show CharStringLazy instance Eq CharStringLazy instance Ord CharStringLazy instance StringLike CharStringLazy instance ListLikeIO CharStringLazy Char instance ListLike CharStringLazy Char instance FoldableLL CharStringLazy Char instance Monoid CharStringLazy instance StringLike CharString instance ListLikeIO CharString Char instance ListLike CharString Char instance FoldableLL CharString Char instance Monoid CharString -- | ListLike instances for DList module Data.ListLike.DList instance StringLike (DList Char) instance ListLike (DList a) a instance FoldableLL (DList a) a -- | ListLike instances for FMList module Data.ListLike.FMList instance MonadZip FMList instance StringLike (FMList Char) instance IsString (FMList Char) instance InfiniteListLike (FMList a) a instance ListLike (FMList a) a instance FoldableLL (FMList a) a module Data.ListLike.Text.Text instance StringLike Text instance ListLikeIO Text Char instance ListLike Text Char instance FoldableLL Text Char module Data.ListLike.Text.TextLazy instance StringLike Text instance ListLikeIO Text Char instance ListLike Text Char instance FoldableLL Text Char module Data.ListLike.Text module Data.ListLike.Vector.Storable instance StringLike (Vector Char) instance Storable a => ListLike (Vector a) a instance Storable a => FoldableLL (Vector a) a module Data.ListLike.Vector.Unboxed instance StringLike (Vector Char) instance Unbox a => ListLike (Vector a) a instance Unbox a => FoldableLL (Vector a) a module Data.ListLike.Vector.Vector instance StringLike (Vector Char) instance ListLike (Vector a) a instance FoldableLL (Vector a) a -- | ListLike instances for several Data.Vector types. The -- Data.ListLike.Vector.Generic instances are not exported from -- this module in order to prevent collisions. module Data.ListLike.Vector -- | Instances of ListLike and related classes. Re-exported by -- Data.ListLike. -- -- Written by John Goerzen, jgoerzen@complete.org module Data.ListLike.Instances instance ListLike (Seq a) a instance FoldableLL (Seq a) a instance StringLike (Seq Char) instance ListLikeIO (Seq Char) Char instance (Integral i, Ix i) => ListLikeIO (Array i Char) Char instance (Integral i, Ix i) => StringLike (Array i Char) instance (Integral i, Ix i) => ListLike (Array i e) e instance (Integral i, Ix i) => Monoid (Array i e) instance Ix i => FoldableLL (Array i e) e instance StringLike ByteString instance ListLikeIO ByteString Word8 instance ListLike ByteString Word8 instance FoldableLL ByteString Word8 instance StringLike ByteString instance ListLikeIO ByteString Word8 instance ListLike ByteString Word8 instance FoldableLL ByteString Word8 instance InfiniteListLike [a] a instance StringLike String instance ListLikeIO String Char -- | ListLike instance for any type supporting the -- Data.Vector.Generic interface. To avoid collisions with other -- Vector instances, this module must be imported directly. module Data.ListLike.Vector.Generic instance [overlap ok] (Eq (v Char), Vector v Char) => StringLike (v Char) instance [overlap ok] (Monoid (v a), Eq (v a), Vector v a) => ListLike (v a) a instance [overlap ok] Vector v a => FoldableLL (v a) a -- | Generic operations over list-like structures -- -- Written by John Goerzen, jgoerzen@complete.org -- -- Please start with the introduction at Data.ListLike#intro. module Data.ListLike -- | Returns True if all elements are True and :: ListLike full Bool => full -> Bool -- | Returns True if any element is True or :: ListLike full Bool => full -> Bool -- | The sum of the list sum :: (Num a, ListLike full a) => full -> a -- | The product of the list product :: (Num a, ListLike full a) => full -> a -- | Combine the elements of a structure using a monoid. fold = -- foldMap id fold :: (FoldableLL full item, Monoid item) => full -> item -- | Map each element to a monoid, then combine the results foldMap :: (FoldableLL full item, Monoid m) => (item -> m) -> full -> m -- | Takes two lists and returns a list of corresponding pairs. zip :: (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result -- | Takes two lists and combines them with a custom combining function zipWith :: (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result -- | Converts a list of pairs into two separate lists of elements unzip :: (ListLike full (itema, itemb), ListLike ra itema, ListLike rb itemb) => full -> (ra, rb) -- | Evaluate each action, ignoring the results. Same as mapM_ -- id. sequence_ :: (Monad m, FoldableLL full (m item)) => full -> m () -- | A map in monad space, discarding results. mapM_ :: (Monad m, FoldableLL full item) => (item -> m b) -> full -> m () -- | An extension to ListLike for those data types that support I/O. -- These functions mirror those in System.IO for the most part. -- They also share the same names; see the comments in -- Data.ListLike for help importing them. -- -- Note that some types may not be capable of lazy reading or writing. -- Therefore, the usual semantics of System.IO functions regarding -- laziness may or may not be available from a particular implementation. -- -- Minimal complete definition: -- -- class ListLike full item => ListLikeIO full item | full -> item where hPutStrLn fp x = do { hPutStr fp x; hPutStrLn fp "" } getLine = hGetLine stdin getContents = hGetContents stdin putStr = hPutStr stdout putStrLn = hPutStrLn stdout interact func = do { c <- getContents; putStr (func c) } readFile fn = do { fp <- openFile fn ReadMode; hGetContents fp } writeFile fn x = do { fp <- openFile fn WriteMode; hPutStr fp x; hClose fp } appendFile fn x = do { fp <- openFile fn AppendMode; hPutStr fp x; hClose fp } hGetLine :: ListLikeIO full item => Handle -> IO full hGetContents :: ListLikeIO full item => Handle -> IO full hGet :: ListLikeIO full item => Handle -> Int -> IO full hGetNonBlocking :: ListLikeIO full item => Handle -> Int -> IO full hPutStr :: ListLikeIO full item => Handle -> full -> IO () hPutStrLn :: ListLikeIO full item => Handle -> full -> IO () getLine :: ListLikeIO full item => IO full getContents :: ListLikeIO full item => IO full putStr :: ListLikeIO full item => full -> IO () putStrLn :: ListLikeIO full item => full -> IO () interact :: ListLikeIO full item => (full -> full) -> IO () readFile :: ListLikeIO full item => FilePath -> IO full writeFile :: ListLikeIO full item => FilePath -> full -> IO () appendFile :: ListLikeIO full item => FilePath -> full -> IO () -- | Newtype wrapper around Data.ByteString.Char8.ByteString, this allows -- for ListLike instances with Char elements. newtype CharString CS :: ByteString -> CharString unCS :: CharString -> ByteString -- | Newtype wrapper around Data.ByteString.Lazy.Char8.ByteString, this -- allows for ListLike instances with Char elements. newtype CharStringLazy CSL :: ByteString -> CharStringLazy unCSL :: CharStringLazy -> ByteString -- | The class implementing list-like functions. -- -- It is worth noting that types such as Map can be instances of -- ListLike. Due to their specific ways of operating, they may not -- behave in the expected way in some cases. For instance, cons -- may not increase the size of a map if the key you have given is -- already in the map; it will just replace the value already there. -- -- Implementators must define at least: -- -- class (FoldableLL full item, Monoid full) => ListLike full item | full -> item where empty = mempty cons item l = append (singleton item) l snoc l item = append l (singleton item) append = mappend last l = case genericLength l of { (0 :: Integer) -> error "Called last on empty list" 1 -> head l _ -> last (tail l) } init l | null l = error "init: empty list" | null xs = empty | otherwise = cons (head l) (init xs) where xs = tail l null x = genericLength x == (0 :: Integer) length = genericLength map func inp | null inp = empty | otherwise = cons (func (head inp)) (map func (tail inp)) rigidMap = map reverse l = rev l empty where rev rl a | null rl = a | otherwise = rev (tail rl) (cons (head rl) a) intersperse sep l | null l = empty | null xs = singleton x | otherwise = cons x (cons sep (intersperse sep xs)) where x = head l xs = tail l concat = fold concatMap = foldMap rigidConcatMap = concatMap any p = getAny . foldMap (Any . p) all p = getAll . foldMap (All . p) maximum = foldr1 max minimum = foldr1 min replicate = genericReplicate take = genericTake drop = genericDrop splitAt = genericSplitAt takeWhile func l | null l = empty | func x = cons x (takeWhile func (tail l)) | otherwise = empty where x = head l dropWhile func l | null l = empty | func (head l) = dropWhile func (tail l) | otherwise = l dropWhileEnd func = foldr (\ x xs -> if func x && null xs then empty else cons x xs) empty span func l | null l = (empty, empty) | func x = (cons x ys, zs) | otherwise = (empty, l) where (ys, zs) = span func (tail l) x = head l break p = span (not . p) group = groupBy (==) inits l | null l = singleton empty | otherwise = append (singleton empty) (map (cons (head l)) theinits) where theinits = asTypeOf (inits (tail l)) [l] tails l | null l = singleton empty | otherwise = cons l (tails (tail l)) isPrefixOf needle haystack | null needle = True | null haystack = False | otherwise = (head needle) == (head haystack) && isPrefixOf (tail needle) (tail haystack) isSuffixOf needle haystack = isPrefixOf (reverse needle) (reverse haystack) isInfixOf needle haystack = any (isPrefixOf needle) thetails where thetails = asTypeOf (tails haystack) [haystack] elem i = any (== i) notElem i = all (/= i) find f l = case findIndex f l of { Nothing -> Nothing Just x -> Just (index l x) } filter func l | null l = empty | func (head l) = cons (head l) (filter func (tail l)) | otherwise = filter func (tail l) partition p xs = (filter p xs, filter (not . p) xs) index l i | null l = error "index: index not found" | i < 0 = error "index: index must be >= 0" | i == 0 = head l | otherwise = index (tail l) (i - 1) elemIndex e l = findIndex (== e) l elemIndices i l = findIndices (== i) l findIndex f = listToMaybe . findIndices f findIndices p xs = map snd $ filter (p . fst) $ thezips where thezips = asTypeOf (zip xs [0 .. ]) [(head xs, 0 :: Int)] sequence l = foldr func (return empty) l where func litem results = do { x <- litem; xs <- results; return (cons x xs) } mapM func l = sequence mapresult where mapresult = asTypeOf (map func l) [] rigidMapM = mapM nub = nubBy (==) delete = deleteBy (==) deleteFirsts = foldl (flip delete) union = unionBy (==) intersect = intersectBy (==) sort = sortBy compare insert = insertBy compare toList = fromListLike fromList [] = empty fromList (x : xs) = cons x (fromList xs) fromListLike = map id nubBy f l = nubBy' l (empty :: full) where nubBy' ys xs | null ys = empty | any (f (head ys)) xs = nubBy' (tail ys) xs | otherwise = let y = head ys in cons y (nubBy' (tail ys) (cons y xs)) deleteBy func i l | null l = empty | otherwise = if func i (head l) then tail l else cons (head l) (deleteBy func i (tail l)) deleteFirstsBy func = foldl (flip (deleteBy func)) unionBy func x y = append x $ foldl (flip (deleteBy func)) (nubBy func y) x intersectBy func xs ys = filter (\ x -> any (func x) ys) xs groupBy eq l | null l = empty | otherwise = cons (cons x ys) (groupBy eq zs) where (ys, zs) = span (eq x) xs x = head l xs = tail l sortBy cmp = foldr (insertBy cmp) empty insertBy cmp x ys | null ys = singleton x | otherwise = case cmp x (head ys) of { GT -> cons (head ys) (insertBy cmp x (tail ys)) _ -> cons x ys } genericLength l = calclen 0 l where calclen !accum cl = if null cl then accum else calclen (accum + 1) (tail cl) genericTake n l | n <= 0 = empty | null l = empty | otherwise = cons (head l) (genericTake (n - 1) (tail l)) genericDrop n l | n <= 0 = l | null l = l | otherwise = genericDrop (n - 1) (tail l) genericSplitAt n l = (genericTake n l, genericDrop n l) genericReplicate count x | count <= 0 = empty | otherwise = map (\ _ -> x) [1 .. count] empty :: ListLike full item => full singleton :: ListLike full item => item -> full cons :: ListLike full item => item -> full -> full snoc :: ListLike full item => full -> item -> full append :: ListLike full item => full -> full -> full head :: ListLike full item => full -> item last :: ListLike full item => full -> item tail :: ListLike full item => full -> full init :: ListLike full item => full -> full null :: ListLike full item => full -> Bool length :: ListLike full item => full -> Int map :: (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' rigidMap :: ListLike full item => (item -> item) -> full -> full reverse :: ListLike full item => full -> full intersperse :: ListLike full item => item -> full -> full concat :: (ListLike full item, ListLike full' full, Monoid full) => full' -> full concatMap :: (ListLike full item, ListLike full' item') => (item -> full') -> full -> full' rigidConcatMap :: ListLike full item => (item -> full) -> full -> full any :: ListLike full item => (item -> Bool) -> full -> Bool all :: ListLike full item => (item -> Bool) -> full -> Bool maximum :: (ListLike full item, Ord item) => full -> item minimum :: (ListLike full item, Ord item) => full -> item replicate :: ListLike full item => Int -> item -> full take :: ListLike full item => Int -> full -> full drop :: ListLike full item => Int -> full -> full splitAt :: ListLike full item => Int -> full -> (full, full) takeWhile :: ListLike full item => (item -> Bool) -> full -> full dropWhile :: ListLike full item => (item -> Bool) -> full -> full dropWhileEnd :: ListLike full item => (item -> Bool) -> full -> full span :: ListLike full item => (item -> Bool) -> full -> (full, full) break :: ListLike full item => (item -> Bool) -> full -> (full, full) group :: (ListLike full item, ListLike full' full, Eq item) => full -> full' inits :: (ListLike full item, ListLike full' full) => full -> full' tails :: (ListLike full item, ListLike full' full) => full -> full' isPrefixOf :: (ListLike full item, Eq item) => full -> full -> Bool isSuffixOf :: (ListLike full item, Eq item) => full -> full -> Bool isInfixOf :: (ListLike full item, Eq item) => full -> full -> Bool elem :: (ListLike full item, Eq item) => item -> full -> Bool notElem :: (ListLike full item, Eq item) => item -> full -> Bool find :: ListLike full item => (item -> Bool) -> full -> Maybe item filter :: ListLike full item => (item -> Bool) -> full -> full partition :: ListLike full item => (item -> Bool) -> full -> (full, full) index :: ListLike full item => full -> Int -> item elemIndex :: (ListLike full item, Eq item) => item -> full -> Maybe Int elemIndices :: (ListLike full item, Eq item, ListLike result Int) => item -> full -> result findIndex :: ListLike full item => (item -> Bool) -> full -> Maybe Int findIndices :: (ListLike full item, ListLike result Int) => (item -> Bool) -> full -> result sequence :: (ListLike full item, Monad m, ListLike fullinp (m item)) => fullinp -> m full mapM :: (ListLike full item, Monad m, ListLike full' item') => (item -> m item') -> full -> m full' rigidMapM :: (ListLike full item, Monad m) => (item -> m item) -> full -> m full nub :: (ListLike full item, Eq item) => full -> full delete :: (ListLike full item, Eq item) => item -> full -> full deleteFirsts :: (ListLike full item, Eq item) => full -> full -> full union :: (ListLike full item, Eq item) => full -> full -> full intersect :: (ListLike full item, Eq item) => full -> full -> full sort :: (ListLike full item, Ord item) => full -> full insert :: (ListLike full item, Ord item) => item -> full -> full toList :: ListLike full item => full -> [item] fromList :: ListLike full item => [item] -> full fromListLike :: (ListLike full item, ListLike full' item) => full -> full' nubBy :: ListLike full item => (item -> item -> Bool) -> full -> full deleteBy :: ListLike full item => (item -> item -> Bool) -> item -> full -> full deleteFirstsBy :: ListLike full item => (item -> item -> Bool) -> full -> full -> full unionBy :: ListLike full item => (item -> item -> Bool) -> full -> full -> full intersectBy :: ListLike full item => (item -> item -> Bool) -> full -> full -> full groupBy :: (ListLike full item, ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full' sortBy :: ListLike full item => (item -> item -> Ordering) -> full -> full insertBy :: ListLike full item => (item -> item -> Ordering) -> item -> full -> full genericLength :: (ListLike full item, Num a) => full -> a genericTake :: (ListLike full item, Integral a) => a -> full -> full genericDrop :: (ListLike full item, Integral a) => a -> full -> full genericSplitAt :: (ListLike full item, Integral a) => a -> full -> (full, full) genericReplicate :: (ListLike full item, Integral a) => a -> item -> full -- | This is the primary class for structures that are to be considered -- foldable. A minimum complete definition provides foldl and -- foldr. -- -- Instances of FoldableLL can be folded, and can be many and -- varied. -- -- These functions are used heavily in Data.ListLike. class FoldableLL full item | full -> item where foldl' f a xs = foldr f' id xs a where f' x k z = k $! f z x foldl1 f xs = fromMaybe (error "fold1: empty structure") (foldl mf Nothing xs) where mf Nothing y = Just y mf (Just x) y = Just (f x y) foldr' f a xs = foldl f' id xs a where f' k x z = k $! f x z foldr1 f xs = fromMaybe (error "foldr1: empty structure") (foldr mf Nothing xs) where mf x Nothing = Just x mf x (Just y) = Just (f x y) foldl :: FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl' :: FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl1 :: FoldableLL full item => (item -> item -> item) -> full -> item foldr :: FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr' :: FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr1 :: FoldableLL full item => (item -> item -> item) -> full -> item -- | An extension to ListLike for those data types that are similar -- to a String. Minimal complete definition is toString and -- fromString. class StringLike s where lines = myLines words = myWords unlines = myUnlines unwords = myUnwords toString :: StringLike s => s -> String fromString :: StringLike s => String -> s lines :: (StringLike s, ListLike full s) => s -> full words :: (StringLike s, ListLike full s) => s -> full -- | An extension to ListLike for those data types that are capable -- of dealing with infinite lists. Some ListLike functions are -- capable of working with finite or infinite lists. The functions here -- require infinite list capability in order to work at all. class ListLike full item => InfiniteListLike full item | full -> item where iterate f x = cons x (iterate f (f x)) repeat x = xs where xs = cons x xs cycle xs | null xs = error "ListLike.cycle: empty list" | otherwise = xs' where xs' = append xs xs' iterate :: InfiniteListLike full item => (item -> item) -> item -> full repeat :: InfiniteListLike full item => item -> full cycle :: InfiniteListLike full item => full -> full