Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What I mean about that is that in nearly every tutorial I've read about functional languages, is that one of the great things about functions, is that if you call a function with the same parameters twice, you'll always end up with the same result.

How on earth do you then make a function that takes a seed as a parameter, and then returns a random number based on that seed?

I mean this would seem to go against one of the things that are so good about functions, right? Or am I completely missing something here?

share|improve this question
add comment

4 Answers

up vote 57 down vote accepted

You can't create a pure function called random that will give a different result every time it is called. In fact, you can't even "call" pure functions. You apply them. So you aren't missing anything, but this doesn't mean that random numbers are off-limits in functional programming. Allow me to demonstrate, I'll use Haskell syntax throughout.

Coming from an imperative background, you may initially expect random to have a type like this:

random :: () -> Integer

But this has already been ruled out because random cannot be a pure function.

Consider the idea of a value. A value is an immutable thing. It never changes and every observation that you can make about it is consistent for all time.

Clearly, random can't produce a Integer value. Instead, it produces a Integer random variable. It's type might look like this:

random :: () -> Random Integer

Except that passing an argument is completely unnecessary, functions are pure, so one random () is as good as another random (). I'll give random, from here on, this type:

random :: Random Integer

Which is all well and fine, but not very useful. You may expect to be able to write expressions like random + 42, but you can't, because it won't typecheck. You can't do anything with random variables, yet.

This raises an interesting question. What functions should exist to manipulate random variables?

This function can't exist:

bad :: Random a -> a

in any useful way, because then you could write:

badRandom :: Integer
badRandom = bad random

Which introduces an inconsistency. badRandom is supposedly a value, but it is also a random number; a contradiction.

Maybe we should add this function:

randomAdd :: Integer -> Random Integer -> Random Integer

But this just a special case of a more general pattern. You should be able to apply any function to random thing in order to get other random things like so:

randomMap :: (a -> b) -> Random a -> Random b

Instead of writing random + 42, we can now write randomMap (+42) random.

If all you had was randomMap, you wouldn't be able to combine random variables together. You couldn't write this function for instance:

randomCombine :: Random a -> Random b -> Random (a, b)

You might try to write it like this:

randomCombine a b = randomMap (\a' -> randomMap (\b' -> (a', b')) b) a

But it has the wrong type. Instead of ending up with a Random (a, b), we end up with a Random (Random (a, b))

This can be fixed by adding another function:

randomJoin :: Random (Random a) -> Random a

But, for reasons that may eventually become clear, I'm not going to do that. Instead I'm going to add this:

randomBind :: Random a -> (a -> Random b) -> Random b

It's not immediately obvious that this actually solves the problem, but it does:

randomCombine a b = randomBind a (\a' -> randomMap (\b' -> (a', b')) b)

In fact, it's possible to write randomBind in terms of randomJoin and randomMap. It's also possible to write randomJoin in terms of randomBind. But, I'll leave doing this as an exercise.

We could simplify this a little. Allow me to define this function:

randomUnit :: a -> Random a

randomUnit turns a value into a random variable. This means that we can have random variables that aren't actually random. This was always the case though; we could have done randomMap (const 4) random before. The reason defining randomUnit is a good idea is that now we can define randomMap in terms of randomUnit and randomBind:

randomMap :: (a -> b) -> Random a -> Random b
randomMap f x = randomBind x (randomUnit . f)

Ok, now we are getting somewhere. We have random variables that we can manipulate. However:

  • It's not obvious how we might actually implement these functions,
  • It's quite cumbersome.

Implementation

I'll tackle pseudo random numbers. It is possible implement these functions for real random numbers, but this answer is already getting quite long.

Essentially, the way this is going to work is that we are going to pass a seed value around everywhere. Whenever we generate a new random value, we will produce a new seed. At the end, when we're done constructing a random variable, we will want to sample from it using this function:

runRandom :: Seed -> Random a -> a

I'm going to define the Random type like this:

data Random a = Random (Seed -> (Seed, a))

