{-
	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)