CODEWITHSUNDEEP
listrandomelm
Yoann B.
Yoann B.

Reputation: 93

Elm random list implementation

Elm standard library offers a function to generate random lists that works fine. By taking a look at its implementation, we can see that the list is constructed in a functionnal style, i.e. from the end to the beginning. When enough elements have been generated, the reversed list is returned:

if n < 1 then
    (List.reverse list, seed)

I'm wondering why do we need to reverse this list? Is it necessary to ensure "correct" randomness?

Upvotes: 4

Views: 611

Answers (3)

rofrol
rofrol

Reputation: 15226

because we can prepend single value to List, and we can only append List to List. We could

append list [value]

and then we don't have to reverse it

http://package.elm-lang.org/packages/elm-lang/core/latest/List

Upvotes: 0

Chad Gilbert
Chad Gilbert

Reputation: 36375

The List.reverse call actually puts the list back in the order in which it was generated.

Here is the code for the functions in question:

list : Int -> Generator a -> Generator (List a)
list n (Generator generate) =
  Generator <| \seed ->
    listHelp [] n generate seed

listHelp : List a -> Int -> (Seed -> (a,Seed)) -> Seed -> (List a, Seed)
listHelp list n generate seed =
  if n < 1 then
    (List.reverse list, seed)
  else
    let
      (value, newSeed) =
        generate seed
    in
      listHelp (value :: list) (n-1) generate newSeed

If we conceptually simplify the concept of a Seed to an Int, and assume that we have a generator that returns (seed, seed + 1), you can reason about the iterations like this, if our initial seed is 1 (generating a list of 5 elements):

listHelp [] 5 myGen 1 -- initial state
listHelp [1] 4 myGen 2
listHelp [2,1] 3 myGen 3
listHelp [3,2,1] 2 myGen 4
listHelp [4,3,2,1] 1 myGen 5
listHelp [5,4,3,2,1] 0 myGen 6

The final output list is then reversed to give you [1,2,3,4,5].

The final ordering doesn't have any bearing on the overall stochasticity of the function, but it does give you a predictable results if you were to run multiple lists with the same seed but requesting different list sizes.

Consider if the list were not reversed in that final step (assuming initialSeed is 1).

List.head (list 5 (myGen initialSeed)) == Just 5
List.head (list 4 (myGen initialSeed)) == Just 4

Since all this pseudo-randomness requires a Seed as input, it makes a lot more sense to reason about things in a predictable manner, rather than introducing an arbitrary re-ordering that would make list unpredictable. List.reverse fixes the output and puts it back into the realm of predictability.

Upvotes: 3

Bzzt
Bzzt

Reputation: 1054

Probably because most random generators aren't really random. If you start them with the same seed, you get the same sequence. If you're depending on this fact for testing, then having the sequence come back in reverse order might break your test.

That's assuming that most programmers would expect the generated sequence to be in list order, ie the first item would be the first generated. I think that's a likely assumption. So its worth it to reverse the list at the end so that the api is less surprising.

Upvotes: 1

Related Questions