4
\$\begingroup\$

I have written this InsertSort program in F#. It works, but I am not very happy with it.

let rec SubArrayBegin list n =
    list |> Seq.ofList |> Seq.take n |> List.ofSeq

let SubArrayEnd list n =     
    List.rev (SubArrayBegin (List.rev list) ((List.length list) - n - 1))

let InsertSort list = 
    let rec innerInsertSort list n = 
        if n = (List.length list) then
            list
        else
            let key = List.nth list n
            let firstList = SubArrayBegin list n
            let (firstListA, firstListB) = List.partition (fun x -> x < key) firstList
            let remList = SubArrayEnd list n
            innerInsertSort (firstListA @ [key] @ firstListB @ remList) (n + 1)
    innerInsertSort list 1


[<EntryPoint>]
let main args = 
    let a = [10; 2; 9; 1; 4; 5; -1]
    let b = InsertSort a
    List.iter (fun x -> printfn "%i" x) b
    0

List of annoyances:

  1. @ symbol for joining the lists back.
  2. If Condition being used instead of pattern matching.

I wonder if there is a better way of writing this.

Can you please review this and help me improve this code?

\$\endgroup\$
2
  • \$\begingroup\$ What's wrong with @ and if? \$\endgroup\$
    – svick
    Dec 21, 2013 at 11:50
  • \$\begingroup\$ @ makes copy of the entire list when it joins the arrays. :: is better but I was not able to use it. functional programmers can write lot of stuff without using if. they tend to use pattern matching for conditionals rather than if. \$\endgroup\$ Dec 22, 2013 at 1:55

2 Answers 2

1
\$\begingroup\$
  1. Function names in F# are usually written in camelCase. (Though members that are not private should use PascalCase, to adhere to general .Net naming conventions.)
  2. SubArrayBegin is not recursive, so it doesn't need to be rec.
  3. List implements Seq, so you don't need that Seq.ofList.
  4. Collection manipulation functions usually have that collection as the last parameter, so that you can use them with |>.
  5. Your implementation of SubArrayEnd is pretty complicated and inefficient. Instead, you could write it for example like this:

    let rec subArrayEnd n list =
        match (n, list) with
        | 0, _ | _, [] -> list
        | _ -> subArrayEnd (n-1) (List.tail list)
    
  6. There is no reason why your innerInsertSort has to follow the normal imperative version of insert sort so closely and operate on a single list (and use List.nth). Instead, you could have two collections: one where you take from using pattern matching and one where you insert using List.partition and @.
  7. Alternatively, you could use ImmutableList from Microsoft.Bcl.Immutable instead of List for the collection you're inserting into. With that, you can insert into the middle in O(log n) and you can also find the index to insert to in O(log n) using binary search. So it will make your code simpler and also much faster.
\$\endgroup\$
1
\$\begingroup\$

Thank you so much Svick .... Based on your inputs I changed my code to

let insertSorted n list = 
    let (a, b) = List.partition (fun x -> x < n) (n :: list) 
    List.append a b

let insertSort list =
    let rec innerInsertSort sorted = function
    | [] -> sorted
    | hd :: tl -> 
        innerInsertSort (insertSorted hd sorted) tl 
    innerInsertSort [List.head list] (List.tail list)

[<EntryPoint>]
let main args = 
    printfn "%s" (List.fold (fun acc elem -> acc + " " + elem.ToString()) "" (insertSort [10; 7; 1; 0; -1; 9; 33; 12; 6; 2; 3]))
    0

Now I don't need List.nth or SubArrayBegin or SubArrayEnd.

I use the two lists input which you gave me in point 6.

Let me know your thoughts... but I am very happy with this code above because it is quite concise and is not so imperative as my first version.

\$\endgroup\$
1
  • \$\begingroup\$ This code won't work if list is empty. \$\endgroup\$
    – svick
    Dec 22, 2013 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.