-- |
--   Module      :  Data.Edison.Coll.Defaults
--   Copyright   :  Copyright (c) 1998, 2008 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  internal (unstable)
--   Portability :  GHC / Hugs (MPTC and FD)
--
--   This module provides default implementations of many of the collection methods.  The functions
--   in this module are used to fill out collection implementations and are not intended to be
--   used directly by end users.

module Data.Edison.Coll.Defaults where

import Prelude hiding (null,foldr,foldl,foldr1,foldl1,lookup,filter)
import qualified Control.Monad.Fail as Fail

import Data.Edison.Prelude ( runFail_ )
import Data.Edison.Coll
import qualified Data.Edison.Seq as S
import qualified Data.Edison.Seq.ListSeq as L
import Data.Edison.Seq.Defaults (tokenMatch,maybeParens)

insertSeqUsingUnion :: (CollX c a,S.Sequence seq) => seq a -> c -> c
insertSeqUsingUnion :: forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingUnion seq a
xs c
c = forall c a. CollX c a => c -> c -> c
union (forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeq seq a
xs) c
c

insertSeqUsingFoldr :: (CollX c a,S.Sequence seq) => seq a -> c -> c
insertSeqUsingFoldr :: forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingFoldr seq a
xs c
c = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr forall c a. CollX c a => a -> c -> c
insert c
c seq a
xs

memberUsingFold :: Coll c a => c -> a -> Bool
memberUsingFold :: forall c a. Coll c a => c -> a -> Bool
memberUsingFold c
h a
x = forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
fold (\a
y Bool
ans -> (a
x forall a. Eq a => a -> a -> Bool
== a
y) Bool -> Bool -> Bool
|| Bool
ans) Bool
False c
h

countUsingMember :: SetX c a => a -> c -> Int
countUsingMember :: forall c a. SetX c a => a -> c -> Int
countUsingMember a
x c
xs = if forall c a. CollX c a => a -> c -> Bool
member a
x c
xs then Int
1 else Int
0

lookupAllUsingLookupM :: (Set c a,S.Sequence seq) => a -> c -> seq a
lookupAllUsingLookupM :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
a -> c -> seq a
lookupAllUsingLookupM a
x c
xs =
  case forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupM a
x c
xs of
    Maybe a
Nothing -> forall (s :: * -> *) a. Sequence s => s a
S.empty
    Just a
y  -> forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
y

deleteSeqUsingDelete :: (CollX c a,S.Sequence seq) => seq a -> c -> c
deleteSeqUsingDelete :: forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
deleteSeqUsingDelete seq a
xs c
c = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr forall c a. CollX c a => a -> c -> c
delete c
c seq a
xs

unionSeqUsingFoldl :: (CollX c a,S.Sequence seq) => seq c -> c
unionSeqUsingFoldl :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingFoldl = forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl forall c a. CollX c a => c -> c -> c
union forall c a. CollX c a => c
empty

unionSeqUsingFoldl' :: (CollX c a,S.Sequence seq) => seq c -> c
unionSeqUsingFoldl' :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingFoldl' = forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl' forall c a. CollX c a => c -> c -> c
union forall c a. CollX c a => c
empty

unionSeqUsingReduce :: (CollX c a,S.Sequence seq) => seq c -> c
unionSeqUsingReduce :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingReduce = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducel forall c a. CollX c a => c -> c -> c
union forall c a. CollX c a => c
empty

fromSeqUsingFoldr :: (CollX c a,S.Sequence seq) => seq a -> c
fromSeqUsingFoldr :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingFoldr = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr forall c a. CollX c a => a -> c -> c
insert forall c a. CollX c a => c
empty

fromSeqUsingUnionSeq :: (CollX c a,S.Sequence seq) => seq a -> c
fromSeqUsingUnionSeq :: forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingUnionSeq = forall c a. CollX c a => [c] -> c
unionList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl forall {s :: * -> *} {a} {a}.
(Sequence s, CollX a a) =>
s a -> a -> s a
singleCons []
  where singleCons :: s a -> a -> s a
singleCons s a
xs a
x = forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons (forall c a. CollX c a => a -> c
singleton a
x) s a
xs

toSeqUsingFold :: (Coll c a,S.Sequence seq) => c -> seq a
toSeqUsingFold :: forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
toSeqUsingFold = forall c a b. Coll c a => (a -> b -> b) -> b -> c -> b
fold forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons forall (s :: * -> *) a. Sequence s => s a
S.empty

