ListPlus.hs

{-
	Copyright (C) 2010 Dr. Alistair Ward

	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/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]	Miscellaneous polymorphic list-operations.
-}

module ToolShed.ListPlus(
-- * Types
-- ** Type-synonyms
	ChunkLength,
--	Split,
-- * Functions
	chunk,
	excise,
	groupComparing,
	merge,
	mergeBy,
--	splitsFrom,
	splitsLeftFrom,
	splitsRightFrom,
	takeUntil
) where

import qualified	Control.Arrow
import qualified	Data.List

-- | The length of the chunks into which a list is split.
type ChunkLength	= Int

{- |
	* Splits a list into length-@size@ pieces, where @(size >= 0)@.

	* The last chunk will be shorter, if @n@ isn't an aliquot part of the input list-length.

	* If @(size == 0)@, the resulting list will be an infinite sequence of null lists.

	* CAVEAT: a similar function is available in the module /Data.List.Split/, though this one checks for @(size < 0)@.
-}
chunk ::
	ChunkLength
	-> [a]		-- ^ The polymorphic input list to be chunked.
	-> [[a]]
chunk size list
	| size < 0	= error $ "ToolShed.ListPlus.chunk:\tnegative chunk-size=" ++ show size
	| otherwise	= chunk' list
	where
		chunk' :: [a] -> [[a]]
		chunk' []	= []
		chunk' a	= uncurry (:) . Control.Arrow.second chunk' $ splitAt size a

-- | Remove the single indexed element from the list.
excise ::
	Int	-- ^ The index.
	-> [a]	-- ^ The polymorphic input list.
	-> [a]	-- ^ The same list, with the indexed element removed.
excise 0	= tail	--Just for efficiency.
excise i	= uncurry (++) . Control.Arrow.second tail . splitAt i

{- |
	* Much like 'Data.List.GroupBy', but where the normal binary predicate,
	is composed from equality, after the same unary translation-function has been applied to both list-elements.

	* cf. 'GHC.Exts.groupWith', which uses the function parameter to both sort and group.
-}
groupComparing :: Eq b
	=> (a -> b)	-- ^ Translates elements from the list, prior to testing the translated values for equality.
	-> [a]		-- ^ The polymorphic input list to group.
	-> [[a]]	-- ^ The same list split into chunks of the required length.
groupComparing f	= Data.List.groupBy (\a b -> f a == f b)

{- |
	* Merge two sorted lists, to product a single sorted list.

	* The merge-process is /stable/, in that where items from each list are equal, they remain in the original order.
-}
merge :: Ord a => [a] -> [a] -> [a]
merge [] r		= r
merge l []		= l
merge l@(x : xs) r@(y : ys)
	| x > y		= y : merge l ys
	| otherwise	= x : merge xs r

{- |
	* Merge two sorted lists, according to the specified order, to product a single sorted list.

	* The merge-process is /stable/, in that where items from each list are equal, they remain in the original order.
-}
mergeBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy _ [] r		= r
mergeBy _ l []		= l
mergeBy cmp l@(x : xs) r@(y : ys)
	| x `cmp` y == GT	= y : mergeBy cmp l ys
	| otherwise		= x : mergeBy cmp xs r 

-- | The polymorphic pair, resulting from splitting a list of arbitrary type.
type Split a	= ([a] {-left list-}, [a] {-right list-})

-- | Use the specified transformation, to generate a list of 'Split's, from the initial one.
splitsFrom ::
	(Split a -> Split a)	-- ^ The function used to transform one /split/ into the next.
	-> Int			-- ^ Index.
	-> [a]			-- ^ The polymorphic input list from which the /splits/ are generated.
	-> [Split a]		-- ^ The list of all required splits of the single input list.
splitsFrom transformation i	= iterate transformation . splitAt i

{- |
	* Create the set of all 'Split's, migrating left from the specified location.

	* CAVEAT: 'init' fails when 'fst' has been reduced to null.
-}
splitsLeftFrom ::
	Int		-- ^ Index.
	-> [a]		-- ^ The polymorphic input list from which the /splits/ are generated, as the index is stepped left
	-> [Split a]	-- ^ The list of all required splits of the single input list.
splitsLeftFrom start
	| start < 0	= error $ "ToolShed.ListPlus.splitsLeftFrom:\tnegative starting-index; " ++ show start
	| otherwise	= splitsFrom (\(l, r) -> (init l, last l : r)) start

{- |
	* Create the set of all 'Split's, migrating right from the specified location.

	* CAVEAT: pattern-match against @ : @ fails, when 'snd' has been reduced to null.
-}
splitsRightFrom ::
	Int		-- ^ Index.
	-> [a]		-- ^ The polymorphic input list from which the /splits/ are generated, as the index is stepped right.
	-> [Split a]	-- ^ The list of all required splits of the single input list.
splitsRightFrom start
	| start < 0	= error $ "ToolShed.ListPlus.splitsRightFrom:\tnegative starting-index; " ++ show start
	| otherwise	= splitsFrom (\(l, r : rs) -> (l ++ [r], rs)) start

{- |
	* Take until the specified predicate is satisfied; /including/ the item which satisfied it.

	* NB: @takeWhile (not . test)@ would return one fewer item.
-}
takeUntil ::
	(a -> Bool)	-- ^ Predicate, used to determine the last item taken.
	-> [a]		-- ^ The polymorphic input list.
	-> [a]
takeUntil predicate	= takeUntil'	where
	takeUntil' (x : xs)	= x {-take regardless-} : if predicate x
		then []
		else takeUntil' xs
	takeUntil' _		= []