{-
	Copyright (C) 2011 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@]	Utilities related to random-numbers.
-}

module ToolShed.System.Random(
-- * Functions
	randomGens,
	shuffle,
	generateSelection,
	generateSelectionFromBounded,
	select
) where

import qualified	Control.Arrow
import qualified	Data.Foldable
import qualified	Data.Sequence
import			Data.Sequence((><), ViewL((:<)))
import qualified	System.Random

-- | Constructs an infinite list of independent random-generators.
randomGens :: System.Random.RandomGen randomGen => randomGen -> [randomGen]
randomGens	= uncurry (:) . Control.Arrow.second randomGens {-recurse-} . System.Random.split

{- |
	* Shuffles the specified finite list, using the /Fisher-Yates/ algorithm; <https://en.wikipedia.org/wiki/Fisher-Yates_shuffle>.

	* The resulting list has the same length and constituents as the original; only the order has changed.

	* The input list is traversed, but the items aren't evaluated.
-}
shuffle :: System.Random.RandomGen randomGen => randomGen -> [a] -> [a]
shuffle _ []		= []		-- Not strictly necessary.
shuffle _ singleton@[_]	= singleton	-- Not strictly necessary.
shuffle randomGen l	= slave randomGen s (pred $ Data.Sequence.length s)	where
	s	= Data.Sequence.fromList l

	slave randomGen' s' maxIndex
		| maxIndex < 0	= []
		| otherwise	= selection : slave randomGen'' (first >< remainder) (pred maxIndex) {-recurse-}
		where
			(randomIndex, randomGen'')	= System.Random.randomR (0, maxIndex) randomGen'
			(first, selection :< remainder)	= Control.Arrow.second Data.Sequence.viewl $ Data.Sequence.splitAt randomIndex s'

{- |
	* Generate an infinite list of items, each independently randomly selected from the specified finite list.

	* CAVEAT: because the selections are made non-destructively, duplicates may be returned; cf. 'shuffle'.
-}
generateSelection :: System.Random.RandomGen randomGen => randomGen -> [a] -> Maybe [a]
generateSelection _ []		= Nothing
generateSelection _ [x]		= Just $ repeat x	-- Not strictly necessary, but more efficient.
generateSelection randomGen l	= Just . map (l !!) $ System.Random.randomRs (0, pred $ length l) randomGen

-- | Return a randomly selected element from those provided.
select :: (
	Data.Foldable.Foldable	foldable,
	System.Random.RandomGen	randomGen
 )
	=> randomGen
	-> foldable a
	-> Maybe a
select randomGen	= fmap head . generateSelection randomGen . Data.Foldable.toList

{- |
	* Generate an infinite list of data, each independently selected random instances of the specified /bounded/ type.

	* E.g. @ (generateSelectionFromBounded `fmap` System.Random.getStdGen) :: IO [Bool] @.
-}
generateSelectionFromBounded :: (System.Random.RandomGen randomGen, Bounded a, System.Random.Random a) => randomGen -> [a]
generateSelectionFromBounded	= System.Random.randomRs (minBound, maxBound)