(** {1 Second part: random computations} *)(** The second part of the project is more open-ended than thefirst. I will give here a module interface, PROB, and a fewconvenience functions, and then ask you to play with it, implementa few ideas, and show me how you've used them. We will give youa good grade if we think you did something interesting.Note in particular that the interface PROB is not set in stone:if, in the course of your use of this library, you discover thatyou need additional primitives, please extend the signature to addthem, and explain (in comments) what they do and how you usethem. Adding interesting primitives is a good thing -- not at allmandatory, but appreciated.*)(** {2 Second part: random computations} *)(** The last module exported a type ['a search] to represent solutionsto a search problem. This one has a type ['a dist] thatexpressions possible outputs of a random computation. For example,you may define a value [flip_coin : bool dist] that representsflipping a random coin, and (morally) returns true half of thetime, false the other.The interesting thing with the ['a dist] type is that we can "run"the random computation and get not one output, but *all possibleoutputs, with their respective probabilities*. The output of[run compare flip_coin] should be something like(I'll explain what the "compare" is for later):[(true, 0.5); (false, 0.5)]A very nice thing with this ['a dist] is that it allows us tocheck whether some algorithms are "really random", in the sensethat all their outputs have an equal chance of happening (it's anuniform distribution), or if the randomness is skewed (e.g., thecoin returns true more often than false). For example, if [a] and[b] are two integers choosen at random in [0..3], is [a+b]uniform, or do some sums happen more often than others? Is [4*a+b]uniform? Let's check:# let pair = prod (rand 3) (rand 3);;val pair : (int * int) Prob.dist = <abstr># let sum = map (fun (a,b) -> a+b) pair;;val sum : int Prob.dist = <abstr># let sum4 = map (fun (a,b)-> 4 * a + b) pair;;val sum4 : int Prob.dist = <abstr># run compare sum;;- : (int * float) list =[(0, 0.111111111111111105); (1, 0.22222222222222221);(2, 0.333333333333333315); (3, 0.22222222222222221);(4, 0.111111111111111105)]# run compare sum4;;- : (int * float) list =[(0, 0.111111111111111105); (1, 0.111111111111111105);(2, 0.111111111111111105); (4, 0.111111111111111105);(5, 0.111111111111111105); (6, 0.111111111111111105);(8, 0.111111111111111105); (9, 0.111111111111111105);(10, 0.111111111111111105)]From this experiment you can directly see (in fact we have_proved_) that [a+b] is not a uniform random number, while [4*a+b]is. This is something you should already know: when you throw twodice in [1..6] and sum them, the "number in the middle", 7, appearmore often than any other; same thing for 2 in this example.*)moduletypePROB =sigtype'a dist(** You may (or may not) need to sort values of type ['a] in yourimplementation of the PROB signature. In order to make lifeeasier for those of you that decide to do so, I decided than[run] would always require a comparison function of type ['a ->'a -> int], just as those required by [Map.Make] and[Set.Make]. In most cases you can just pass the standardfunction [compare] of OCaml, which has the right type and doesthe right thing for values that don't contain functions.*)valrun : ('a -> 'a -> int) -> 'a dist -> ('a * float) listvalreturn : 'a -> 'a dist(** an element chosen at random, with equal probability, in thegiven array; you can assume that the array elements are all distinct *)valuniform : 'a array -> 'a dist(** [rand n] is a random number between 0 and (n-1) *)valrand : int -> int dist(** be careful to compute the probabilities of the productcorrectly *)valprod : 'a dist -> 'b dist -> ('a * 'b) distvalmap : ('a -> 'b) -> 'a dist -> 'b distvalbind : 'a dist -> ('a -> 'b dist) -> 'b distendmoduleProb : PROB =struct(* FILL CODE HERE *)end(** {2 Where you should go from here} *)(* I want you to experiment with the Prob modules (or variants of theProb modules if you find extensions or different approaches thatwould be interesting) to study the probabilities of outputs ofprograms using randomness.*)(*As a first step, I suggest you study *array shuffles* (ways toshuffle randomly the elements of an array); for example, startingfrom the array [|3;4|], you want the shuffle to randomly return[|3;4|] or [|4;3|], each with the same probability. There are manyalgorithms to shuffle an array, and most of them are wrong, in thesense than some outputs are more likely than the others.I recommend that you try to implement, using the [Prob] module, thetwo following algorithms to shuffle an array of size N:- algorithm 1: N times, pick two integers i,j among [0..N-1], andswap the values of the array at indices i and j- algorithm 2: assign to each value of the array a random "weight"in [0..N-1], sort the values by their weights, and return thecorresponding arrayDo those techniques return a shuffled array with uniformrandomness, or do they return some outputs more often than theother?Could you write a third shuffling algorithm that is different fromthose two, and is uniform -- each output has equal chances of beingchosen? I don't mind if you search for an algorithm to do that onthe internet -- there is a simple, well-known way to do this, thatis interesting to search for if you have some time, but is not thetopic of this project.There is code below that will help you work with (persistent)arrays, and write code using the Prob module that look a bit likethe imperative algorithm (you cannot directly use OCaml's "for"loops to produce ['a dist] values).*)(*What to do next?It's your choice, this project is open-ended. If you stop here, andhave done correctly the ['a search] part, the ['a dist] module andthe three shuffles, I will already be happy -- and you may be tired.I expect some of you to go further, however. I'm sure there areother random algorithms you're interested in, that you could try toexpress with ['a dist] type, to check whether they're uniform orwhat their output probabilities are.Alternatively, there are other ways to represent randomcomputations. Instead of returning the probability distribution ofall the outputs, you can define a datatype that will return theexpected value ("espĂ©rance") of the random process. Or only compute*some* of the possible outputs, by simulating the algorithm, andapproximate the real distributions by making several runs. This isprobably harder than expressing other algorithms, though, soI wouldn't recommend it.*)(** {2 Helper functions for array-manipulating code} *)(** The code below will help you write functions doing randommanipulations on arrays; it is not very interesting so I'm giving itdirectly. *)(** Side-effects would not mix very well with the various structureswe have in the Prob module. We will therefore use *persistent*arrays, such as the "get" and "set" operation do not mutate anexisting array in place, but return a new array, without modifyingthe old one.To make things simple, I just reused the Map structure of OCaml,that provides association maps with keys at any type witha comparison function. I define PArray (persistent arrays) as mapswhose keys are integers. An invariant such maps must respect istheir keys are exactly 0,1,...,N-1, where N is the size of themap.*)modulePArray =Map.Make(structtypet = intletcompare = compareend)(** conversion functions *)letparray_of_array arr =letparray = refPArray.emptyinfori = 0toArray.length arr - 1doparray :=PArray.add i arr.(i) !parraydone; !parrayletarray_of_parray parray =Array.init (PArray.cardinal parray) (funi ->PArray.find i parray)(** length of a persistent array *)letlength =PArray.cardinal(** swapping two indices of a persistent array *)letswap i j parray = parray |>PArray.add i (PArray.find j parray) |>PArray.add j (PArray.find i parray)(** Remark: feel free, of course, to add additional conveniencefunctions, according to the needs of the code you'll develop. *)openProb(** looping functions; you may want to look at their type *)letrecfor_to a b v f =ifa > bthenreturn velsebind (f a v) @@funv' -> for_to (a + 1) b v' fletrecfor_downto a b v f =ifa < bthenreturn velsebind (f a v) @@funv' -> for_downto (a - 1) b v' f(** example of use of looping functions (of no particular interest):returns a persistent array of length n with, at each index i,a random number between 0 and i *)letrand_parray n =letinit = parray_of_array (Array.make n 0)infor_to 0 n init (funi parr -> bind (rand (i+1)) @@funv -> return (PArray.add i v parr))(** [rand_parray n] returns a [int PArray.t Prob.dist], a distributionof persistent arrays; if we want to inspect the content of thosearrays, it's better to convert them back to normal arrays that canbe pretty-printed by the toplevel:(rand_parray n |> Prob.map array_of_parray)On my machine, "running" the probability distribution to get theactual probabilities of each output returns the following result:# run compare (rand_parray 2 |> map array_of_parray);;- : (int array * float) list =[([|0; 0; 0|], 0.166666666666666657);([|0; 0; 1|], 0.166666666666666657);([|0; 0; 2|], 0.166666666666666657);([|0; 1; 0|], 0.166666666666666657);([|0; 1; 1|], 0.166666666666666657);([|0; 1; 2|], 0.166666666666666657)]Of course, the order of the result is not important: it is nota problem if your code for Prob returns those result ina different order. Remark that, as expected, each output comes outwith the same (uniform) probability.*)