This repository has been archived by the owner on Oct 9, 2019. It is now read-only.
forked from NoRedInk/elm-random-extra
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Array.elm
110 lines (88 loc) · 2.74 KB
/
Array.elm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
module Random.Array exposing (..)
{-| List of Array Generators
# Generate an Array
@docs array, emptyArray, rangeLengthArray
# Random Operations on an Array
@docs sample, choose, shuffle
-}
import Array exposing (Array, fromList, empty)
import Random exposing (Generator, map, list, int)
import Random.Extra exposing (flatMap, constant)
{-| Generate a random array of given size given a random generator
randomLength5IntArray = array 5 (int 0 100)
-}
array : Int -> Generator a -> Generator (Array a)
array arrayLength generator =
map fromList (list arrayLength generator)
{-| Generator that always generates the empty array
-}
emptyArray : Generator (Array a)
emptyArray =
constant empty
{-| Generate a random array of random length given a minimum length and
a maximum length.
-}
rangeLengthArray : Int -> Int -> Generator a -> Generator (Array a)
rangeLengthArray minLength maxLength generator =
flatMap (\len -> array len generator) (int minLength maxLength)
{-| Sample with replacement: produce a randomly selected element of the
array, or `Nothing` for an empty array. Takes O(1) time.
-}
sample : Array a -> Generator (Maybe a)
sample arr =
let
gen =
Random.int 0 (Array.length arr - 1)
in
Random.map (\index -> Array.get index arr) gen
{-| Sample without replacement: produce a randomly selected element of the
array, and the array with that element omitted (shifting all later elements
down).
-}
choose : Array a -> Generator ( Maybe a, Array a )
choose arr =
if Array.isEmpty arr then
constant ( Nothing, arr )
else
let
lastIndex =
Array.length arr - 1
front i =
Array.slice 0 i arr
back i =
if
i == lastIndex
-- workaround for #1
then
Array.empty
else
Array.slice (i + 1) (lastIndex + 1) arr
gen =
Random.int 0 lastIndex
in
Random.map
(\index ->
( Array.get index arr, Array.append (front index) (back index) )
)
gen
{-| Shuffle the array using the Fisher-Yates algorithm. Takes O(_n_ log _n_)
time and O(_n_) additional space.
-}
shuffle : Array a -> Generator (Array a)
shuffle arr =
if Array.isEmpty arr then
constant arr
else
let
--helper : (List a, Array a) -> Generator (List a, Array a)
helper ( done, remaining ) =
choose remaining
`Random.andThen` (\( m_val, shorter ) ->
case m_val of
Nothing ->
constant ( done, shorter )
Just val ->
helper ( val :: done, shorter )
)
in
Random.map (fst >> Array.fromList) (helper ( [], arr ))