Skip to content
Swizec Teller - a geek with a hatswizec.com

An elegant way to randomly change every list member in Haskell

Randomness is a bit of a strange concept in Haskell.

As I discovered writing about Haskell and Randomness a few weeks ago, the best way to avoid doing everything inside the IO monad is to write functions that always return the random generator.

The crux of the matter is that random generators are long mathematical sequences. If you keep using the same index, you'll keep getting the same "random" value. You have to make sure the random generator progresses.

Increasing a number by a random value would look something like this:

import System.Random
addRand::(RandomGen g) => g -> Int -> (g, Int)
addRand gen x = let (a, gen') = randomR (0, 20) gen
in (gen', x+a)
main = do
generator <- newStdGen
print $ snd $ addRand generator 5
-- prints 15

While this approach is great for changing a single value, it breaks down when you try to randomly change a whole list:

print $ map (snd . (addRand generator)) [1,1,1,1]
-- prints [11,11,11,11]

Bummer! We applied a random function to every list member. And got a list of identical values!

The problem is that every time addRand gets called, it uses the same random generator. This means we're always using the same number in the random generator series.

We need a way to perform a fold and a map at the same time. A map, so the function is applied to every list item and we get a new list, and a fold where the generator is used as the accumulator.

We might be tempted to write something like this monstrosity:

addRand'::(RandomGen g) => g -> [Int] -> [(g, Int)]
addRand' gen [x] = [addRand gen x]
addRand' gen (x:xs) = let (gen', x') = addRand gen x
in (gen', x'):(addRand' gen' xs)
-- and then in main
print $ map (snd) $ addRand' generator [1,1,1,1]
-- prints [11,3,13,14]

This works. Every number in the list is different!

But the code is somewhat terrible and difficult to reason about.

Luckily, Haskell has got us covered and comes with a standard function called mapAccumL, which is a combination of a fold and a map:

print $ snd $ mapAccumL addRand generator [1,1,1,1]
-- prints [11,3,13,14]

Cleaner, less work, more obvious what's going on. And it just happens to be perfect for writing evolutionary algorithms in Haskell. But more on that later, hopefully as early as Friday.

Here's the whole code:

import System.Random
import Data.List
addRand::(RandomGen g) => g -> Int -> (g, Int)
addRand gen x = let (a, gen') = randomR (0, 20) gen
in (gen', x+a)
addRand'::(RandomGen g) => g -> [Int] -> [(g, Int)]
addRand' gen [x] = [addRand gen x]
addRand' gen (x:xs) = let (gen', x') = addRand gen x
in (gen', x'):(addRand' gen' xs)
main = do
generator <- newStdGen
print $ snd $ addRand generator 5
-- prints 15
print $ map (snd . (addRand generator)) [1,1,1,1]
-- prints [11,11,11,11]
print $ map (snd) $ addRand' generator [1,1,1,1]
-- prints [11,3,13,14]
print $ snd $ mapAccumL addRand generator [1,1,1,1]
-- prints [11,3,13,14]

Enhanced by Zemanta

Did you enjoy this article?

Published on August 13th, 2012 in Algorithm, Evolutionary algorithm, Haskell, Programming, Random number generation, Randomness, Uncategorized

Learned something new?
Want to become a high value JavaScript expert?

Here's how it works 👇

Leave your email and I'll send you an Interactive Modern JavaScript Cheatsheet 📖right away. After that you'll get thoughtfully written emails every week about React, JavaScript, and your career. Lessons learned over my 20 years in the industry working with companies ranging from tiny startups to Fortune5 behemoths.

Start with an interactive cheatsheet 📖

Then get thoughtful letters 💌 on mindsets, tactics, and technical skills for your career.

"Man, love your simple writing! Yours is the only email I open from marketers and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"

~ Ashish Kumar

Join over 10,000 engineers just like you already improving their careers with my letters, workshops, courses, and talks. ✌️

Have a burning question that you think I can answer? I don't have all of the answers, but I have some! Hit me up on twitter or book a 30min ama for in-depth help.

Ready to Stop copy pasting D3 examples and create data visualizations of your own?  Learn how to build scalable dataviz components your whole team can understand with React for Data Visualization

Curious about Serverless and the modern backend? Check out Serverless Handbook, modern backend for the frontend engineer.

Ready to learn how it all fits together and build a modern webapp from scratch? Learn how to launch a webapp and make your first 💰 on the side with ServerlessReact.Dev

Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️