2

This older question tells us that in functional programming "true" randomness cannot be achieved since in FP functions are pure/idempotent and return the same value irrespective of number of invocations without any side effects.

But if that is true, how is FP applicable for problems like picking randomly a Captcha or some puzzle to question the user before entering the system?

I considered taking system time as a seed inside the function. But that is depending on external state.

Could anyone please demonstrate it with a code snippet in Haskell/Clojure etc?

Improve this question
16
  • 2
    How does your hypothetical functional language handle I/O?
    – Philip Kendall
    Commented Jan 3, 2018 at 6:55
  • Several options are: (1) make it an impure function that interacts with the outside and/or maintain (use and update) its own state with each call. (2) Use an external tool to pre-generate a huge but finite-size stream of random data, then allow the "random function" to take this stream and feed its values one-by-one to its consumers. In the simplest case, consider zip-with the (fixed, pre-generated) random stream with another input stream.
    – rwong
    Commented Jan 3, 2018 at 7:14
  • The code (algorithm) that requires a random source will now need to be rewritten, so that each time it requires a random value, it needs to pass in a "invoke number". An example is, say, incrementing integers, 0, 1, 2,..., where the "fixed random function" will simply look up the corresponding pre-generated random number from the list. This ensures that, given the same "invoke number", the returned pre-generated number is the same. This removes the dependence on order of evaluation.
    – rwong
    Commented Jan 3, 2018 at 7:18
  • 1
    @JörgWMittag, to be fair to the OP, I don't think that link is clear enough that the answer to her question "how to functional languages handle random numbers", is that "they don't". Functions don't handle non-determinism, and "functional languages" handle non-determinism essentially by being non-functional (that is, by stepping outside the functional paradigm and employing non-functional code) - and so-called functional languages actually allow non-functional code (and non-functional programs) to be written. In the same way that "structured languages" permit unstructured code (e.g. GOTOs).
    – Steve
    Commented Jan 3, 2018 at 7:36
  • 1
    This does feel like a "trick question"; under the conditions specified (no IO, deterministic machine execution), you can't implement "true" randomness in an imperative language either.
    – pjc50
    Commented Jan 4, 2018 at 9:57

3 Answers 3

Reset to default
4

Your question in a bit unclear in that you don't specify whether you are talking about true random numbers or pseudo-random numbers, so I will answer both.

True Random Numbers

You are correct that functional programs can't produce true random numbers. But neither can imperative programs. Computers are still deterministic machines, regardless of whether they are running a C program or a Haskell program.

Pseudo-Random Numbers

Pseudo-Random Numbers are generated by a Pseudo-Random Number Generator (aka PRNG). PRNGs are just algorithms like any other algorithm. They can be expressed in a functional language just as well as they can be expressed in an imperative language.

