module MagicHaskeller.T10 where
import Control.Monad
import Data.List(partition, sortBy)
import Data.Monoid
import Data.Functor((<$>))
liftList :: MonadPlus m => [a] -> m a
liftList :: [a] -> m a
liftList = [m a] -> m a
forall (t :: * -> *) (m :: * -> *) a.
(Foldable t, MonadPlus m) =>
t (m a) -> m a
msum ([m a] -> m a) -> ([a] -> [m a]) -> [a] -> m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m a) -> [a] -> [m a]
forall a b. (a -> b) -> [a] -> [b]
map a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
scan10 :: [[(a, k, i)]] -> [[(a, k, i)]]
scan10 ([(a, k, i)]
xs:[[(a, k, i)]]
xss) = ([(a, k, i)] -> [(a, k, i)] -> [(a, k, i)])
-> [(a, k, i)] -> [[(a, k, i)]] -> [[(a, k, i)]]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
scanl (\[(a, k, i)]
x [(a, k, i)]
y -> [(a, k, i)] -> [(a, k, i)]
forall a k i. (Monoid a, Eq k, Ord k) => [(a, k, i)] -> [(a, k, i)]
tokoro10 ([(a, k, i)]
x [(a, k, i)] -> [(a, k, i)] -> [(a, k, i)]
forall a. [a] -> [a] -> [a]
++ [(a, k, i)]
y)) ([(a, k, i)] -> [(a, k, i)]
forall a k i. (Monoid a, Eq k, Ord k) => [(a, k, i)] -> [(a, k, i)]
tokoro10 [(a, k, i)]
xs) [[(a, k, i)]]
xss
mergesortWithBy :: (k->k->k) -> (k->k->Ordering) -> [k] -> [k]
mergesortWithBy :: (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k]
mergesortWithBy k -> k -> k
op k -> k -> Ordering
cmp = (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
forall k. (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
mergesortWithByBot k -> k -> k
op (\k
x k
y -> Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just (k -> k -> Ordering
cmp k
x k
y))
mergesortWithByBot :: (k->k->k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
mergesortWithByBot :: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k]
mergesortWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp = (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [k]
mergesortWithByBot' k -> k -> k
op k -> k -> Maybe Ordering
cmp ([[k]] -> [k]) -> ([k] -> [[k]]) -> [k] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> [k]) -> [k] -> [[k]]
forall a b. (a -> b) -> [a] -> [b]
map k -> [k]
forall (m :: * -> *) a. Monad m => a -> m a
return
mergesortWithByBotIO :: (k->k->k) -> (k -> k -> IO (Maybe Ordering)) -> [k] -> IO [k]
mergesortWithByBotIO :: (k -> k -> k) -> (k -> k -> IO (Maybe Ordering)) -> [k] -> IO [k]
mergesortWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp = (k -> k -> k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [k]
forall k.
(k -> k -> k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [k]
mergesortWithByBot'IO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp ([[k]] -> IO [k]) -> ([k] -> [[k]]) -> [k] -> IO [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> [k]) -> [k] -> [[k]]
forall a b. (a -> b) -> [a] -> [b]
map (k -> [k] -> [k]
forall a. a -> [a] -> [a]
:[])
mergesortWithByBot' :: (k->k->k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [k]
mergesortWithByBot' :: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [k]
mergesortWithByBot' k -> k -> k
op k -> k -> Maybe Ordering
cmp [] = []
mergesortWithByBot' k -> k -> k
op k -> k -> Maybe Ordering
cmp [[k]
xs] = [k]
xs
mergesortWithByBot' k -> k -> k
op k -> k -> Maybe Ordering
cmp [[k]]
xss = (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [k]
mergesortWithByBot' k -> k -> k
op k -> k -> Maybe Ordering
cmp ((k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [[k]]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [[k]]
merge_pairsBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [[k]]
xss)
mergesortWithByBot'IO :: (k->k->k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [k]
mergesortWithByBot'IO :: (k -> k -> k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [k]
mergesortWithByBot'IO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [] = [k] -> IO [k]
forall (m :: * -> *) a. Monad m => a -> m a
return []
mergesortWithByBot'IO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [[k]
xs] = [k] -> IO [k]
forall (m :: * -> *) a. Monad m => a -> m a
return [k]
xs
mergesortWithByBot'IO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [[k]]
xss = (k -> k -> k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [k]
forall k.
(k -> k -> k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [k]
mergesortWithByBot'IO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp ([[k]] -> IO [k]) -> IO [[k]] -> IO [k]
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< ((k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [[k]]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [[k]]
merge_pairsBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [[k]]
xss)
merge_pairsBot :: (k->k->k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [[k]]
merge_pairsBot :: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [[k]]
merge_pairsBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [] = []
merge_pairsBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [[k]
xs] = [[k]
xs]
merge_pairsBot k -> k -> k
op k -> k -> Maybe Ordering
cmp ([k]
xs:[k]
ys:[[k]]
xss) = (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [k]
xs [k]
ys [k] -> [[k]] -> [[k]]
forall a. a -> [a] -> [a]
: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [[k]]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [[k]] -> [[k]]
merge_pairsBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [[k]]
xss
merge_pairsBotIO :: (k->k->k) -> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [[k]]
merge_pairsBotIO :: (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [[k]]
merge_pairsBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [] = [[k]] -> IO [[k]]
forall (m :: * -> *) a. Monad m => a -> m a
return []
merge_pairsBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [[k]
xs] = [[k]] -> IO [[k]]
forall (m :: * -> *) a. Monad m => a -> m a
return [[k]
xs]
merge_pairsBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp ([k]
xs:[k]
ys:[[k]]
xss) = ([k] -> [[k]] -> [[k]]) -> IO [k] -> IO [[k]] -> IO [[k]]
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 (:) ((k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [k]
xs [k]
ys) (IO [[k]] -> IO [[k]]) -> IO [[k]] -> IO [[k]]
forall a b. (a -> b) -> a -> b
$ (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [[k]]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [[k]] -> IO [[k]]
merge_pairsBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [[k]]
xss
mergeWithBy :: (k->k->k) -> (k->k->Ordering) -> [k] -> [k] -> [k]
mergeWithBy :: (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k] -> [k]
mergeWithBy k -> k -> k
op k -> k -> Ordering
cmp = (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op (\k
x k
y -> Ordering -> Maybe Ordering
forall a. a -> Maybe a
Just (k -> k -> Ordering
cmp k
x k
y))
mergeWithByBot :: (k->k->k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot :: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [k]
xs [] = [k]
xs
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [] [k]
ys = [k]
ys
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp (k
x:[k]
xs) (k
y:[k]
ys)
= case k
x k -> k -> Maybe Ordering
`cmp` k
y of
Just Ordering
GT -> k
y k -> [k] -> [k]
forall a. a -> [a] -> [a]
: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp (k
xk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
xs) [k]
ys
Just Ordering
EQ -> k
x k -> k -> k
`op` k
y k -> [k] -> [k]
forall a. a -> [a] -> [a]
: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [k]
xs [k]
ys
Just Ordering
LT -> k
x k -> [k] -> [k]
forall a. a -> [a] -> [a]
: (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [k]
xs (k
yk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ys)
Maybe Ordering
Nothing -> (k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
forall k.
(k -> k -> k) -> (k -> k -> Maybe Ordering) -> [k] -> [k] -> [k]
mergeWithByBot k -> k -> k
op k -> k -> Maybe Ordering
cmp [k]
xs [k]
ys
mergeWithByBotIO :: (k->k->k) -> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO :: (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [k]
xs [] = [k] -> IO [k]
forall (m :: * -> *) a. Monad m => a -> m a
return [k]
xs
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [] [k]
ys = [k] -> IO [k]
forall (m :: * -> *) a. Monad m => a -> m a
return [k]
ys
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp (k
x:[k]
xs) (k
y:[k]
ys)
= do Maybe Ordering
mbo <- k
x k -> k -> IO (Maybe Ordering)
`cmp` k
y
case Maybe Ordering
mbo of
Just Ordering
GT -> (k
y k -> [k] -> [k]
forall a. a -> [a] -> [a]
:) ([k] -> [k]) -> IO [k] -> IO [k]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp (k
xk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
xs) [k]
ys
Just Ordering
EQ -> (k
x k -> k -> k
`op` k
y k -> [k] -> [k]
forall a. a -> [a] -> [a]
:) ([k] -> [k]) -> IO [k] -> IO [k]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [k]
xs [k]
ys
Just Ordering
LT -> (k
x k -> [k] -> [k]
forall a. a -> [a] -> [a]
:) ([k] -> [k]) -> IO [k] -> IO [k]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [k]
xs (k
yk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ys)
Maybe Ordering
Nothing -> (k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
forall k.
(k -> k -> k)
-> (k -> k -> IO (Maybe Ordering)) -> [k] -> [k] -> IO [k]
mergeWithByBotIO k -> k -> k
op k -> k -> IO (Maybe Ordering)
cmp [k]
xs [k]
ys
diffSortedBy :: (a -> t -> Ordering) -> [a] -> [t] -> [a]
diffSortedBy a -> t -> Ordering
_ [] [t]
_ = []
diffSortedBy a -> t -> Ordering
_ [a]
vs [] = [a]
vs
diffSortedBy a -> t -> Ordering
op vs :: [a]
vs@(a
c:[a]
cs) ws :: [t]
ws@(t
d:[t]
ds) = case a -> t -> Ordering
op a
c t
d of Ordering
EQ -> (a -> t -> Ordering) -> [a] -> [t] -> [a]
diffSortedBy a -> t -> Ordering
op [a]
cs [t]
ds
Ordering
LT -> a
c a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> t -> Ordering) -> [a] -> [t] -> [a]
diffSortedBy a -> t -> Ordering
op [a]
cs [t]
ws
Ordering
GT -> (a -> t -> Ordering) -> [a] -> [t] -> [a]
diffSortedBy a -> t -> Ordering
op [a]
vs [t]
ds
diffSortedByBot :: (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot a -> t -> Maybe Ordering
_ [] [t]
_ = []
diffSortedByBot a -> t -> Maybe Ordering
_ [a]
vs [] = [a]
vs
diffSortedByBot a -> t -> Maybe Ordering
op vs :: [a]
vs@(a
c:[a]
cs) ws :: [t]
ws@(t
d:[t]
ds) = case a -> t -> Maybe Ordering
op a
c t
d of
Just Ordering
EQ -> (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot a -> t -> Maybe Ordering
op [a]
cs [t]
ds
Just Ordering
LT -> a
c a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot a -> t -> Maybe Ordering
op [a]
cs [t]
ws
Just Ordering
GT -> (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot a -> t -> Maybe Ordering
op [a]
vs [t]
ds
Maybe Ordering
Nothing -> (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot a -> t -> Maybe Ordering
op [a]
cs [t]
ds
tokoro10nil :: Eq k => [([a],[k],i)] -> [([a],[k],i)]
tokoro10nil :: [([a], [k], i)] -> [([a], [k], i)]
tokoro10nil [([a], [k], i)]
xs = case (([a], [k], i) -> Bool)
-> [([a], [k], i)] -> ([([a], [k], i)], [([a], [k], i)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition (\ ([a]
_,[k]
k,i
_) -> [k]
k[k] -> [k] -> Bool
forall a. Eq a => a -> a -> Bool
==[] ) [([a], [k], i)]
xs of
([], [([a], [k], i)]
diff) -> [([a], [k], i)]
diff
(same :: [([a], [k], i)]
same@(([a]
_,[k]
_,i
i):[([a], [k], i)]
_), [([a], [k], i)]
diff) -> ([[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ((([a], [k], i) -> [a]) -> [([a], [k], i)] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
map (\ ([a]
a,[k]
_,i
_) -> [a]
a) [([a], [k], i)]
same), [], i
i) ([a], [k], i) -> [([a], [k], i)] -> [([a], [k], i)]
forall a. a -> [a] -> [a]
: [([a], [k], i)]
diff
tokoro10 :: (Monoid a, Eq k, Ord k) => [(a,k,i)] -> [(a,k,i)]
tokoro10 :: [(a, k, i)] -> [(a, k, i)]
tokoro10 = ((a, k, i) -> (a, k, i) -> (a, k, i))
-> ((a, k, i) -> (a, k, i) -> Ordering)
-> [(a, k, i)]
-> [(a, k, i)]
forall k. (k -> k -> k) -> (k -> k -> Ordering) -> [k] -> [k]
mergesortWithBy (\(a
xs,k
k,i
i) (a
ys,k
_,i
_) -> (a
xs a -> a -> a
forall a. Monoid a => a -> a -> a
`mappend` a
ys, k
k, i
i)) (\ (a
_,k
k,i
_) (a
_,k
l,i
_) -> k
k k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
`compare` k
l)
[] !? :: [a] -> t -> Maybe a
!? t
n = Maybe a
forall a. Maybe a
Nothing
(a
x:[a]
xs) !? t
0 = a -> Maybe a
forall a. a -> Maybe a
Just a
x
(a
x:[a]
xs) !? t
n = [a]
xs [a] -> t -> Maybe a
!? (t
nt -> t -> t
forall a. Num a => a -> a -> a
-t
1)