#!/usr/bin/runghc
-- This file implements this:
-- https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

-- More background on Shuffle:
-- https://en.wikipedia.org/wiki/Random_permutation
-- https://en.wikipedia.org/wiki/Shuffling#Algorithms
-- https://wiki.haskell.org/Random_shuffle
-- https://www.reddit.com/r/haskell/comments/y8t3b/ask_rhaskell_how_to_elegantly_and_randomly/https://www.reddit.com/r/haskell/comments/y8t3b/ask_rhaskell_how_to_elegantly_and_randomly/
-- https://apfelmus.nfshost.com/articles/random-permutations.html
-- https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm
-- https://en.wikipedia.org/wiki/Heap%27s_algorithm

import Data.Map
import System.Random

shuffleStep :: (RandomGen g) => (Map Int a, g) -> (Int, a) -> (Map Int a, g)
shuffleStep (m, gen) (i, x) =
  let (j, gen') = randomR (0, i) gen
   in ((insert j x . insert i (m ! j)) m, gen')

shuffle :: (RandomGen g) => g -> [a] -> ([a], g)
shuffle gen [] = ([], gen)
shuffle gen l =
  let toElems (x, y) = (elems x, y)
      enumerate = zip [1 ..]
      initial x gen = (singleton 0 x, gen)
   in toElems $ Prelude.foldl shuffleStep (initial (head l) gen) (enumerate (tail l))

main :: IO ()
main = do
  g <- getStdGen
  print (shuffle g [1..10])