1
\$\begingroup\$

I made a simple insertion sort in F#, it uses a tail recursive shift function that attempts to shift an element in a list until it is in the right order. Would like some feedback on the design.

let insertionSort xs =
    let shiftInsert xs x =
        let rec shift xs x f =
            match xs with
            | [] ->
                f() @ [x]
            | hd::tl ->
                if x < hd then
                    f() @ x::hd::tl
                else
                    shift tl x (fun () -> f() @ [hd])
        shift xs x (fun () -> [])
    List.fold shiftInsert [] xs
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Have you thought about changing the structure to remove the use of @ \$\endgroup\$ Sep 23, 2016 at 22:23
  • \$\begingroup\$ @JohnPalmer Hm no, I haven't really thought of a way of doing that and maintaining the brevity. \$\endgroup\$ Sep 25, 2016 at 10:22
  • \$\begingroup\$ if you fit any of the answers, you have to accept it \$\endgroup\$
    – user110704
    Oct 17, 2016 at 14:48

2 Answers 2

1
\$\begingroup\$
  1. Why do you always create a function f :

    shift tl x (fun () -> f() @ [hd])

    f() @ x::hd::tl

  2. In your inner function shift the parameter x is not used - you don't need to pass it each time you call.

So, you can rewrite as:

let insertionSort xs =
    let shiftInsert xs x =
        let rec shift xs f =
            match xs with
            | [] ->
                f @ [x]
            | hd::tl ->
                if x < hd then
                    f @ x::hd::tl
                else
                    shift tl (f @ [hd])
        shift xs []
    List.fold shiftInsert [] xs

As @JohnPalmer written in the comments instead of @ better to change the algorithm with using operator "::"

let insertionSort xs =
    let shiftInsert xs x =
        let rec shift xs acc isAdd =
            match xs, isAdd with
            | [], true -> acc
            | [], false -> x::acc
            | h::t, false -> 
                if h <= x then
                    shift t (h::acc) false
                else
                    shift t (h::x::acc) true
            |h::t,true -> 
                shift t (h::acc) true
        shift xs [] false
        |> List.rev
    List.fold shiftInsert [] xs
\$\endgroup\$
0
\$\begingroup\$

I'm not sure if the objective was insertion sort or tail recusion? In any case the performance is rather bad for larger data sets.

If insertion sort was the focus the following approach is maybe somewhat more straightforward:

let insertionSort xs =
  let fold res x =
    let index = res |> List.tryFindIndex (fun n -> n > x)
    match index with
    | None -> res @ [x]
    | Some i -> 
        let start, tail = res |> List.splitAt i
        start @ x :: tail

  xs |> List.fold fold []
\$\endgroup\$

Your Answer

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

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