List manipulation in F#

Question

What I'm hoping to make this function do is:

1. Generate a list of random integers of length specified by count

2. Generate another random number to replace first element of list

3. Sort the list

4. Split list in half, discarding second half

5. Discard first element of list

6. Repeat 2-5 unless list is empty

What I have so far (but not working) is below. What is the matter with it?

let go count =
    let rec cut l = 
        if List.length l = 0 then l
        printfn "%A" l
        let list = System.Random().Next(100)::List.tail l
        let cut list = 
            let firstHalf= list |> Seq.take (List.length list / 2) |> Seq.toList
            firstHalf
        let listSorted = List.sort list
        cut (List.tail listSorted)
    let r = System.Random()
    let list1 = List.init count (fun numbers -> r.Next(100))
    printfn "List = %A" list1
    cut list1

Answer 1

A few tips:

• Don't test if a list is empty by List.length L = 0. Each test will take as long as the amount of elements in the list. Test with pattern matching instead, that's (almost) instantanteous:

• Don't instantiate a new instance of a random number generator each time your cut function is called: let list = System.Random().... Doing that means that you're likely to get the same numbers (each instantiaion seeds the generator with the current system time). Just move your declaration r = System.Random() up a bit, and use that generator throughout your code.

example:

let rec cut l =
    match l with
    | [] -> // the list is empty, end the recursion here
    | head::tail -> // the list consists of the head element and the rest
                    // you can refer to head and tail in your code here
                    let newlist = r.next(100) :: tail

• You're declaring a function called 'cut' inside your recursive 'cut' function, which means that the last call to 'cut' in your recursive function actually calls the non-recursive one you defined inside. Use different names there.

• You've written 'if List.length l = 0 then l', which (apart from not using a pattern match) also presents a problem: an 'if' in F# is an expression, like the ? operator in C#. In C# that would mean something like

  (l.Count == 0) ? l : //other case missing! error! danger!

• Another tip: once your list is sorted, you don't need to sort again each time you add a new random element. You can write code that inserts a new element in a sorted list that would be more efficient than adding an element and sorting afterwards. I'll leave the insert-into-sorted-list as an excercise.

I hope these tips are useful.