{-# LANGUAGE ScopedTypeVariables ,TypeFamilies ,MultiParamTypeClasses ,FunctionalDependencies ,FlexibleInstances ,BangPatterns ,FlexibleContexts ,ConstraintKinds ,CPP #-} {-# LANGUAGE TypeOperators #-} -- for GHC >= 9.4 {- Copyright (C) 2007 John Goerzen <jgoerzen@complete.org> All rights reserved. For license and copyright information, see the file COPYRIGHT -} {- | Module : Data.ListLike.Base Copyright : Copyright (C) 2007 John Goerzen License : BSD3 Maintainer : David Fox <dsf@seereason.com>, Andreas Abel Stability : stable Portability: portable Generic operations over list-like structures Written by John Goerzen, jgoerzen\@complete.org -} module Data.ListLike.Base ( ListLike(..), ListOps, toList, fromList, InfiniteListLike(..), zip, zipWith, sequence_ ) where import Prelude ( Applicative(..), Bool(..), Eq(..), Int, Integer, Integral , Maybe(..), Monad, Monoid(..), Num(..), Ord(..), Ordering(..) , ($), (.), (&&), (||), (++), asTypeOf, error, flip, fst, snd , id, maybe, max, min, not, otherwise , sequenceA ) #if MIN_VERSION_base(4,17,0) import Data.Type.Equality -- GHC 9.4: type equality ~ is just an operator now #endif import qualified Data.List as L import Data.ListLike.FoldableLL ( FoldableLL(foldr, foldr1, foldl), fold, foldMap, sequence_ ) import qualified Control.Applicative as A import Data.Monoid ( All(All, getAll), Any(Any, getAny) ) import Data.Maybe ( listToMaybe ) import GHC.Exts (IsList(Item, fromList, {-fromListN,-} toList)) {- | The class implementing list-like functions. It is worth noting that types such as 'Data.Map.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: * singleton * head * tail * null or genericLength -} class (IsList full, item ~ Item full, FoldableLL full item, Monoid full) => ListLike full item | full -> item where ------------------------------ Creation {- | The empty list -} empty :: full empty = forall a. Monoid a => a mempty {- | Creates a single-element list out of an element -} singleton :: item -> full ------------------------------ Basic Functions {- | Like (:) for lists: adds an element to the beginning of a list -} cons :: item -> full -> full cons item item full l = forall full item. ListLike full item => full -> full -> full append (forall full item. ListLike full item => item -> full singleton item item) full l {- | Adds an element to the *end* of a 'ListLike'. -} snoc :: full -> item -> full snoc full l item item = forall full item. ListLike full item => full -> full -> full append full l (forall full item. ListLike full item => item -> full singleton item item) {- | Combines two lists. Like (++). -} append :: full -> full -> full append = forall a. Monoid a => a -> a -> a mappend {- | Extracts the first element of a 'ListLike'. -} head :: full -> item head = forall b a. b -> (a -> b) -> Maybe a -> b maybe (forall a. HasCallStack => [Char] -> a error [Char] "head") forall a b. (a, b) -> a fst forall b c a. (b -> c) -> (a -> b) -> a -> c . forall full item. ListLike full item => full -> Maybe (item, full) uncons {- | Extract head and tail, return Nothing if empty -} uncons :: full -> Maybe (item, full) uncons full x = if forall full item. ListLike full item => full -> Bool null full x then forall a. Maybe a Nothing else forall a. a -> Maybe a Just (forall full item. ListLike full item => full -> item head full x, forall full item. ListLike full item => full -> full tail full x) -- please don't {- | Extracts the last element of a 'ListLike'. -} last :: full -> item last full l = case forall full item a. (ListLike full item, Num a) => full -> a genericLength full l of (Integer 0::Integer) -> forall a. HasCallStack => [Char] -> a error [Char] "Called last on empty list" Integer 1 -> forall full item. ListLike full item => full -> item head full l Integer _ -> forall full item. ListLike full item => full -> item last (forall full item. ListLike full item => full -> full tail full l) {- | Gives all elements after the head. -} tail :: full -> full tail = forall b a. b -> (a -> b) -> Maybe a -> b maybe (forall a. HasCallStack => [Char] -> a error [Char] "tail") forall a b. (a, b) -> b snd forall b c a. (b -> c) -> (a -> b) -> a -> c . forall full item. ListLike full item => full -> Maybe (item, full) uncons {- | All elements of the list except the last one. See also 'inits'. -} init :: full -> full init full l | forall full item. ListLike full item => full -> Bool null full l = forall a. HasCallStack => [Char] -> a error [Char] "init: empty list" | forall full item. ListLike full item => full -> Bool null full xs = forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => full -> item head full l) (forall full item. ListLike full item => full -> full init full xs) where xs :: full xs = forall full item. ListLike full item => full -> full tail full l {- | Tests whether the list is empty. -} null :: full -> Bool null full x = forall full item a. (ListLike full item, Num a) => full -> a genericLength full x forall a. Eq a => a -> a -> Bool == (Integer 0::Integer) {- | Length of the list. See also 'genericLength'. -} length :: full -> Int length = forall full item a. (ListLike full item, Num a) => full -> a genericLength ------------------------------ List Transformations {- | Apply a function to each element, returning any other valid 'ListLike'. 'rigidMap' will always be at least as fast, if not faster, than this function and is recommended if it will work for your purposes. See also 'mapM'. -} map :: ListLike full' item' => (item -> item') -> full -> full' map item -> item' func full inp | forall full item. ListLike full item => full -> Bool null full inp = forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons (item -> item' func (forall full item. ListLike full item => full -> item head full inp)) (forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map item -> item' func (forall full item. ListLike full item => full -> full tail full inp)) {- | Like 'map', but without the possibility of changing the type of the item. This can have performance benefits for things such as ByteStrings, since it will let the ByteString use its native low-level map implementation. -} rigidMap :: (item -> item) -> full -> full rigidMap = forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map {- | Reverse the elements in a list. -} reverse :: full -> full reverse full l = forall {full} {t}. (ListLike full (Item t), ListLike t (Item t)) => full -> t -> t rev full l forall full item. ListLike full item => full empty where rev :: full -> t -> t rev full rl t a | forall full item. ListLike full item => full -> Bool null full rl = t a | Bool otherwise = full -> t -> t rev (forall full item. ListLike full item => full -> full tail full rl) (forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => full -> item head full rl) t a) {- | Add an item between each element in the structure -} intersperse :: item -> full -> full intersperse item sep full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | forall full item. ListLike full item => full -> Bool null full xs = forall full item. ListLike full item => item -> full singleton item x | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons item x (forall full item. ListLike full item => item -> full -> full cons item sep (forall full item. ListLike full item => item -> full -> full intersperse item sep full xs)) where x :: item x = forall full item. ListLike full item => full -> item head full l xs :: full xs = forall full item. ListLike full item => full -> full tail full l ------------------------------ Reducing Lists (folds) -- See also functions in FoldableLLL ------------------------------ Special folds {- | Flatten the structure. -} concat :: (ListLike full' full{-, Monoid full-}) => full' -> full concat = forall full item. (FoldableLL full item, Monoid item) => full -> item fold {- | Map a function over the items and concatenate the results. See also 'rigidConcatMap'.-} concatMap :: (ListLike full' item') => (item -> full') -> full -> full' concatMap = forall full item m. (FoldableLL full item, Monoid m) => (item -> m) -> full -> m foldMap {- | Like 'concatMap', but without the possibility of changing the type of the item. This can have performance benefits for some things such as ByteString. -} rigidConcatMap :: (item -> full) -> full -> full rigidConcatMap = forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> full') -> full -> full' concatMap {- | True if any items satisfy the function -} any :: (item -> Bool) -> full -> Bool any item -> Bool p = Any -> Bool getAny forall b c a. (b -> c) -> (a -> b) -> a -> c . forall full item m. (FoldableLL full item, Monoid m) => (item -> m) -> full -> m foldMap (Bool -> Any Any forall b c a. (b -> c) -> (a -> b) -> a -> c . item -> Bool p) {- | True if all items satisfy the function -} all :: (item -> Bool) -> full -> Bool all item -> Bool p = All -> Bool getAll forall b c a. (b -> c) -> (a -> b) -> a -> c . forall full item m. (FoldableLL full item, Monoid m) => (item -> m) -> full -> m foldMap (Bool -> All All forall b c a. (b -> c) -> (a -> b) -> a -> c . item -> Bool p) {- | The maximum value of the list -} maximum :: Ord item => full -> item maximum = forall full item. FoldableLL full item => (item -> item -> item) -> full -> item foldr1 forall a. Ord a => a -> a -> a max {- | The minimum value of the list -} minimum :: Ord item => full -> item minimum = forall full item. FoldableLL full item => (item -> item -> item) -> full -> item foldr1 forall a. Ord a => a -> a -> a min ------------------------------ Infinite lists {- | Generate a structure with the specified length with every element set to the item passed in. See also 'genericReplicate' -} replicate :: Int -> item -> full replicate = forall full item a. (ListLike full item, Integral a) => a -> item -> full genericReplicate ------------------------------ Sublists {- | Takes the first n elements of the list. See also 'genericTake'. -} take :: Int -> full -> full take = forall full item a. (ListLike full item, Integral a) => a -> full -> full genericTake {- | Drops the first n elements of the list. See also 'genericDrop' -} drop :: Int -> full -> full drop = forall full item a. (ListLike full item, Integral a) => a -> full -> full genericDrop {- | Equivalent to @('take' n xs, 'drop' n xs)@. See also 'genericSplitAt'. -} splitAt :: Int -> full -> (full, full) splitAt = forall full item a. (ListLike full item, Integral a) => a -> full -> (full, full) genericSplitAt {- | Returns all elements at start of list that satisfy the function. -} takeWhile :: (item -> Bool) -> full -> full takeWhile item -> Bool func full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | item -> Bool func item x = forall full item. ListLike full item => item -> full -> full cons item x (forall full item. ListLike full item => (item -> Bool) -> full -> full takeWhile item -> Bool func (forall full item. ListLike full item => full -> full tail full l)) | Bool otherwise = forall full item. ListLike full item => full empty where x :: item x = forall full item. ListLike full item => full -> item head full l {- | Drops all elements from the start of the list that satisfy the function. -} dropWhile :: (item -> Bool) -> full -> full dropWhile item -> Bool func full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | item -> Bool func (forall full item. ListLike full item => full -> item head full l) = forall full item. ListLike full item => (item -> Bool) -> full -> full dropWhile item -> Bool func (forall full item. ListLike full item => full -> full tail full l) | Bool otherwise = full l {- | Drops all elements from the end of the list that satisfy the function. -} dropWhileEnd :: (item -> Bool) -> full -> full dropWhileEnd item -> Bool func = forall full item b. FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr (\item x full xs -> if item -> Bool func item x Bool -> Bool -> Bool && forall full item. ListLike full item => full -> Bool null full xs then forall full item. ListLike full item => full empty else forall full item. ListLike full item => item -> full -> full cons item x full xs) forall full item. ListLike full item => full empty {- | The equivalent of @('takeWhile' f xs, 'dropWhile' f xs)@ -} span :: (item -> Bool) -> full -> (full, full) span item -> Bool func full l | forall full item. ListLike full item => full -> Bool null full l = (forall full item. ListLike full item => full empty, forall full item. ListLike full item => full empty) | item -> Bool func item x = (forall full item. ListLike full item => item -> full -> full cons item x full ys, full zs) | Bool otherwise = (forall full item. ListLike full item => full empty, full l) where (full ys, full zs) = forall full item. ListLike full item => (item -> Bool) -> full -> (full, full) span item -> Bool func (forall full item. ListLike full item => full -> full tail full l) x :: item x = forall full item. ListLike full item => full -> item head full l {- | The equivalent of @'span' ('not' . f)@ -} break :: (item -> Bool) -> full -> (full, full) break item -> Bool p = forall full item. ListLike full item => (item -> Bool) -> full -> (full, full) span (Bool -> Bool not forall b c a. (b -> c) -> (a -> b) -> a -> c . item -> Bool p) {- | Split a list into sublists, each which contains equal arguments. For order-preserving types, concatenating these sublists will produce the original list. See also 'groupBy'. -} group :: (ListLike full' full, Eq item) => full -> full' group = forall full item full'. (ListLike full item, ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full' groupBy forall a. Eq a => a -> a -> Bool (==) {- | All initial segments of the list, shortest first -} inits :: (ListLike full' full) => full -> full' inits full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => item -> full singleton forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => full -> full -> full append (forall full item. ListLike full item => item -> full singleton forall full item. ListLike full item => full empty) (forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map (forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => full -> item head full l)) [full] theinits) where theinits :: [full] theinits = forall a. a -> a -> a asTypeOf (forall full item full'. (ListLike full item, ListLike full' full) => full -> full' inits (forall full item. ListLike full item => full -> full tail full l)) [full l] {- | All final segnemts, longest first -} tails :: ListLike full' full => full -> full' tails full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => item -> full singleton forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons full l (forall full item full'. (ListLike full item, ListLike full' full) => full -> full' tails (forall full item. ListLike full item => full -> full tail full l)) ------------------------------ Predicates {- | True when the first list is at the beginning of the second. -} isPrefixOf :: Eq item => full -> full -> Bool isPrefixOf full needle full haystack | forall full item. ListLike full item => full -> Bool null full needle = Bool True | forall full item. ListLike full item => full -> Bool null full haystack = Bool False | Bool otherwise = (forall full item. ListLike full item => full -> item head full needle) forall a. Eq a => a -> a -> Bool == (forall full item. ListLike full item => full -> item head full haystack) Bool -> Bool -> Bool && forall full item. (ListLike full item, Eq item) => full -> full -> Bool isPrefixOf (forall full item. ListLike full item => full -> full tail full needle) (forall full item. ListLike full item => full -> full tail full haystack) {- | True when the first list is at the beginning of the second. -} isSuffixOf :: Eq item => full -> full -> Bool isSuffixOf full needle full haystack = forall full item. (ListLike full item, Eq item) => full -> full -> Bool isPrefixOf (forall full item. ListLike full item => full -> full reverse full needle) (forall full item. ListLike full item => full -> full reverse full haystack) {- | True when the first list is wholly containted within the second -} isInfixOf :: Eq item => full -> full -> Bool isInfixOf full needle full haystack = forall full item. ListLike full item => (item -> Bool) -> full -> Bool any (forall full item. (ListLike full item, Eq item) => full -> full -> Bool isPrefixOf full needle) [full] thetails where thetails :: [full] thetails = forall a. a -> a -> a asTypeOf (forall full item full'. (ListLike full item, ListLike full' full) => full -> full' tails full haystack) [full haystack] ------------------------------ Conditionally modify based on predicates {- | Remove a prefix from a listlike if possible -} stripPrefix :: Eq item => full -> full -> Maybe full stripPrefix full xs full ys = if full xs forall full item. (ListLike full item, Eq item) => full -> full -> Bool `isPrefixOf` full ys then forall a. a -> Maybe a Just forall a b. (a -> b) -> a -> b $ forall full item. ListLike full item => Int -> full -> full drop (forall full item. ListLike full item => full -> Int length full xs) full ys else forall a. Maybe a Nothing {- | Remove a suffix from a listlike if possible -} stripSuffix :: Eq item => full -> full -> Maybe full stripSuffix full xs full ys = if full xs forall full item. (ListLike full item, Eq item) => full -> full -> Bool `isSuffixOf` full ys then forall a. a -> Maybe a Just forall a b. (a -> b) -> a -> b $ forall full item. ListLike full item => Int -> full -> full take (forall full item. ListLike full item => full -> Int length full ys forall a. Num a => a -> a -> a - forall full item. ListLike full item => full -> Int length full xs) full ys else forall a. Maybe a Nothing ------------------------------ Searching {- | True if the item occurs in the list -} elem :: Eq item => item -> full -> Bool elem item i = forall full item. ListLike full item => (item -> Bool) -> full -> Bool any (forall a. Eq a => a -> a -> Bool == item i) {- | True if the item does not occur in the list -} notElem :: Eq item => item -> full -> Bool notElem item i = forall full item. ListLike full item => (item -> Bool) -> full -> Bool all (forall a. Eq a => a -> a -> Bool /= item i) {- | Take a function and return the first matching element, or Nothing if there is no such element. -} find :: (item -> Bool) -> full -> Maybe item find item -> Bool f full l = case forall full item. ListLike full item => (item -> Bool) -> full -> Maybe Int findIndex item -> Bool f full l of Maybe Int Nothing -> forall a. Maybe a Nothing Just Int x -> forall a. a -> Maybe a Just (forall full item. ListLike full item => full -> Int -> item index full l Int x) {- | Returns only the elements that satisfy the function. -} filter :: (item -> Bool) -> full -> full filter item -> Bool func full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | item -> Bool func (forall full item. ListLike full item => full -> item head full l) = forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => full -> item head full l) (forall full item. ListLike full item => (item -> Bool) -> full -> full filter item -> Bool func (forall full item. ListLike full item => full -> full tail full l)) | Bool otherwise = forall full item. ListLike full item => (item -> Bool) -> full -> full filter item -> Bool func (forall full item. ListLike full item => full -> full tail full l) {- | Returns the lists that do and do not satisfy the function. Same as @('filter' p xs, 'filter' ('not' . p) xs)@ -} partition :: (item -> Bool) -> full -> (full, full) partition item -> Bool p full xs = (forall full item. ListLike full item => (item -> Bool) -> full -> full filter item -> Bool p full xs, forall full item. ListLike full item => (item -> Bool) -> full -> full filter (Bool -> Bool not forall b c a. (b -> c) -> (a -> b) -> a -> c . item -> Bool p) full xs) ------------------------------ Indexing {- | The element at 0-based index i. Raises an exception if i is out of bounds. Like (!!) for lists. -} index :: full -> Int -> item index full l Int i | forall full item. ListLike full item => full -> Bool null full l = forall a. HasCallStack => [Char] -> a error [Char] "index: index not found" | Int i forall a. Ord a => a -> a -> Bool < Int 0 = forall a. HasCallStack => [Char] -> a error [Char] "index: index must be >= 0" | Int i forall a. Eq a => a -> a -> Bool == Int 0 = forall full item. ListLike full item => full -> item head full l | Bool otherwise = forall full item. ListLike full item => full -> Int -> item index (forall full item. ListLike full item => full -> full tail full l) (Int i forall a. Num a => a -> a -> a - Int 1) {- | Returns the index of the element, if it exists. -} elemIndex :: Eq item => item -> full -> Maybe Int elemIndex item e full l = forall full item. ListLike full item => (item -> Bool) -> full -> Maybe Int findIndex (forall a. Eq a => a -> a -> Bool == item e) full l {- | Returns the indices of the matching elements. See also 'findIndices' -} elemIndices :: (Eq item, ListLike result Int) => item -> full -> result elemIndices item i full l = forall full item result. (ListLike full item, ListLike result Int) => (item -> Bool) -> full -> result findIndices (forall a. Eq a => a -> a -> Bool == item i) full l {- | Take a function and return the index of the first matching element, or Nothing if no element matches -} findIndex :: (item -> Bool) -> full -> Maybe Int findIndex item -> Bool f = forall a. [a] -> Maybe a listToMaybe forall b c a. (b -> c) -> (a -> b) -> a -> c . forall full item result. (ListLike full item, ListLike result Int) => (item -> Bool) -> full -> result findIndices item -> Bool f {- | Returns the indices of all elements satisfying the function -} findIndices :: (ListLike result Int) => (item -> Bool) -> full -> result findIndices item -> Bool p full xs = forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map forall a b. (a, b) -> b snd forall a b. (a -> b) -> a -> b $ forall full item. ListLike full item => (item -> Bool) -> full -> full filter (item -> Bool p forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a b. (a, b) -> a fst) forall a b. (a -> b) -> a -> b $ [(item, Int)] thezips where thezips :: [(item, Int)] thezips = forall a. a -> a -> a asTypeOf (forall full item fullb itemb result. (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result zip full xs [Int 0..]) [(forall full item. ListLike full item => full -> item head full xs, Int 0::Int)] ------------------------------ Monadic operations {- | Evaluate each action in the sequence and collect the results -} sequence :: (Applicative m, ListLike fullinp (m item)) => fullinp -> m full sequence = forall full item b. FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr (forall (f :: * -> *) a b c. Applicative f => (a -> b -> c) -> f a -> f b -> f c A.liftA2 forall full item. ListLike full item => item -> full -> full cons) (forall (f :: * -> *) a. Applicative f => a -> f a pure forall full item. ListLike full item => full empty) {- | A map in monad space. Same as @'sequence' . 'map'@ See also 'rigidMapM' -} mapM :: (Applicative m, ListLike full' item') => (item -> m item') -> full -> m full' mapM item -> m item' func full l = forall full item (m :: * -> *) fullinp. (ListLike full item, Applicative m, ListLike fullinp (m item)) => fullinp -> m full sequence [m item'] mapresult where mapresult :: [m item'] mapresult = forall a. a -> a -> a asTypeOf (forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map item -> m item' func full l) [] {- | Like 'mapM', but without the possibility of changing the type of the item. This can have performance benefits with some types. -} rigidMapM :: Monad m => (item -> m item) -> full -> m full rigidMapM = forall full item (m :: * -> *) full' item'. (ListLike full item, Applicative m, ListLike full' item') => (item -> m item') -> full -> m full' mapM ------------------------------ "Set" operations {- | Removes duplicate elements from the list. See also 'nubBy' -} nub :: Eq item => full -> full nub = forall full item. ListLike full item => (item -> item -> Bool) -> full -> full nubBy forall a. Eq a => a -> a -> Bool (==) {- | Removes the first instance of the element from the list. See also 'deleteBy' -} delete :: Eq item => item -> full -> full delete = forall full item. ListLike full item => (item -> item -> Bool) -> item -> full -> full deleteBy forall a. Eq a => a -> a -> Bool (==) {- | List difference. Removes from the first list the first instance of each element of the second list. See '(\\)' and 'deleteFirstsBy' -} deleteFirsts :: Eq item => full -> full -> full deleteFirsts = forall full item a. FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl (forall a b c. (a -> b -> c) -> b -> a -> c flip forall full item. (ListLike full item, Eq item) => item -> full -> full delete) {- | List union: the set of elements that occur in either list. Duplicate elements in the first list will remain duplicate. See also 'unionBy'. -} union :: Eq item => full -> full -> full union = forall full item. ListLike full item => (item -> item -> Bool) -> full -> full -> full unionBy forall a. Eq a => a -> a -> Bool (==) {- | List intersection: the set of elements that occur in both lists. See also 'intersectBy' -} intersect :: Eq item => full -> full -> full intersect = forall full item. ListLike full item => (item -> item -> Bool) -> full -> full -> full intersectBy forall a. Eq a => a -> a -> Bool (==) ------------------------------ Ordered lists {- | Sorts the list. On data types that do not preserve ordering, or enforce their own ordering, the result may not be what you expect. See also 'sortBy'. -} sort :: Ord item => full -> full sort = forall full item. ListLike full item => (item -> item -> Ordering) -> full -> full sortBy forall a. Ord a => a -> a -> Ordering compare {- | Inserts the element at the last place where it is still less than or equal to the next element. On data types that do not preserve ordering, or enforce their own ordering, the result may not be what you expect. On types such as maps, this may result in changing an existing item. See also 'insertBy'. -} insert :: Ord item => item -> full -> full insert = forall full item. ListLike full item => (item -> item -> Ordering) -> item -> full -> full insertBy forall a. Ord a => a -> a -> Ordering compare ------------------------------ Conversions {- | Converts the structure to a list. This is logically equivolent to 'fromListLike', but may have a more optimized implementation. These two functions are now retired in favor of the methods of IsList, but they are retained here because some instances still use this implementation. -} toList' :: full -> [item] toList' = forall full item full'. (ListLike full item, ListLike full' item) => full -> full' fromListLike {- | Generates the structure from a list. -} fromList' :: [item] -> full fromList' [] = forall full item. ListLike full item => full empty fromList' (item x:[item] xs) = forall full item. ListLike full item => item -> full -> full cons item x (forall l. IsList l => [Item l] -> l fromList [item] xs) {- | Converts one ListLike to another. See also 'toList''. Default implementation is @fromListLike = map id@ -} fromListLike :: ListLike full' item => full -> full' fromListLike = forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map forall a. a -> a id {-# INLINE fromListLike #-} ------------------------------ Generalized functions {- | Generic version of 'nub' -} -- This code is adapted from Data.List in base. nubBy :: (item -> item -> Bool) -> full -> full nubBy item -> item -> Bool eq full l = full -> full -> full nubBy' full l forall a. Monoid a => a mempty where nubBy' :: full -> full -> full nubBy' full ys full xs = case forall full item. ListLike full item => full -> Maybe (item, full) uncons full ys of Maybe (item, full) Nothing -> forall a. Monoid a => a mempty Just (item y, full ys') | item -> full -> Bool elem_by item y full xs -> full -> full -> full nubBy' full ys' full xs | Bool otherwise -> forall full item. ListLike full item => item -> full -> full cons item y (full -> full -> full nubBy' full ys' (forall full item. ListLike full item => item -> full -> full cons item y full xs)) elem_by :: item -> full -> Bool elem_by :: item -> full -> Bool elem_by item y full xs = case forall full item. ListLike full item => full -> Maybe (item, full) uncons full xs of Maybe (item, full) Nothing -> Bool False Just (item x, full xs') -> item x item -> item -> Bool `eq` item y Bool -> Bool -> Bool || item -> full -> Bool elem_by item y full xs' {- nubBy f l | null l = empty | otherwise = cons (head l) (nubBy f (filter (\y -> not (f (head l) y)) (tail l))) -} {- | Generic version of 'deleteBy' -} deleteBy :: (item -> item -> Bool) -> item -> full -> full deleteBy item -> item -> Bool func item i full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | Bool otherwise = if item -> item -> Bool func item i (forall full item. ListLike full item => full -> item head full l) then forall full item. ListLike full item => full -> full tail full l else forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => full -> item head full l) (forall full item. ListLike full item => (item -> item -> Bool) -> item -> full -> full deleteBy item -> item -> Bool func item i (forall full item. ListLike full item => full -> full tail full l)) {- | Generic version of 'deleteFirsts' -} deleteFirstsBy :: (item -> item -> Bool) -> full -> full -> full deleteFirstsBy item -> item -> Bool func = forall full item a. FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl (forall a b c. (a -> b -> c) -> b -> a -> c flip (forall full item. ListLike full item => (item -> item -> Bool) -> item -> full -> full deleteBy item -> item -> Bool func)) {- | Generic version of 'union' -} unionBy :: (item -> item -> Bool) -> full -> full -> full unionBy item -> item -> Bool func full x full y = forall full item. ListLike full item => full -> full -> full append full x forall a b. (a -> b) -> a -> b $ forall full item a. FoldableLL full item => (a -> item -> a) -> a -> full -> a foldl (forall a b c. (a -> b -> c) -> b -> a -> c flip (forall full item. ListLike full item => (item -> item -> Bool) -> item -> full -> full deleteBy item -> item -> Bool func)) (forall full item. ListLike full item => (item -> item -> Bool) -> full -> full nubBy item -> item -> Bool func full y) full x {- | Generic version of 'intersect' -} intersectBy :: (item -> item -> Bool) -> full -> full -> full intersectBy item -> item -> Bool func full xs full ys = forall full item. ListLike full item => (item -> Bool) -> full -> full filter (\item x -> forall full item. ListLike full item => (item -> Bool) -> full -> Bool any (item -> item -> Bool func item x) full ys) full xs {- | Generic version of 'group'. -} groupBy :: (ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full' groupBy item -> item -> Bool eq full l | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => item -> full -> full cons item x full ys) (forall full item full'. (ListLike full item, ListLike full' full, Eq item) => (item -> item -> Bool) -> full -> full' groupBy item -> item -> Bool eq full zs) where (full ys, full zs) = forall full item. ListLike full item => (item -> Bool) -> full -> (full, full) span (item -> item -> Bool eq item x) full xs x :: item x = forall full item. ListLike full item => full -> item head full l xs :: full xs = forall full item. ListLike full item => full -> full tail full l {- | Sort function taking a custom comparison function -} sortBy :: (item -> item -> Ordering) -> full -> full sortBy item -> item -> Ordering cmp = forall full item b. FoldableLL full item => (item -> b -> b) -> b -> full -> b foldr (forall full item. ListLike full item => (item -> item -> Ordering) -> item -> full -> full insertBy item -> item -> Ordering cmp) forall full item. ListLike full item => full empty {- | Like 'insert', but with a custom comparison function -} insertBy :: (item -> item -> Ordering) -> item -> full -> full insertBy item -> item -> Ordering cmp item x full ys = case forall full item. ListLike full item => full -> Maybe (item, full) uncons full ys of Maybe (item, full) Nothing -> forall full item. ListLike full item => item -> full singleton item x Just (item ys_head,full ys_tail) -> case item -> item -> Ordering cmp item x item ys_head of Ordering GT -> forall full item. ListLike full item => item -> full -> full cons item ys_head (forall full item. ListLike full item => (item -> item -> Ordering) -> item -> full -> full insertBy item -> item -> Ordering cmp item x full ys_tail) Ordering _ -> forall full item. ListLike full item => item -> full -> full cons item x full ys ------------------------------ Generic Operations {- | Length of the list -} genericLength :: Num a => full -> a genericLength full l = forall {t} {t}. (ListLike t (Item t), Num t) => t -> t -> t calclen a 0 full l where calclen :: t -> t -> t calclen !t accum t cl = if forall full item. ListLike full item => full -> Bool null t cl then t accum else t -> t -> t calclen (t accum forall a. Num a => a -> a -> a + t 1) (forall full item. ListLike full item => full -> full tail t cl) {- | Generic version of 'take' -} genericTake :: Integral a => a -> full -> full genericTake a n full l | a n forall a. Ord a => a -> a -> Bool <= a 0 = forall full item. ListLike full item => full empty | forall full item. ListLike full item => full -> Bool null full l = forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons (forall full item. ListLike full item => full -> item head full l) (forall full item a. (ListLike full item, Integral a) => a -> full -> full genericTake (a n forall a. Num a => a -> a -> a - a 1) (forall full item. ListLike full item => full -> full tail full l)) {- | Generic version of 'drop' -} genericDrop :: Integral a => a -> full -> full genericDrop a n full l | a n forall a. Ord a => a -> a -> Bool <= a 0 = full l | forall full item. ListLike full item => full -> Bool null full l = full l | Bool otherwise = forall full item a. (ListLike full item, Integral a) => a -> full -> full genericDrop (a n forall a. Num a => a -> a -> a - a 1) (forall full item. ListLike full item => full -> full tail full l) {- | Generic version of 'splitAt' -} genericSplitAt :: Integral a => a -> full -> (full, full) genericSplitAt a n full l = (forall full item a. (ListLike full item, Integral a) => a -> full -> full genericTake a n full l, forall full item a. (ListLike full item, Integral a) => a -> full -> full genericDrop a n full l) {- | Generic version of 'replicate' -} genericReplicate :: Integral a => a -> item -> full genericReplicate a count item x | a count forall a. Ord a => a -> a -> Bool <= a 0 = forall full item. ListLike full item => full empty | Bool otherwise = forall full item full' item'. (ListLike full item, ListLike full' item') => (item -> item') -> full -> full' map (\a _ -> item x) [a 1..a count] {-# MINIMAL (singleton, uncons, null) | (singleton, uncons, genericLength) | (singleton, head, tail, null) | (singleton, head, tail, genericLength) #-} -- | A version of 'ListLike' with a single type parameter, the item -- type is obtained using the 'Item' type function from 'IsList'. type ListOps full = (ListLike full (Item full)) {- instance (ListLike full item) => Monad full where m >>= k = foldr (append . k) empty m m >> k = foldr (append . (\_ -> k)) empty m return x = singleton x fail _ = empty instance (ListLike full item) => M.MonadPlus full where mzero = empty mplus = append -} {- | 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 {- | An infinite list of repeated calls of the function to args -} iterate :: (item -> item) -> item -> full iterate item -> item f item x = forall full item. ListLike full item => item -> full -> full cons item x (forall full item. InfiniteListLike full item => (item -> item) -> item -> full iterate item -> item f (item -> item f item x)) {- | An infinite list where each element is the same -} repeat :: item -> full repeat item x = full xs where xs :: full xs = forall full item. ListLike full item => item -> full -> full cons item x full xs {- | Converts a finite list into a circular one -} cycle :: full -> full cycle full xs | forall full item. ListLike full item => full -> Bool null full xs = forall a. HasCallStack => [Char] -> a error [Char] "ListLike.cycle: empty list" | Bool otherwise = full xs' where xs' :: full xs' = forall full item. ListLike full item => full -> full -> full append full xs full xs' -------------------------------------------------- -- This instance is here due to some default class functions instance ListLike [a] a where empty :: [a] empty = [] singleton :: a -> [a] singleton a x = [a x] cons :: a -> [a] -> [a] cons a x [a] l = a x forall a. a -> [a] -> [a] : [a] l snoc :: [a] -> a -> [a] snoc [a] l a x = [a] l forall a. [a] -> [a] -> [a] ++ [a x] append :: [a] -> [a] -> [a] append = forall a. [a] -> [a] -> [a] (++) -- Andreas Abel, 2023-10-10, issue #32: -- Use implementation of 'head' and 'tail' in terms of 'uncons' to avoid the x-partial warning under GHC 9.8 uncons :: [a] -> Maybe (a, [a]) uncons [] = forall a. Maybe a Nothing uncons (a x : [a] xs) = forall a. a -> Maybe a Just (a x, [a] xs) last :: [a] -> a last = forall a. [a] -> a L.last init :: [a] -> [a] init = forall a. [a] -> [a] L.init null :: [a] -> Bool null = forall (t :: * -> *) a. Foldable t => t a -> Bool L.null length :: [a] -> Int length = forall (t :: * -> *) a. Foldable t => t a -> Int L.length map :: forall full' item'. ListLike full' item' => (a -> item') -> [a] -> full' map a -> item' f = forall l. IsList l => [Item l] -> l fromList forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a b. (a -> b) -> [a] -> [b] L.map a -> item' f rigidMap :: (a -> a) -> [a] -> [a] rigidMap = forall a b. (a -> b) -> [a] -> [b] L.map reverse :: [a] -> [a] reverse = forall a. [a] -> [a] L.reverse intersperse :: a -> [a] -> [a] intersperse = forall a. a -> [a] -> [a] L.intersperse -- fromListLike = toList concat :: forall full'. ListLike full' [a] => full' -> [a] concat = forall (t :: * -> *) a. Foldable t => t [a] -> [a] L.concat forall b c a. (b -> c) -> (a -> b) -> a -> c . forall l. IsList l => l -> [Item l] toList -- concatMap func = fromList . L.concatMap func rigidConcatMap :: (a -> [a]) -> [a] -> [a] rigidConcatMap = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b] L.concatMap any :: (a -> Bool) -> [a] -> Bool any = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool L.any all :: (a -> Bool) -> [a] -> Bool all = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool L.all maximum :: Ord a => [a] -> a maximum = forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a L.maximum minimum :: Ord a => [a] -> a minimum = forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a L.minimum -- fold -- foldMap replicate :: Int -> a -> [a] replicate = forall a. Int -> a -> [a] L.replicate take :: Int -> [a] -> [a] take = forall a. Int -> [a] -> [a] L.take drop :: Int -> [a] -> [a] drop = forall a. Int -> [a] -> [a] L.drop splitAt :: Int -> [a] -> ([a], [a]) splitAt = forall a. Int -> [a] -> ([a], [a]) L.splitAt takeWhile :: (a -> Bool) -> [a] -> [a] takeWhile = forall a. (a -> Bool) -> [a] -> [a] L.takeWhile dropWhile :: (a -> Bool) -> [a] -> [a] dropWhile = forall a. (a -> Bool) -> [a] -> [a] L.dropWhile span :: (a -> Bool) -> [a] -> ([a], [a]) span = forall a. (a -> Bool) -> [a] -> ([a], [a]) L.span break :: (a -> Bool) -> [a] -> ([a], [a]) break = forall a. (a -> Bool) -> [a] -> ([a], [a]) L.break group :: forall full'. (ListLike full' [a], Eq a) => [a] -> full' group = forall l. IsList l => [Item l] -> l fromList forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a. Eq a => [a] -> [[a]] L.group inits :: forall full'. ListLike full' [a] => [a] -> full' inits = forall l. IsList l => [Item l] -> l fromList forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a. [a] -> [[a]] L.inits tails :: forall full'. ListLike full' [a] => [a] -> full' tails = forall l. IsList l => [Item l] -> l fromList forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a. [a] -> [[a]] L.tails isPrefixOf :: Eq a => [a] -> [a] -> Bool isPrefixOf = forall a. Eq a => [a] -> [a] -> Bool L.isPrefixOf isSuffixOf :: Eq a => [a] -> [a] -> Bool isSuffixOf = forall a. Eq a => [a] -> [a] -> Bool L.isSuffixOf isInfixOf :: Eq a => [a] -> [a] -> Bool isInfixOf = forall a. Eq a => [a] -> [a] -> Bool L.isInfixOf stripPrefix :: Eq a => [a] -> [a] -> Maybe [a] stripPrefix = forall a. Eq a => [a] -> [a] -> Maybe [a] L.stripPrefix elem :: Eq a => a -> [a] -> Bool elem = forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool L.elem notElem :: Eq a => a -> [a] -> Bool notElem = forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool L.notElem find :: (a -> Bool) -> [a] -> Maybe a find = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Maybe a L.find filter :: (a -> Bool) -> [a] -> [a] filter = forall a. (a -> Bool) -> [a] -> [a] L.filter partition :: (a -> Bool) -> [a] -> ([a], [a]) partition = forall a. (a -> Bool) -> [a] -> ([a], [a]) L.partition index :: [a] -> Int -> a index = forall a. [a] -> Int -> a (L.!!) elemIndex :: Eq a => a -> [a] -> Maybe Int elemIndex = forall a. Eq a => a -> [a] -> Maybe Int L.elemIndex elemIndices :: forall result. (Eq a, ListLike result Int) => a -> [a] -> result elemIndices a item = forall l. IsList l => [Item l] -> l fromList forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a. Eq a => a -> [a] -> [Int] L.elemIndices a item findIndex :: (a -> Bool) -> [a] -> Maybe Int findIndex = forall a. (a -> Bool) -> [a] -> Maybe Int L.findIndex sequence :: forall (m :: * -> *) fullinp. (Applicative m, ListLike fullinp (m a)) => fullinp -> m [a] sequence = forall (t :: * -> *) (f :: * -> *) a. (Traversable t, Applicative f) => t (f a) -> f (t a) sequenceA forall b c a. (b -> c) -> (a -> b) -> a -> c . forall l. IsList l => l -> [Item l] toList -- mapM = M.mapM nub :: Eq a => [a] -> [a] nub = forall a. Eq a => [a] -> [a] L.nub delete :: Eq a => a -> [a] -> [a] delete = forall a. Eq a => a -> [a] -> [a] L.delete deleteFirsts :: Eq a => [a] -> [a] -> [a] deleteFirsts = forall a. Eq a => [a] -> [a] -> [a] (L.\\) union :: Eq a => [a] -> [a] -> [a] union = forall a. Eq a => [a] -> [a] -> [a] L.union intersect :: Eq a => [a] -> [a] -> [a] intersect = forall a. Eq a => [a] -> [a] -> [a] L.intersect sort :: Ord a => [a] -> [a] sort = forall a. Ord a => [a] -> [a] L.sort groupBy :: forall full'. (ListLike full' [a], Eq a) => (a -> a -> Bool) -> [a] -> full' groupBy a -> a -> Bool func = forall l. IsList l => [Item l] -> l fromList forall b c a. (b -> c) -> (a -> b) -> a -> c . forall a. (a -> a -> Bool) -> [a] -> [[a]] L.groupBy a -> a -> Bool func unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] unionBy = forall a. (a -> a -> Bool) -> [a] -> [a] -> [a] L.unionBy intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] intersectBy = forall a. (a -> a -> Bool) -> [a] -> [a] -> [a] L.intersectBy sortBy :: (a -> a -> Ordering) -> [a] -> [a] sortBy = forall a. (a -> a -> Ordering) -> [a] -> [a] L.sortBy insert :: Ord a => a -> [a] -> [a] insert = forall a. Ord a => a -> [a] -> [a] L.insert genericLength :: forall a. Num a => [a] -> a genericLength = forall i a. Num i => [a] -> i L.genericLength -------------------------------------------------- -- These utils are here instead of in Utils.hs because they are needed -- by default class functions {- | Takes two lists and returns a list of corresponding pairs. -} zip :: (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result zip :: forall full item fullb itemb result. (ListLike full item, ListLike fullb itemb, ListLike result (item, itemb)) => full -> fullb -> result zip = forall full item fullb itemb result resultitem. (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result zipWith (,) {- | 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 zipWith :: forall full item fullb itemb result resultitem. (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result zipWith item -> itemb -> resultitem f full a fullb b | forall full item. ListLike full item => full -> Bool null full a = forall full item. ListLike full item => full empty | forall full item. ListLike full item => full -> Bool null fullb b = forall full item. ListLike full item => full empty | Bool otherwise = forall full item. ListLike full item => item -> full -> full cons (item -> itemb -> resultitem f (forall full item. ListLike full item => full -> item head full a) (forall full item. ListLike full item => full -> item head fullb b)) (forall full item fullb itemb result resultitem. (ListLike full item, ListLike fullb itemb, ListLike result resultitem) => (item -> itemb -> resultitem) -> full -> fullb -> result zipWith item -> itemb -> resultitem f (forall full item. ListLike full item => full -> full tail full a) (forall full item. ListLike full item => full -> full tail fullb b))