1
\$\begingroup\$

I have written this code for BubbleSort in F#. Can you review and let me know how I can do this in most functional way.

let rec getHighest list = 
    match list with
    | [x] -> x
    | [x; y] when x > y -> x 
    | [x; y] -> y
    | hd1 :: hd2 :: tl when hd1 > hd2 -> getHighest (hd1 :: tl)
    | hd1 :: tl -> getHighest tl
    | _ -> failwith "unknown pattern"

let bubbleSort list = 
    let rec innerBubbleSort sorted = function
    | [] -> sorted
    | l -> 
        let x = getHighest l
        let (a, b) = List.partition (fun i -> i = x) l
        innerBubbleSort (a @ sorted) b
    innerBubbleSort [] list

[<EntryPoint>]
let main args = 
    let input = [10; 7; 1; 0; -1; 9; 33; 12; 6; 2; 3; 33; 34;]
    let output = bubbleSort input
    printfn "%s" (List.fold (fun acc x -> acc + " " + x.ToString()) "" output)
    0
\$\endgroup\$
1
\$\begingroup\$

The first part could be rewritten as

match list with
| hd1 :: hd2 :: tl when hd1 > hd2 -> getHighest (hd1 :: tl)
| hd1 :: hd2 :: tl -> getHighest (hd2::t1)
| hd1 :: [] -> hd1
| _ -> failwith "unknown pattern"

which is significantly simpler

\$\endgroup\$
  • \$\begingroup\$ even simpler if you replace the first two patterns with a single one: | hd1::hd2::tl -> let hd = if hd1 > hd2 then hd1 else hd2 in getHighest (hd::tl) \$\endgroup\$ – scrwtp Dec 29 '13 at 22:32
1
\$\begingroup\$

I think a cleaner way to write getHighest would be to use accumulator:

let getHighest list =
    let rec getHighestImpl list highest =
        match list with
        | [] -> highest
        | head::tail -> getHighestImpl tail (max head highest)
    getHighestImpl (List.tail list) (List.head list)

You could also use the version of this function that already exists in the library: List.max.


This is not bubble sort. In bubble sort, you compare neighboring items and swap them if they're in the wrong order. You do something similar in your getHighest, but you don't preserve the swaps. So, in the end, your algorithm is closer to selection sort, than bubble sort.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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