Show HN: A visual explanation of Fisher–Yates shuffle

Re:Show HN: A visual explanation of Fisher–Yates shuffle by psykotic on Tuesday January 17, 2012 @09:48PM (#3477649)

Hey, sorry for the late reply.

It seems pretty obvious to me, so I'm not sure what is confusing you.

    class Monad m => ChoiceMonad m where
        choice :: [a] -> m a

For the list monad, choice is just the identity function. For the probability monad, choice picks a random element from the list. (Ideally choice would take a random access structure like a set as its argument, but I'm doing it the simplest way here.)

To implement shuffle, you more or less just transliterate the Python code as you'd expect.

Before you tackle this, make you sure completely understand how the same situation plays out for the simpler case of subsets:

    subset        :: ChoiceMonad m => [a] -> m [a]
    subset []     = return []
    subset (x:xs) = do b <- choice [True, False]
                       xs' <- subset xs
                       return (if b then x:xs' else xs')

Over the list monad, this generates a list of all subsets. Over the probability monad, it generates a random subset.

[ Parent | on HN ]

Re:Show HN: A visual explanation of Fisher–Yates shuffle by longlivedeath on Thursday January 19, 2012 @04:49AM (#3483817)

Thank you, now I see. Here's my version:

    shuffle :: (ChoiceMonad m, Eq a) => [a] -> m [a]
    shuffle [] = return []
    shuffle elems = do 
      x <- choice elems
      xs <- shuffle (x `delete` elems)
      return (x:xs)

[ Parent | on HN ]