{-# 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]
(++)
    head :: [a] -> a
head = forall a. [a] -> a
L.head
    last :: [a] -> a
last = forall a. [a] -> a
L.last
    tail :: [a] -> [a]
tail = forall a. [a] -> [a]
L.tail
    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))