CODEWITHSUNDEEP
listrecursionf#
Danny
Danny

Reputation: 3665

List manipulation in F#

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

Upvotes: 6

Views: 1048

Answers (4)

cnd
cnd

Reputation: 33754

here is my try... 

let go count = 
    System.Random() |> fun rnd ->  // With ranomizer ... (we will need it)
        let rec repeat = function  // So we got recursion 
            | x::xs when xs.Length <> 1 ->       // while we have head and tail
                printfn "%A" xs
                rnd .Next(100) :: (List.tail xs) // Add random value
                |> Seq.sort                      // Sort
                |> Seq.take( abs(xs.Length /2) ) // Make a half
                |> Seq.skip 1                    // Remove first (just skip)
                |> List.ofSeq                    // Make the list
                |> repeat                        // So and repeat
            | x::xs -> printfn "%A" xs
            | _ -> ()              // If we have no head and tail
        repeat <| List.init count (fun _ -> rnd.Next(100)) // do it with our random list

Upvotes: 2

Ankur
Ankur

Reputation: 33637

Here it is as simple as making functions for each of your statements.

let rnd = new System.Random()

let genList n = 
    [for i = 0 to n-1 do yield rnd.Next()]

let replaceHead v lst = match lst with
                        | [] -> []
                        | (x::xs) -> (v::xs)

let splitInHalf lst = 
    let len = (lst |> List.length) / 2
    let rec loop n lst = 
        match (n,lst) with
        | 0,_ -> []
        | _,[] -> []
        | _,(x::xs) -> x :: (loop (n-1) xs)
    loop len lst


let start n = 
    let lst = genList n
    let rec loop l = 
        match l with
        | [] -> []
        | ls -> match ls |> replaceHead (rnd.Next()) 
                         |> List.sort 
                         |> splitInHalf with
                | [] -> []
                | xs -> xs |> List.tail |> loop

    loop lst

start 1

Upvotes: 2

cfern
cfern

Reputation: 6006

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.

Upvotes: 7

Huusom
Huusom

Reputation: 5912

It does look like homework :) But here is my take on it:

#light

// Create random integer sequence
let random_integers_of_length l  = 
    (l, new System.Random()) 
        |> Seq.unfold (fun (c, rnd) -> if c = 0 then None else Some (rnd.Next(), (c-1, rnd))) 
        |> Seq.cache

let rec mutate numbers =
    printfn "%A" (List.ofSeq numbers);                          // pretty print the list
    match numbers with                                  
    | _ when (Seq.length numbers) <= 1 -> printfn "Done.."      // if length is 1 or 0 we can stop.
    | _ ->
        numbers
            |> Seq.skip 1                                       // discard first element 
            |> Seq.append (random_integers_of_length 1)         // append random number at the start 
            |> Seq.sort                                         // sort 
            |> Seq.take ((Seq.length numbers) / 2)              // take the first half, ignore the rest
            |> Seq.skip 1                                       // discard first element 
            |> mutate                                           // do it again.

Upvotes: 0

Related Questions