unsafeInsertMaxUsingUnsafeAppend :: OrdCollX c a => a -> c -> c
unsafeInsertMaxUsingUnsafeAppend :: forall c a. OrdCollX c a => a -> c -> c
unsafeInsertMaxUsingUnsafeAppend a
x c
c = forall c a. OrdCollX c a => c -> c -> c
unsafeAppend c
c (forall c a. CollX c a => a -> c
singleton a
x)

toOrdSeqUsingFoldr :: (OrdColl c a,S.Sequence seq) => c -> seq a
toOrdSeqUsingFoldr :: forall c a (seq :: * -> *).
(OrdColl c a, Sequence seq) =>
c -> seq a
toOrdSeqUsingFoldr = forall c a b. OrdColl c a => (a -> b -> b) -> b -> c -> b
foldr forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons forall (s :: * -> *) a. Sequence s => s a
S.empty

unsafeFromOrdSeqUsingUnsafeInsertMin ::
    (OrdCollX c a,S.Sequence seq) => seq a -> c
unsafeFromOrdSeqUsingUnsafeInsertMin :: forall c a (seq :: * -> *).
(OrdCollX c a, Sequence seq) =>
seq a -> c
unsafeFromOrdSeqUsingUnsafeInsertMin = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr forall c a. OrdCollX c a => a -> c -> c
unsafeInsertMin forall c a. CollX c a => c
empty

disjointUsingToOrdList :: OrdColl c a => c -> c -> Bool
disjointUsingToOrdList :: forall c a. OrdColl c a => c -> c -> Bool
disjointUsingToOrdList c
xs c
ys = forall {a}. Ord a => [a] -> [a] -> Bool
disj (forall c a. OrdColl c a => c -> [a]
toOrdList c
xs) (forall c a. OrdColl c a => c -> [a]
toOrdList c
ys)
  where disj :: [a] -> [a] -> Bool
disj a :: [a]
a@(a
c:[a]
cs) b :: [a]
b@(a
d:[a]
ds) =
          case forall a. Ord a => a -> a -> Ordering
compare a
c a
d of
            Ordering
LT -> [a] -> [a] -> Bool
disj [a]
cs [a]
b
            Ordering
EQ -> Bool
False
            Ordering
GT -> [a] -> [a] -> Bool
disj [a]
a [a]
ds
        disj [a]
_ [a]
_ = Bool
True

intersectWitnessUsingToOrdList ::
        (OrdColl c a, Fail.MonadFail m) => c -> c -> m (a,a)
