SML Looping through 2 Random variables and ordering them?

Question

I am trying to use SML to do the following:

• print a tuple of 2 integers, the first being a number 1-50, and the second being 1 (this is what I have so far):

val nextInt = Random.randRange (1,50);
val r = Random.rand ();
val x1 = nextInt r;
val x2 = nextInt r;

val inputL = [(x1,1)];

• I then need to load this list into an input list and process the list tuple by tuple so that if the first value has not been seen before, it gets added to the output list. If it has been seen, increment the 2 variable (the second variable is for the frequency that number has been seen)

• Next is to automatically sort the output list in increasing order of the first integer.

I am very lost... Essentially this program will loop maybe 10 times, giving a random int for its first integer, and the frequency as the second, then arrange the first variable in an ascending order.

Again, I've tried this and it only gives me one tuple of 1 random integer, and a 1. I need it to loop about 10 times, track frequency, and order it.

val nextInt = Random.randRange (1,50);
val r = Random.rand ();
val x1 = nextInt r;
val x2 = nextInt r;

val inputL = [(x1,1)];

OUTPUT IM GETTING:

> val r = <rand>: Random.rand;
> val x1 = 2: int;
> val x2 = 3: int;
> val inputL = [(2, 1)]: (int * int) list;

Answer 1

Your description isn't very clear, but it seems like you're trying to tally a list of tuples. Let's skip the part about generating a list of random integers and just use an example.

val numbers = [10, 45, 5, 32, 10, 2, 17, 22, 38, 17]

A naive approach would involve two simpler operations: counting a value in a list, and filtering a value out of a list. Both are easily implemented as recursive functions.

fun count _ [] = 0
  | count v (x::xs) = 
      (if x = v then 1 else 0) + count v xs;

fun filter _ [] = []
  | filter v (x::xs) =
      if x = v then 
        filter v xs
      else
        x :: filter v xs;

Then the basics rules of tally are very simple:

• Tallying an empty list is an empty list.
• Tallying a non-empty list is attaching a tuple of the first element and its count in the list to the list that results from counting the list with the first element filtered out.

A sample run might look like:

tally [10, 45, 5, 32, 10, 2, 17, 22, 38, 17]
(10, 2) :: tally [45, 5, 32, 2, 17, 22, 38, 17]
(10, 2) :: (45, 1) :: tally [5, 32, 2, 17, 22, 38, 17]
(10, 2) :: (45, 1) :: (5, 1) :: tally [32, 2, 17, 22, 38, 17]
(10, 2) :: (45, 1) :: (5, 1) :: (32, 1) :: tally [2, 17, 22, 38, 17]
(10, 2) :: (45, 1) :: (5, 1) :: (32, 1) :: (2, 1) :: tally [17, 22, 38, 17]
(10, 2) :: (45, 1) :: (5, 1) :: (32, 1) :: (2, 1) :: (17, 2) :: tally [22, 38]
(10, 2) :: (45, 1) :: (5, 1) :: (32, 1) :: (2, 1) :: (17, 2) :: (22, 1) :: tally [38]
(10, 2) :: (45, 1) :: (5, 1) :: (32, 1) :: (2, 1) :: (17, 2) :: (22, 1) :: (38, 1) :: tally []
(10, 2) :: (45, 1) :: (5, 1) :: (32, 1) :: (2, 1) :: (17, 2) :: (22, 1) :: (38, 1) :: []
[(10, 2), (45, 1), (5, 1), (32, 1), (2, 1), (17, 2), (22, 1), (38, 1)]

This has very poor runtime complexity, since it involves looping within a loop. Consider whether tallying a list would be easier if the list were sorted first.

If it is sorted, then our sample becomes:

val numbers = [2, 5, 10, 10, 17, 17, 22, 32, 38, 45]

Now, to tally this list, we just need to use an accumulator.

fun tally([], acc) = List.rev acc
  | tally(x::xs, []) = tally(xs, [(x, 1)])
  | tally(x::xs, (acc as (y, c)::ys)) =
    if x = y then 
      tally(xs, (y, c+1)::ys)
    else 
      tally(xs, (x, 1)::acc)

This is accomplished in linear time. The sorting takes O(n * log n) time, but that's better than O(n^2) time with the nested looping.

It can be called as:

tally([2, 5, 10, 10, 17, 17, 22, 32, 38, 45], [])
tally([5, 10, 10, 17, 17, 22, 32, 38, 45], [(2, 1)])
tally([10, 10, 17, 17, 22, 32, 38, 45], [(5, 1), (2, 1)])
tally([10, 17, 17, 22, 32, 38, 45], [(10, 1), (5, 1), (2, 1)])
tally([17, 17, 22, 32, 38, 45], [(10, 2), (5, 1), (2, 1)])
tally([17, 22, 32, 38, 45], [(17, 1), (10, 2), (5, 1), (2, 1)])
tally([22, 32, 38, 45], [(17, 2), (10, 2), (5, 1), (2, 1)])
tally([32, 38, 45], [(22, 1), (17, 2), (10, 2), (5, 1), (2, 1)])
tally([38, 45], [(32, 1), (22, 1), (17, 2), (10, 2), (5, 1), (2, 1)])
tally([45], [(38, 1), (32, 1), (22, 1), (17, 2), (10, 2), (5, 1), (2, 1)])
tally([], [(45, 1), (38, 1), (32, 1), (22, 1), (17, 2), (10, 2), (5, 1), (2, 1)])
[(2, 1), (5, 1), (10, 2), (17, 2), (22, 1), (32, 1), (38, 1), (45, 1)]