So, there is really no difference between functional languages and imperative languages when it comes to random numbers. Both can compute pseudo-random numbers and neither can compute true random numbers (since they can't be computed at all).

in functional programming "true" randomness cannot be achieved since in FP functions are pure/idempotent and return the same value irrespective of number of invocations without any side effects.

Again, the same thing is true for imperative programming. If you call srand with the same seed number, you will deterministically get the same pseudo-random number sequence from rand, every time.

The only way to get true randomness is through I/O. But, functional languages can model I/O just fine, whether that be with an I/O Monad (or something more specialized like a Random monad), linear types, world types, effect types, an effect system, or like Scala, ML, Clojure, and F♯ do it, by simply allowing them and trusting the programmer to not make mistakes.

So, in other words, it makes no sense to be asking about Random Numbers specifically. A PRNG is just a function, so if you are asking how functional programming can be used to deal with pseudo-random numbers, then you should rather ask how functional programming can be used to deal with functions, because there is nothing special about a PRNG, it's just a function. And True Randomness is just I/O, so again, it doesn't make sense to ask about them specifically.

If you accept that you can write functions in FP, then you must also accept that you can write PRNGs in FP. And if you accept that you can read the clock, read input from the user, read a file, access a database, access the web, etc., then you must also accept that you can read True Random Numbers. (In fact, on Unix, for example, device drivers are typically exposed as files, and a true random number device would typically be exposed as a file you read from. And there is a web service that serves true random numbers.)

Improve this answer
5
  • This is a good answer except to add that any PRNG generates a (potentially) infinite array of numbers from a given seed. That array is generated without any side effects. That said, it would have been nice to show some Haskell/Clojure code that actually does it.
    – Daniel T.
    Commented Jan 4, 2018 at 3:16
  • I agree with the tenor of your analysis here about any PNRG that is implemented purely in terms of its inputs (and does not reference things like the system clock or any other environmental variable), but I would still make it clear that I/O is something that fundamentally breaks the functional-ness of the program and the guarantees that come with following a functional coding pattern, and puts the onus back on the programmer to manage all the potential difficulties of mutable state. "Functional" languages "model I/O just fine" simply by deviating from being functional, and that's a key point.
    – Steve
    Commented Jan 4, 2018 at 8:03
  • @Steve: There are plenty of ways of modeling I/O without deviating from being functional. Linear types, effect types, world types, effect systems, I/O monads, are but a few. Haskell alone tried out two other approaches (continuations and lazy streams) before settling on the I/O monad.
    – Jörg W Mittag
    Commented Jan 4, 2018 at 17:07
  • @JörgWMittag, it depends what you mean by "being functional". If it means "employing a language described as functional", yes functional languages have I/O - but that is because those languages actually have non-functional features which allow code to be implemented imperatively, not because I/O is actually being implemented as a "function" (in the theoretical sense, rather than in the sense of a language construct or syntax). And the use of the imperative code causes the loss of the guarantees and the potentials that exist for the evaluation of functions.
    – Steve
    Commented Jan 4, 2018 at 17:31
  • Nice analysis. I think it's worth emphasizing that by "simply" allowing I/O in languages like Scala, etc. one does break the idempotence aspect of FP, which was part of the question. It's possible to stay purely functional by using monads, as @JörgWMittag stated. That way the function is still idempotent but the randomness is represented in the result. It's like collapsing the wave function of a quantum system when you measure it, or something like that. :)
    – wensveen
    Commented Feb 10, 2021 at 10:46
3

The whole point of a random number generator is to return a value that is not a deterministic function of its input.

A "random number function" is therefore a contradiction in terms. It is not even on par with I/O, which can still be modelled purely as a function as part of a deterministic system.

What we do in a functional language is simply implement a non-functional, non-deterministic method call - it may look like a function, have the garb of functional syntax, and assemble together as a function (and be called or evaluated, and its results used, in a deterministic order relative to other functions), but it is clearly not actually a function (because its outputs do not relate to its inputs) - and the whole program that depends on it ceases to be a function anymore (because the program does not execute deterministically according to its inputs).

Improve this answer
12
  • Perfect. Hence my question is: Is FP applicable in the below scenario for production environment where want to throw Captcha and Various puzzles to question the user before entering the system?
    – Vicky
    Commented Jan 3, 2018 at 7:37
  • I don't see why Captcha cannot be reconciled with deterministic execution. With a Captcha, the aim is not for the program or results to be non-deterministic - the Captcha system does not depend fundamentally on randomness, but on analytical complexity and obscurity to differentiate the human perception of the information within an image from machine analysis and extraction of the information. In other words, a purely deterministic set of Captchas, would still be unamenable to accurate machine analysis (unless a human first evaluated them all and provided a lookup table).
    – Steve
    Commented Jan 3, 2018 at 7:48
  • 1
    This isn't true of most functional languages I've seen. The approach taken, for example, in Haskell is to set up the user program so that rather than calling a function that returns a random number (which, as you say, would make it not actually a function), the user program passes their own function to the system, and then the system calls that passing it a random number as an argument. This side-steps the issue: there is no non-function involved, just a non-deterministic behaviour that is caused by the environment interacting with the program, which remains purely functional.
    – Jules
    Commented Jan 3, 2018 at 8:01
  • 6
    There are two kinds of random numbers. Computers are deterministic devices, they cannot produce random numbers. They can only produce pseudo-random numbers, which behave statistically is if they were random. However, pseudo-random number generators are still just algorithms like any other algorithm and can be modeled by pure functions. "True" random numbers can only be generated by a physical process and read from the environment. However, this is just I/O like any other I/O, and if your language can model I/O, then it can model this as well. So, I really don't see the problem..
    – Jörg W Mittag
    Commented Jan 3, 2018 at 8:12
  • 1
    @Vicky, that is true. But bear in mind that all computers are supposed to be deterministic, including imperative code. A functional language is one that is designed to aid the use of functional patterns - it does not matter (to me) that it does not strictly enforce them. The reason a true random number generator cannot be a function, is because the meaning of that concept can't be expressed in terms of the functional pattern of inputs relating to outputs, and even the full workings of a useful pseudo-random system would be almost impossible to describe entirely in functional terms.
    – Steve
    Commented Jan 3, 2018 at 9:35
1

Short Answer

Randomness is handled just like other kinds of input.

Long Answer

Random is Input

Random is like reading the state of the hardware clock. And that is like reading the state of the camera to take a profile picture about the computer user, or like reading the content of a certain file. Random is just a special kind of input.

Handling Random Differently than Other Input

In theory some need exists to handle randomness differently from other kinds of input. For example : for security. And the theory of purely functional programming can answer that need. But in practice this direction happens to be not pursued. Even more important security needs are not addressed yet in practice simply because of deficit in software engineering capacity.

How Input is Handled by Purely Functional Programming ?

This topic is discussed in much material over the web. If it to be discussed here on StackExchange then it deserves its own question.

Some Concrete Help to your question Anyway

A pure function returns not the final, concrete result that depends on random, but a [possibly composite] action, like a little algorithm, that says : get a random value; compute some other action with it and perform that other action. A pure function returns just a deterministic value that represents, describes what the program is to do. It forwards the "dirty" problems of non-determinism, IO to the runtime system. A pure function does not do anything, it just computes [and returns] what to do.

Improve this answer
1
  • "A pure function does not do anything" - there is a grain of underlying philosophical truth there I think, which explains why all useful functional languages contain general purpose, non-functional features, and why most programs written in functional languages are not themselves functions.
    – Steve
    Commented Jan 4, 2018 at 10:12

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