intersectWitnessUsingToOrdList :: forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> c -> m (a, a)
intersectWitnessUsingToOrdList c
as c
bs = forall {b} {m :: * -> *}.
(Ord b, MonadFail m) =>
[b] -> [b] -> m (b, b)
witness (forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where witness :: [b] -> [b] -> m (b, b)
witness a :: [b]
a@(b
x:[b]
xs) b :: [b]
b@(b
y:[b]
ys) =
          case forall a. Ord a => a -> a -> Ordering
compare b
x b
y of
            Ordering
LT -> [b] -> [b] -> m (b, b)
witness [b]
xs [b]
b
            Ordering
EQ -> forall (m :: * -> *) a. Monad m => a -> m a
return (b
x, b
y)
            Ordering
GT -> [b] -> [b] -> m (b, b)
witness [b]
a [b]
ys
        -- XXX
        witness [b]
_ [b]
_ = forall (m :: * -> *) a. MonadFail m => String -> m a
fail forall a b. (a -> b) -> a -> b
$ forall c a. CollX c a => c -> String
instanceName c
as forall a. [a] -> [a] -> [a]
++ String
".intersect: failed"

lookupUsingLookupM :: Coll c a => a -> c -> a
lookupUsingLookupM :: forall c a. Coll c a => a -> c -> a
lookupUsingLookupM a
x c
ys = forall a. Fail a -> a
runFail_ (forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupM a
x c
ys)

lookupUsingLookupAll :: Coll c a => a -> c -> a
lookupUsingLookupAll :: forall c a. Coll c a => a -> c -> a
lookupUsingLookupAll a
x c
ys =
  case forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
lookupAll a
x c
ys of
    (a
y:[a]
_) -> a
y
    [] -> forall a. HasCallStack => String -> a
error forall a b. (a -> b) -> a -> b
$ forall c a. CollX c a => c -> String
instanceName c
ys forall a. [a] -> [a] -> [a]
++ String
".lookup: lookup failed"

lookupMUsingLookupAll :: (Coll c a, Fail.MonadFail m) => a -> c -> m a
lookupMUsingLookupAll :: forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupMUsingLookupAll a
x c
ys =
  case forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
lookupAll a
x c
ys of
    (a
y:[a]
_) -> forall (m :: * -> *) a. Monad m => a -> m a
return a
y
    []    -> forall (m :: * -> *) a. MonadFail m => String -> m a
fail forall a b. (a -> b) -> a -> b
$ forall c a. CollX c a => c -> String
instanceName c
ys forall a. [a] -> [a] -> [a]
++ String
".lookupM: lookup failed"

lookupWithDefaultUsingLookupAll :: Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupAll :: forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupAll a
dflt a
x c
ys =
  case forall c a (seq :: * -> *).
(Coll c a, Sequence seq) =>
a -> c -> seq a
lookupAll a
x c
ys of
    (a
y:[a]
_) -> a
y
    [] -> a
dflt

lookupWithDefaultUsingLookupM :: Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupM :: forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupM a
dflt a
x c
ys =
  case forall c a (m :: * -> *). (Coll c a, MonadFail m) => a -> c -> m a
lookupM a
x c
ys of
    Just a
y  -> a
y
    Maybe a
Nothing -> a
dflt

deleteMaxUsingMaxView :: OrdColl c a => c -> c
deleteMaxUsingMaxView :: forall c a. OrdColl c a => c -> c
deleteMaxUsingMaxView c
c =
  case forall c a (m :: * -> *).
(OrdColl c a, MonadFail m) =>
c -> m (a, c)
maxView c
c of
    Just (a
_,c
c') -> c
c'
    Maybe (a, c)
Nothing     -> c
c

fromSeqWithUsingInsertWith :: (Set c a,S.Sequence seq) => (a -> a -> a) -> seq a -> c
fromSeqWithUsingInsertWith :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c
fromSeqWithUsingInsertWith a -> a -> a
c = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall c a. Set c a => (a -> a -> a) -> a -> c -> c
insertWith a -> a -> a
c) forall c a. CollX c a => c
empty

insertUsingInsertWith :: Set c a => a -> c -> c
insertUsingInsertWith :: forall c a. Set c a => a -> c -> c
insertUsingInsertWith = forall c a. Set c a => (a -> a -> a) -> a -> c -> c
insertWith (\a
x a
_ -> a
x)

unionUsingUnionWith :: Set c a => c -> c -> c
unionUsingUnionWith :: forall c a. Set c a => c -> c -> c
unionUsingUnionWith = forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith (\a
x a
_ -> a
x)

filterUsingOrdLists :: OrdColl c a => (a -> Bool) -> c -> c
filterUsingOrdLists :: forall c a. OrdColl c a => (a -> Bool) -> c -> c
filterUsingOrdLists a -> Bool
p = forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> Bool) -> [a] -> [a]
L.filter a -> Bool
p forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall c a. OrdColl c a => c -> [a]
toOrdList

partitionUsingOrdLists :: OrdColl c a => (a -> Bool) -> c -> (c,c)
partitionUsingOrdLists :: forall c a. OrdColl c a => (a -> Bool) -> c -> (c, c)
partitionUsingOrdLists a -> Bool
p c
xs = (forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList [a]
ys,forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList [a]
zs)
  where ([a]
ys,[a]
zs) = forall a. (a -> Bool) -> [a] -> ([a], [a])
L.partition a -> Bool
p (forall c a. OrdColl c a => c -> [a]
toOrdList c
xs)

intersectionUsingIntersectionWith :: Set c a => c -> c -> c
intersectionUsingIntersectionWith :: forall c a. Set c a => c -> c -> c
intersectionUsingIntersectionWith = forall c a. Set c a => (a -> a -> a) -> c -> c -> c
intersectionWith (\a
x a
_ -> a
x)

