pastebin - collaborative debugging

pastebin is a collaborative debugging tool allowing you to share and modify code snippets while chatting on IRC, IM or a message board.

This site is developed to XHTML and CSS2 W3C standards. If you see this paragraph, your browser does not support those standards and you need to upgrade. Visit WaSP for a variety of options.

Haskell pastebin - collaborative debugging tool View Help


Posted by randomwalker on Wed 16 Sep 08:24 (modification of post by me view diff)
report abuse | download | new post

  1. import System.Random
  2. import Ix
  3.  
  4. -- general notes:
  5. --    1. is it really this painful to do anything with random numbers?
  6. --    2. the RNG doesn't even work very well, seems to be linear-congruential
  7. --       how do i get Mersenne Twister?
  8.  
  9. -- attempt 1: straightforward translation of standard idiom; quadratic time
  10. permute1 xs = permute_ xs (mkStdGen 0) where
  11.     permute_ [] rgen = []
  12.     permute_ xs rgen = let (idx, newrgen) = randomR (1, length xs) rgen in
  13.                        xs!!(idx-1) : permute_ (take (idx-1) xs ++ drop idx xs) newrgen
  14.  
  15. -- attempt 2: decorate-sort-undecorate
  16. permute2 xs = permute_ xs (iteraternd (mkStdGen 0) random) where
  17.     -- had to force input type to Int because
  18.     -- i can't figure out what's the base class for sortable types
  19.     permute_ :: [Int] -> [Int] -> [Int]
  20.     permute_ xs rnds = map snd (qsort (zip rnds xs)) where
  21.         -- why does 'sort' work in the prelude but not here?
  22.         qsort [] = []
  23.         qsort (x:xs) = qsort (filter (<=x) xs) ++ [x] ++ qsort (filter (>x) xs)
  24.     -- i'm hoping this is somewhere in the library and i've missed it
  25.     iteraternd g rnd = let (val, newg) = rnd g in val : iteraternd newg rnd
  26.  
  27. -- attempt 3: not really sure where i was going with this..
  28. -- neither linear-time nor a perfect shuffle
  29. -- strategy is to split in half, permute each, and merge 'randomly'
  30. permute3 xs = permute_ xs (mkStdGen 0) where
  31.     permute_ []  rgen = []
  32.     permute_ [x] rgen = [x]
  33.     permute_ xs  rgen =
  34.         let mid = (length xs) `div` 2; (rgen1, rgen2) = split rgen in
  35.         merge (permute_ (take mid xs) rgen1)
  36.               (permute_ (drop mid xs) rgen2)
  37.               []
  38.               rgen
  39.     -- acc is needed to make merge tail-recursive
  40.     merge xs [] acc rgen = xs ++ acc
  41.     merge [] ys acc rgen = ys ++ acc
  42.     merge (x:xs) (y:ys) acc rgen =
  43.         let (rnd, newrgen) = randomR (0,1) rgen :: (Int, StdGen) in
  44.         if rnd == 0
  45.             then merge xs ys (x:y:acc) newrgen
  46.             else merge xs ys (y:x:acc) newrgen

Submit a correction or amendment below (click here to make a fresh posting)
After submitting an amendment, you'll be able to view the differences between the old and new posts easily.

Syntax highlighting:

To highlight particular lines, prefix each line with @@


Remember me so that I can delete my post