Then, we just need to provide implementations of randomUnit, randomBind, runRandom and random which is quite straight-forward:

randomUnit :: a -> Random a
randomUnit x = Random (\seed -> (seed, x))

randomBind :: Random a -> (a -> Random b) -> Random b
randomBind (Random f) g =
  Random (\seed ->
    let (seed', x) = f seed
        Random g' = g x in
          g' seed')

runRandom :: Seed -> Random a -> a
runRandom seed (Random f) = (snd . f) seed

For random, I'm going to assume there's already a function of the type:

psuedoRandom :: Seed -> (Seed, Integer)

In which case random is just Random psuedoRandom.

Making things less cumbersome

Haskell has syntactic sugar to make things like this nicer on the eyes. It's called do-notation and to use it all we have to do it create an instance of Monad for Random.

instance Monad Random where
  return = randomUnit
  (>>=) = randomBind

Done. randomCombine from before could now be written:

randomCombine :: Random a -> Random b -> Random (a, b)
randomCombine a b = do
  a' <- a
  b' <- b
  return (a', b')

If I was doing this for myself, I would even go one step further than this and create an instance of Applicative. (Don't worry if this makes no sense).

instance Functor Random where
  fmap = liftM

instance Applicative Random where
  pure = return
  (<*>) = ap

Then randomCombine could be written:

randomCombine :: Random a -> Random b -> Random (a, b)
randomCombine a b = (,) <$> a <*> b

Now that we have these instances, we can use >>= instead of randomBind, join instead of randomJoin, fmap instead of randomMap, return instead of randomUnit. We also get a whole load of functions for free.

Is it worth it? You could argue, that getting to this stage, where working with random numbers isn't completely horrendous was quite difficult and long-winded. What did we get in exchange for this effort?

The most immediate reward is that we can now see exactly which parts of our program are dependent on randomness and which parts are entirely deterministic. In my experience, forcing a strict separation like this simplifies things immensely.

We've assumed so far that we just want a single sample from each random variable that we generate, but if it turns out that in the future we'd actually like to see more of the distribution, this is trivial. You can just use runRandom lots of times on the same random variable with different seeds. This is, of course, possible in imperative languages, but in this case, we can be certain that we aren't going to perform unanticipated IO every time we sample a random variable and we don't have to be careful about initializing state.

share|improve this answer
5  
+1 for a good example of Applicative functors/Monads practical usage. –  jozefg Jun 27 '13 at 12:09
8  
Nice answer, but it goes a bit too fast with some steps. For example, why would bad :: Random a -> a introduce inconsistencies? What is bad about it? Please go slowly in the explanation, especially for the first steps :) If you could explain why the "useful" functions are useful, this could be a 1000-point answer! :) –  Andres F. Jun 27 '13 at 12:31
    
@AndresF. Ok, I'll revise it a little. –  dan_waterworth Jun 27 '13 at 13:12
1  
@AndresF. I've revised my answer, but I don't think I've sufficiently explained how you might use this is practice, so I might come back to it later. –  dan_waterworth Jun 27 '13 at 15:03
1  
Remarkable answer. I'm not a functional programmer but I do understand most of the concepts and I've "played" with Haskell. This is the type of answer that both informs the questioner and inspires others to dig deeper and learn more about the topic. I wish I could give you a few extra points above the 10 from my up-vote. –  RLH Jun 28 '13 at 13:00
show 3 more comments

You're not wrong. If you give the same seed to a RNG twice, then the first pseudo-random number it returns will be the same. This is nothing to do with functional vs. side-effect programming; the definition of a seed is that a specific input causes a specific output of well-distributed but decidedly non-random values. That's why it's called pseudo-random, and it's often a good thing to have, e.g. to write predictable unit tests, to reliably compare different optimisation methods on the same problem, etc.

