burn your gas factories down

I've been Haskelling for three years now and have been loving it. The only discomfort is that from time to time I become painfully aware of my habit of making things horrible and ugly. Consider this code for instance:

usine à gaz

List of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N

> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

This code has been called "clever". Anytime somebody calls your code "clever", you should begin to worry. I mean just look at that thing! You can positively hear the gears turning and the doodads clicking. This code is what the French call a "gas factory", something incomprehensibly and needlessly complex.

is there no simpler way?

Stop micromanaging! Just tell the computer what you want, not what you want it to do

> nexts2 g (l,h) = map (\x -> fst $ randomR (x,h) g) [l..h-1]

No gears or doodads. Geez... I don't what it is with me and making things more complicated than they need to be.

I've been Haskelling for three years now and have been loving it. The only discomfort is that from time to time I become painfully aware of my habit of making things horrible and ugly. Consider this code for instance:

usine à gaz

List of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N

> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

This code has been called "clever". Anytime somebody calls your code "clever", you should begin to worry. I mean just look at that thing! You can positively hear the gears turning and the doodads clicking. This code is what the French call a "gas factory", something incomprehensibly and needlessly complex.

is there no simpler way?

Stop micromanaging! Just tell the computer what you want, not what you want it to do

> nexts2 g (l,h) = map (\x -> fst $ randomR (x,h) g) [l..h-1]

No gears or doodads. Geez... I don't what it is with me and making things more complicated than they need to be.

burn your gas factories down

unsort bis

Boy, do I feel like a big dummy!

Here is a super short and functional version I saw from a Pythonista on reddit.

import Data.List ( sort )
import System.Random ( Random, RandomGen, randoms, getStdGen )

main :: IO ()
main =
 do gen   <- getStdGen
    interact $ unlines . unsort gen . lines

unsort :: (Ord x, RandomGen g) => g -> [x] -> [x]
unsort g es = [ y | (_,y) <- sort $ zip rs es ]
  where rs = randoms g :: [Integer]

edit!

Heffalump points out that (i) if you have duplicates in rs, you don't get scrambling for the relevant bits (ii) this requires Ord x, which it really ought not to (although that is ani improvement from the array thing where I had to lock the type down for some reason)

edit deux

Hmm... what does it mean to get a list of random arbitrary precision integers?

Boy, do I feel like a big dummy!

Here is a super short and functional version I saw from a Pythonista on reddit.

import Data.List ( sort )
import System.Random ( Random, RandomGen, randoms, getStdGen )

main :: IO ()
main =
 do gen   <- getStdGen
    interact $ unlines . unsort gen . lines

unsort :: (Ord x, RandomGen g) => g -> [x] -> [x]
unsort g es = [ y | (_,y) <- sort $ zip rs es ]
  where rs = randoms g :: [Integer]

edit!

Heffalump points out that (i) if you have duplicates in rs, you don't get scrambling for the relevant bits (ii) this requires Ord x, which it really ought not to (although that is ani improvement from the array thing where I had to lock the type down for some reason)

edit deux

Hmm... what does it mean to get a list of random arbitrary precision integers?

unsort bis

unsort

Here's a small script I wrote partly for wikibook stuff and partly to learn how to use arrays and random numbers in Haskell.

I'm not a particularly enlightened Haskeller, so you might want to be careful about learning from me. Go ask somebody more experienced.

Note: one thing I'm a bit annoyed about is that I can't figure out how to make the unsort function generic, how to make it work for any type of array, element, index. Suggestions and by all means simplifications welcome.

unsort

> import Data.Ix ( Ix )
> import Data.List ( unfoldr )
> import Data.Array.MArray ( MArray, getElems, newListArray, readArray, writeArray )
> import System.Random ( mkStdGen, getStdGen, Random, RandomGen, random, randomR )
> import Data.Array.IO

> main :: IO ()
> main =
>  do gen   <- getStdGen
>     ins   <- lines `fmap` getContents
>     outs  <- unsort gen ins
>     putStr . unlines $ outs

Our objective is to scramble a list. To do this we convert the list into a mutable array and scramble it in place. This consists of traversing the array from left to right, swapping each element N with a random element from N to the end of the array.

> unsort :: RandomGen g => g -> [String] -> IO [String]
> unsort g es =
>  do arr  <- newListArray (l,h) es :: IO (IOArray Int String)
>     unsortH arr l idxs >>= getElems
>  where
>   idxs   = nexts g (l,h)
>   (l, h) = (1, length es)

The swapping itself is pretty straightforward. We swap the element at the
given index at the next random index. Recursion to the next element until
we run out of indices.

> unsortH :: (MArray a e m, Num i, Ix i) => a i e -> i -> [i] -> m (a i e)
> unsortH arr c [] = return arr
> unsortH arr c (r:rs) =
>  do rElem <- readArray arr r
>     cElem <- readArray arr c
>     writeArray arr c rElem
>     writeArray arr r cElem
>     unsortH arr (c+1) rs

And here is how we generate that list of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N... Hmm... I'm pretty sure this can be greatly cut down

> nexts :: (RandomGen g, Num n, Ord n, Random n, Ix n) => g -> (n,n) -> [n]
> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

Here's a small script I wrote partly for wikibook stuff and partly to learn how to use arrays and random numbers in Haskell.

I'm not a particularly enlightened Haskeller, so you might want to be careful about learning from me. Go ask somebody more experienced.

Note: one thing I'm a bit annoyed about is that I can't figure out how to make the unsort function generic, how to make it work for any type of array, element, index. Suggestions and by all means simplifications welcome.

unsort

> import Data.Ix ( Ix )
> import Data.List ( unfoldr )
> import Data.Array.MArray ( MArray, getElems, newListArray, readArray, writeArray )
> import System.Random ( mkStdGen, getStdGen, Random, RandomGen, random, randomR )
> import Data.Array.IO

> main :: IO ()
> main =
>  do gen   <- getStdGen
>     ins   <- lines `fmap` getContents
>     outs  <- unsort gen ins
>     putStr . unlines $ outs

Our objective is to scramble a list. To do this we convert the list into a mutable array and scramble it in place. This consists of traversing the array from left to right, swapping each element N with a random element from N to the end of the array.

> unsort :: RandomGen g => g -> [String] -> IO [String]
> unsort g es =
>  do arr  <- newListArray (l,h) es :: IO (IOArray Int String)
>     unsortH arr l idxs >>= getElems
>  where
>   idxs   = nexts g (l,h)
>   (l, h) = (1, length es)

The swapping itself is pretty straightforward. We swap the element at the
given index at the next random index. Recursion to the next element until
we run out of indices.

> unsortH :: (MArray a e m, Num i, Ix i) => a i e -> i -> [i] -> m (a i e)
> unsortH arr c [] = return arr
> unsortH arr c (r:rs) =
>  do rElem <- readArray arr r
>     cElem <- readArray arr c
>     writeArray arr c rElem
>     writeArray arr r cElem
>     unsortH arr (c+1) rs

And here is how we generate that list of random indices. It is a list [ rM, r(M+1), ..., rN ] where rX is a random number from X to N... Hmm... I'm pretty sure this can be greatly cut down

> nexts :: (RandomGen g, Num n, Ord n, Random n, Ix n) => g -> (n,n) -> [n]
> nexts g (l,h) = unfoldr nxt (g,l,h)
>  where
>    nxt (_,l,h) | l >= h = Nothing
>    nxt (g,l,h) = let (r,g2) = randomR (l,h) g
>                      glh2   = (g2, l + 1, h)
>                  in  Just (r, glh2)

unsort