{-
  Merge a finite collection of (possibly) infinite ordered lists.

  Made obsolete by the data-ordlist package.

Copyright 2018 Ken Takusagawa

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.

-}
{-# LANGUAGE ScopedTypeVariables #-}
module MergeLists (mergeLists, allSplits) where {
import Data.Function((&));
import Control.Category((>>>));
import Prelude hiding((.),(>>));
import Data.List;
import Data.Ord;

allSplits :: [a] -> [([a],[a])];
allSplits l = zip (inits l) (tails l);

-- merge a finite list of infinite lists
mergeLists :: forall a . (Ord a) => [[a]] -> [a];
mergeLists = let {
 mergeLists1 :: (Ord a) => [[a]] -> [a];
 mergeLists1 [] = [];
 mergeLists1 l = allSplits l & init & map process & minimumBy (comparing fst) & (\result -> (fst result):(mergeLists1 (snd result)));
 -- general strategy is do every possible computation (map process), then pick the best one (minimumBy), relying on laziness.
 process :: ([[a]],[[a]]) -> (a,[[a]]);
 process (x,(y1:yr):z) = (y1,x++(case yr of{
[] -> z;
_ -> yr:z}));
 process (_,[]) = error "should not happen because init";
 process (_,[]:_) = error "should not happen because filter not null";
} in filter (null >>> not) >>> mergeLists1;


} --end