If you actually want non-pseudo-random numbers from a computer, you have to hook it up to something genuinely random, such as a particle decay source, unpredictable events occurring within the network that the computer is on, etc. This is hard to get right and usually expensive even if it works, but it is the only way of not getting pseudo-random values (usually the values you receive from your programming language are based on some seed, even if you didn't explicitly provide one.)

This, and only this, would compromise the functional nature of a system. Since non-pseudo-random generators are rare, this doesn't come up often, but yes, if you really do have a method generating true random numbers, then at least that little bit of your programming language cannot be 100% pure functional. Whether a language would make an exception for it or not is just a question of how pragmatic the language implementer is.

share|improve this answer
9  
A true RNG can't be a computer program at all, regardless of whether it is pure(ly functional) or not. We all know the von Neumann quote about arithmetical methods of producing random digits (those who don't, look it up - preferably the whole thing, not just the first sentence). You'd need to interact with some non-deterministic hardware, which of course is impure too. But that's just I/O, which has been reconciled with purity several times in very different wans. No language that is in any way useable disallows I/O completely - you couldn't even see the result of the program otherwise. –  delnan Jun 27 '13 at 10:16
    
What's with the down vote? –  l0b0 Jun 27 '13 at 10:51
4  
Why would an external & truly random source compromise the functional nature of the system? It's still "same input -> same output". Unless you consider the external source as part of the system, but then it wouldn't be "external", would it? –  Andres F. Jun 27 '13 at 12:21
3  
This has nothing to do with PRNG vs TRNG. You cannot have a non-constant function of type () -> Integer. You can have a purely functional PRNG of type PRNG_State -> (PRNG_State, Integer), but you'll have to initialize it by impure means). –  Gilles Jun 27 '13 at 14:06
1  
@Brian Agreed, but the wording ("hook it up to something genuinely random") suggests the random source is external to the system. Therefore, the system itself remains purely functional; it's the input source that isn't. –  Andres F. Jun 27 '13 at 15:22
show 1 more comment

It's the same for non functional languages. Ignoring the slightly separate problem of truly random numbers here.

A random number generator always takes a seed value and for the same seed returns the same sequence of random numbers (very helpful if you need to test a program that uses random numbers). Basically it starts with the seed you choose and then uses the last result as seed for the next iteration. So most implementations are "pure" functions as you describe them: Take a value and for the same value always return the same result.

share|improve this answer
add comment

One way is to think of it as an infinite sequence of random numbers:

IEnumerable<int> randomNumberGenerator = new RandomNumberGenerator(seed);

That is, just think of it as a bottomless data structure, like a Stack where you can only call Pop, but you can call it forever. Like a normal immutable stack, taking one off the top gives you another (different) stack.

So an immutable (with lazy evaluation) random number generator might look like:

class RandomNumberGenerator
{
    private readonly int nextSeed;
    private RandomNumberGenerator next;

    public RandomNumberGenerator(int seed)
    {
        this.nextSeed = this.generateNewSeed(seed);
        this.RandomNumber = this.generateRandomNumberBasedOnSeed(seed);
    }

    public int RandomNumber { get; private set; }

    public RandomNumberGenerator Next
    {
        get
        {
            if(this.next == null) this.next = new RandomNumberGenerator(this.nextSeed);
            return this.next;
        }
    }

    private static int generateNewSeed(int seed)
    {
        //...
    }

    private static int generateRandomNumberBasedOnSeed(int seed)
    {
        //...
    }
}

That's functional.

share|improve this answer
    
I don't see how creating an infinite list of random numbers is easier to work with than function like: pseudoRandom :: Seed -> (Seed, Integer). You might even end up writing a function of this type [Integer] -> ([Integer], Integer) –  dan_waterworth Jun 28 '13 at 6:37
1  
@dan_waterworth actually it makes a lot of sense. An integer cannot be said to be random. A list of numbers can have this protperty. So truth is, a random generator can have the type int -> [int] ie a function which takes a seed and return a random list of integers. Sure, you can have a state monad around this to get haskell's do notation. But as a generic answer to the question, I think this is really helpful. –  Simon Jun 28 '13 at 9:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.