-- 
-- (c) Susumu Katayama
--
module MagicHaskeller.T10 where
import Control.Monad
-- import MagicHaskeller.CoreLang
-- import PriorSubsts
import Data.List(partition, sortBy)
import Data.Monoid
import Data.Functor((<$>))

-- import MagicHaskeller.Types

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


-- Was:  scan10 = mapDepth tokoro10 . scanl1 (++)
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 const cmp = map head . groupBy (\x y -> cmp x y == EQ) . sortBy cmp, except that mergesortWithBy is quicker when the domain includes lots of duplicates.
-- (If there are no duplicates, implementation with sortBy should be quicker.)
-- Implementation of mergesort by Ian Lynagh which is found in GHC distributions was useful for implementing this.
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))

-- cmp returns Nothing when the comparison causes time-out.
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
-- Actually it is questionable if we may remove both of the expressions compared just because comparison between them fails, because only one of them might be responsible.

-- cmp returns Nothing when the comparison causes time-out.
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
-- Actually it is questionable if we may remove both of the expressions compared just because comparison between them fails, because only one of them might be responsible.

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
--         Nothing -> c : diffSortedByBot op cs ds -- I just do not know what is the best solution here, but when timeout happens, I temporarily believe @c@, and skip d.
         Maybe Ordering
Nothing -> (a -> t -> Maybe Ordering) -> [a] -> [t] -> [a]
diffSortedByBot a -> t -> Maybe Ordering
op [a]
cs [t]
ds -- The above turned out to be not a good solution, because when an error (or a timeout) happens, the expression repeatedly appears at each depth. See newnotes on Dec. 18, 2011


-- filters only emptySubst
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
{-
-- ちゃんと計算してないけど，O(n^2)くらい？ ただ，要素数nは少ないっぽいのでこっちの方が速いかも
tokoro10             :: Eq k => [([a],k,i)] -> [([a],k,i)]
tokoro10 []          =  []
tokoro10 ((es,k,i):xs) =  case partition (\ (_,k',_) -> k==k' ) xs of
                                        (same, diff) -> (es ++ concat (map (\ (a,_,_) -> a) same), k, i) : tokoro10 diff
-}
{- quicksortの変形
tokoro10             :: (Eq k, Ord k) => [([a],k,i)] -> [([a],k,i)]
tokoro10 []             = []
tokoro10 ((t@(x,k,i)):ts) = case partition3 k ts of (ls,es,gs) -> tokoro10 ls ++ (x ++ concat es, k, i) : tokoro10 gs
partition3     :: (Eq k, Ord k) => k -> [(a,k,i)] -> ([(a,k,i)],[a],[(a,k,i)])
-- {-# INLINE partition3 #-}
partition3 k ts = foldr (select3 k) ([],[],[]) ts
select3 k t@(x,k',_) (ls,es,gs) = case k' `compare` k of LT -> (t:ls,   es,   gs)
                                                         EQ -> (  ls, x:es,   gs)
                                                         GT -> (  ls,   es, t:gs)
-}

-- merge sort could be much faster.
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)
{- sortはしないけど，実はこっちの方が効率が悪いのでは? 長さに対して2乗のオーダーになりそう．ソートすれば，O(n log n)（後半はO(n)ですみそう）しかも，(\\\)を使うにはソートしてないとだめ．
tokoro10 :: (Eq k, Ord k) => [([a],k,i)] -> [([a],k,i)]
tokoro10 ((t@(xs,k,i)):ts) = case partition (\ (_,k',_) -> k'==k) ts of (es,ns) -> (xs ++ concat (map (\ (a,_,_) -> a) es),  k,  i) : tokoro10 ns
-}

-- Moved from DebMT.lhs
-- ? means Maybe
[]     !? :: [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)


{-
-- nlambda n e = iterate Lambda e !! nの方が美しい？効率は？
nlambda 0 e = e
nlambda n e = Lambda $ nlambda (n-1) e
-}