differenceUsingOrdLists :: OrdSet c a => c -> c -> c
differenceUsingOrdLists :: forall c a. OrdSet c a => c -> c -> c
differenceUsingOrdLists c
as c
bs = forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList forall a b. (a -> b) -> a -> b
$ forall {a}. Ord a => [a] -> [a] -> [a]
diff (forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where diff :: [a] -> [a] -> [a]
diff a :: [a]
a@(a
x:[a]
xs) b :: [a]
b@(a
y:[a]
ys) =
          case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> a
x forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
diff [a]
xs [a]
b
            Ordering
EQ -> [a] -> [a] -> [a]
diff [a]
xs [a]
ys
            Ordering
GT -> [a] -> [a] -> [a]
diff [a]
a [a]
ys
        diff [a]
a [a]
_ = [a]
a

symmetricDifferenceUsingDifference :: SetX c a => c -> c -> c
symmetricDifferenceUsingDifference :: forall c a. SetX c a => c -> c -> c
symmetricDifferenceUsingDifference c
xs c
ys = forall c a. CollX c a => c -> c -> c
union (forall c a. SetX c a => c -> c -> c
difference c
xs c
ys) (forall c a. SetX c a => c -> c -> c
difference c
ys c
xs)

properSubsetUsingOrdLists :: OrdSet c a => c -> c -> Bool
properSubsetUsingOrdLists :: forall c a. OrdSet c a => c -> c -> Bool
properSubsetUsingOrdLists c
xs c
ys = forall {a}. Ord a => [a] -> [a] -> Bool
properSubsetOnOrdLists (forall c a. OrdColl c a => c -> [a]
toOrdList c
xs) (forall c a. OrdColl c a => c -> [a]
toOrdList c
ys)

subsetUsingOrdLists :: OrdSet c a => c -> c -> Bool
subsetUsingOrdLists :: forall c a. OrdSet c a => c -> c -> Bool
subsetUsingOrdLists c
xs c
ys = forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists (forall c a. OrdColl c a => c -> [a]
toOrdList c
xs) (forall c a. OrdColl c a => c -> [a]
toOrdList c
ys)

properSubsetOnOrdLists :: (Ord t) => [t] -> [t] -> Bool
properSubsetOnOrdLists :: forall {a}. Ord a => [a] -> [a] -> Bool
properSubsetOnOrdLists [] [] = Bool
False
properSubsetOnOrdLists [] (t
_:[t]
_) = Bool
True
properSubsetOnOrdLists (t
_:[t]
_) [] = Bool
False
properSubsetOnOrdLists a :: [t]
a@(t
x:[t]
xs) (t
y:[t]
ys) =
  case forall a. Ord a => a -> a -> Ordering
compare t
x t
y of
    Ordering
LT -> Bool
False
    Ordering
EQ -> forall {a}. Ord a => [a] -> [a] -> Bool
properSubsetOnOrdLists [t]
xs [t]
ys
    Ordering
GT -> forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [t]
a [t]
ys

subsetOnOrdLists :: (Ord t) => [t] -> [t] -> Bool
subsetOnOrdLists :: forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [] [t]
_ = Bool
True
subsetOnOrdLists (t
_:[t]
_) [] = Bool
False
subsetOnOrdLists a :: [t]
a@(t
x:[t]
xs) (t
y:[t]
ys) =
  case forall a. Ord a => a -> a -> Ordering
compare t
x t
y of
    Ordering
LT -> Bool
False
    Ordering
EQ -> forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [t]
xs [t]
ys
    Ordering
GT -> forall {a}. Ord a => [a] -> [a] -> Bool
subsetOnOrdLists [t]
a [t]
ys

insertSeqWithUsingInsertWith :: (Set c a,S.Sequence seq) => (a -> a -> a) -> seq a -> c -> c
insertSeqWithUsingInsertWith :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c -> c
insertSeqWithUsingInsertWith a -> a -> a
c seq a
xs c
s = forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (forall c a. Set c a => (a -> a -> a) -> a -> c -> c
insertWith a -> a -> a
c) c
s seq a
xs

unionlUsingUnionWith :: Set c a => c -> c -> c
unionlUsingUnionWith :: forall c a. Set c a => c -> c -> c
unionlUsingUnionWith c
xs c
ys = forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith (\a
x a
_ -> a
x) c
xs c
ys

unionrUsingUnionWith :: Set c a => c -> c -> c
unionrUsingUnionWith :: forall c a. Set c a => c -> c -> c
unionrUsingUnionWith c
xs c
ys = forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith (\a
_ a
y -> a
y) c
xs c
ys

unionWithUsingOrdLists :: OrdSet c a => (a -> a -> a) -> c -> c -> c
unionWithUsingOrdLists :: forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
unionWithUsingOrdLists a -> a -> a
c c
as c
bs = forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [a]
merge (forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where merge :: [a] -> [a] -> [a]
merge a :: [a]
a@(a
x:[a]
xs) b :: [a]
b@(a
y:[a]
ys) =
          case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> a
x forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
xs [a]
b
            Ordering
EQ -> a -> a -> a
c a
x a
y forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
xs [a]
ys
            Ordering
GT -> a
y forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
merge [a]
a [a]
ys
        merge [a]
a [] = [a]
a
        merge [] [a]
b = [a]
b

unionSeqWithUsingReducer :: (Set c a,S.Sequence seq) => (a -> a -> a) -> seq c -> c
unionSeqWithUsingReducer :: forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq c -> c
unionSeqWithUsingReducer a -> a -> a
c = forall (s :: * -> *) a.
Sequence s =>
(a -> a -> a) -> a -> s a -> a
S.reducer (forall c a. Set c a => (a -> a -> a) -> c -> c -> c
unionWith a -> a -> a
c) forall c a. CollX c a => c
empty

intersectionWithUsingOrdLists :: OrdSet c a => (a -> a -> a) -> c -> c -> c
intersectionWithUsingOrdLists :: forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
intersectionWithUsingOrdLists a -> a -> a
c c
as c
bs = forall c a. OrdCollX c a => [a] -> c
unsafeFromOrdList forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [a]
inter (forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
  where inter :: [a] -> [a] -> [a]
inter a :: [a]
a@(a
x:[a]
xs) b :: [a]
b@(a
y:[a]
ys) =
          case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> [a] -> [a] -> [a]
inter [a]
xs [a]
b
            Ordering
EQ -> a -> a -> a
c a
x a
y forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
inter [a]
xs [a]
ys
            Ordering
GT -> [a] -> [a] -> [a]
inter [a]
a [a]
ys
        inter [a]
_ [a]
_ = []


unsafeMapMonotonicUsingFoldr :: (OrdColl cin a, OrdCollX cout b) => (a -> b) -> (cin -> cout)
unsafeMapMonotonicUsingFoldr :: forall cin a cout b.
(OrdColl cin a, OrdCollX cout b) =>
(a -> b) -> cin -> cout
unsafeMapMonotonicUsingFoldr a -> b
f cin
xs = forall c a b. OrdColl c a => (a -> b -> b) -> b -> c -> b
foldr (forall c a. OrdCollX c a => a -> c -> c
unsafeInsertMin forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) forall c a. CollX c a => c
empty cin
xs

showsPrecUsingToList :: (Coll c a,Show a) => Int -> c -> ShowS
showsPrecUsingToList :: forall c a. (Coll c a, Show a) => Int -> c -> ShowS
showsPrecUsingToList Int
i c
xs String
rest
  | Int
i forall a. Eq a => a -> a -> Bool
== Int
0    = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [    forall c a. CollX c a => c -> String
instanceName c
xs,String
".fromSeq ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall c a. Coll c a => c -> [a]
toList c
xs) String
rest]
  | Bool
otherwise = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [String
"(",forall c a. CollX c a => c -> String
instanceName c
xs,String
".fromSeq ",forall a. Show a => Int -> a -> ShowS
showsPrec Int
10 (forall c a. Coll c a => c -> [a]
toList c
xs) (Char
')'forall a. a -> [a] -> [a]
:String
rest)]

readsPrecUsingFromList :: (Coll c a, Read a) => Int -> ReadS c
readsPrecUsingFromList :: forall c a. (Coll c a, Read a) => Int -> ReadS c
readsPrecUsingFromList Int
_ String
xs =
    let result :: [(c, String)]
result = forall a. ReadS a -> ReadS a
maybeParens ReadS c
p String
xs
        p :: ReadS c
p String
ys = forall (m :: * -> *). MonadPlus m => String -> String -> m String
tokenMatch ((forall c a. CollX c a => c -> String
instanceName c
x) forall a. [a] -> [a] -> [a]
++ String
".fromSeq") String
ys
                 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall a. Read a => Int -> ReadS a
readsPrec Int
10
                 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \([a]
l,String
rest) -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall c a. CollX c a => [a] -> c
fromList [a]
l,String
rest)

        -- play games with the typechecker so we don't have to use
        -- extensions for scoped type variables
        ~[(c
x,String
_)] = [(c, String)]
result

    in [(c, String)]
result

compareUsingToOrdList :: OrdColl c a => c -> c -> Ordering
compareUsingToOrdList :: forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList c
as c
bs = forall {a}. Ord a => [a] -> [a] -> Ordering
cmp (forall c a. OrdColl c a => c -> [a]
toOrdList c
as) (forall c a. OrdColl c a => c -> [a]
toOrdList c
bs)
 where
  cmp :: [a] -> [a] -> Ordering
cmp [] [] = Ordering
EQ
  cmp [] [a]
_  = Ordering
LT
  cmp [a]
_  [] = Ordering
GT
  cmp (a
x:[a]
xs) (a
y:[a]
ys) =
      case forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
         Ordering
EQ -> [a] -> [a] -> Ordering
cmp [a]
xs [a]
ys
         Ordering
c -> Ordering
c