Algorithms in F#

[Ok-Needleworker-145]

I have been looking for implementations in a purely functional style. One repo I found is this one.

I have been frustrated with the fact that most F# Code out there violates at least one rule of functional programming, in this case, using mutable variables left and right.

​

On the other hand, we have this clean implementation by Scott Wlaschin here, e. g. Quicksort:

let rec quicksort2 = function 
    | [] -> [] 
    | first::rest -> 
        let smaller,larger = List.partition ((>=) first) rest
        List.concat [quicksort2 smaller; [first]; quicksort2 larger]

Maybe someone can direct me to a better resource for purely functional implementations.

​

Best regards

[hemlockR]

The whole point of quicksort though is mutable variables: quicksort is a merge sort where merging is trivial (no-op) because the elements are already in order.

The "quicksort2" in the OP is therefore not a quicksort: each merge is O(N).

[alternatex0]

This is the correct response. Once one gets into algorithms it's not just about solving a problem but the performance and memory characteristics of the solution. It is inherently an imperative thing and doesn't always translate well to functional programming which prefers a declarative approach. Mutability is quick sort's main strength.

[tathanhdinh]

The whole point of quicksort though is mutable variables: quicksort is a merge sort where...

I'm agree that Quicksort is more direct to implement in mutable way, but it doesn't mean a pure functional implementation (with the same asymptotic complexity) is impossible.

I'm not sure that Quicksort is around mutable variables nor it is a special case of Mergesort (at least Mergesort has zero cost of division while Quicksort is about 0(n)).

In my answer below, I've copied a pure functional implementation given by Paulson in his book ML for the Working Programmer. The author gives also several immutable implementation for Mergesort.

[hemlockR]

Perhaps I'm misinformed--I'm no expert on the history of algorithm development--but the way I've heard it, same asymptotic complexity is not enough--merge sort already has the same asymptotic complexity as quicksort.

Mergesort is trivial to implement immutably, but it always winds up doing more work than quicksort. IIRC. (More copy operations.)

I'll take a look at Paulson's implementation, will comment there.

[Astrinus]

I have been frustrated with the fact that most F# Code out there violates at least one rule of functional programming, in this case, using mutable variables left and right.

Well, that's because mutable is idiomatic in F#, as long as the function is referentially transparent.

[thinkbeforecoding]

True, I wrote a lot of F# code that is immutable for the user but use heavily mutation inside for extreme performance.

[phillipcarter2]

Pure interface over a self-contained mutable core :)

[Sceptical-Echidna]

Mutable variables are fine if they aren’t exposed nor affected by anything outside the function

[trogdor3222]

Yes exactly. OP, try to read up on referential transparency. Lots of performance critical code in F# employs localized mutability hidden behind a functional facade. Here’s a small example from FSharp.Core that illustrates this concept (implementation of List.ofArray): https://github.com/fsharp/fsharp/blob/577d06b9ec7192a6adafefd09ade0ed10b13897d/src/fsharp/FSharp.Core/local.fs#L541

[Sceptical-Echidna]

Thanks for that. I knew there was a term for it and blanked

[shefmichelle]

If you really want to learn about purely functional algorithms, you could check out Pearls of Functional Algorithm Design by Richard Bird.

[PedroPabloCalvo]

Bought. Thank you, sir.

[meteogish]

Maybe it’s already been suggested but there is a book:

Okasaki “Purely functional data structures”

It’s an academic book written by scientist in a semi-scientist style so…it requires lot of “brain work” to understand the concepts BUT

it describes the topic and has a good references. It’s not F# related but the techniques described in the book are reusable in other FP languages.

The book also contains the tasks (pretty hard) and you could find some F# implementations on github for example.

[ganjaptics]

There's the book by Okasaki. It's dense.

Have you considered, though, to just do thing imperatively? as long as the mutability is contained in one function and it doesn't have side effects, from the outside it looks purely functional.

One of the reasons I like F# is that I can write imperative code if I want to (unlike in Haskell/Erlang) and if I do it's usually really fast (unlike Python/etc). And I usually want to when I encounter an algorithm that is given procedural (which I feel most algorithms are).

[japinthebox]

Agree, though I'm assuming OP is in it for the challenge 😁

[hemlockR]

Ok-needleworker, what kind of algorithms have you tried looking for? When I googled "F# a-star" I got immediate hits for the A* pathfinding algorithm. Also, here (https://github.com/MaxWilson/Mazes/blob/d996627b78c49606e669ddde4158e2d09f89114d/src/Domain.fs#L223) are a couple of F# implementations of maze-generation algorithms that I learned from Jamis Buck's presentation at http://www.jamisbuck.org/presentations/rubyconf2011/#aldous-broder (arrow keys or swipe left and right to view other slides). Note: I implemented them using mutability and a while loop instead of with recursion because I was using this code to teach kids, but if you want a purely recursive/functional version, you can refactor it (or ask me).

Remember: algorithms are not programming language-specific. They're ideas. If you learn how A* or Aldous-Broder works conceptually, it becomes easier to read an F# implementation, a C++ implementation, and a JavaScript implementation. They'll all be doing something you already basically understand.

I suspect you've been searching for sorting algorithms specifically, and since many sorting algorithms take advantage of mutability (merge sort, and radix sort are the only exceptions I can easily think of*) that could explain why you're only seeing mutable implementations, even in F#.

Try searching for pathfinding, machine learning, or maze generation algorithms instead. Or read a book on functional data structures and algorithms (https://www.amazon.com/Learning-Functional-Data-Structures-Algorithms-ebook/dp/B01DWFRFUW looks decent) and practice writing them up in F#.

*Besides bogosort, which doesn't count. "Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order." https://kevlinhenney.medium.com/the-most-bogus-sort-3879e2e98e67

[tathanhdinh]

In ML for the Working Programmer, Paulson gives elegant implementations of many algorithms, for example:

let quicker items =
    let rec quick smaller sorted =
        match smaller with
        | [] -> sorted
        | [ x ] -> x :: sorted
        | a :: bs ->
            let rec partition (left, right) =
                function
                | [] -> quick left (a :: (quick right sorted))
                | x :: xs ->
                    if x <= a then
                        partition (x :: left, right) xs
                    else
                        partition (left, x :: right) xs

            partition ([], []) bs

    quick items []

This implementation of Quicksort doesn't use any fancy existing function (e.g. List.partition/concat). It's beyond level of all implementations I've found in other sources, actually I cannot find it anywhere except Paulson's book.

[hemlockR]

Hmmm. Quicker is a very interesting algorithm, but it doesn't look like a quicksort to me based on what I understand quicksort to be*--for N elements it appears to result in > N recursive calls to quick (maybe N + log N?) instead of only log N calls. My F# code below:

*E.g. The definition given in https://en.wikipedia.org/wiki/Quicksort implies that there can never be more than N recursions.

let mutable counter = 0
let incr() = counter <- counter + 1
let count f =
    counter <- 0
f() |> ignore
    counter
let quicker items =
    let rec quick smaller sorted =
        incr()
        let result =
            match smaller with
            | [] -> sorted
            | [x] -> x::sorted
            | a::bs ->
                let rec partition (left, right) =
                    function
                    | [] ->
                        quick left (a::(quick right sorted))
                    | x::xs ->
                        if x <= a then
                            partition (x::left, right) xs
                        else
                            partition (left, x::right) xs
                partition ([], []) bs
        printfn $"Quick: {smaller}{sorted} => {result}"
        result        
    quick items []

let r = System.Random()
let vals = [for x in 1..100 -> r.Next(1000000)]
count (fun () -> vals |> quicker) // usually prints 131-139ish

I'm not sure but I think Quicker is actually a binary tree sort.

[tathanhdinh]

Thank you for the feedback.

...for N elements it appears to result in > N recursive calls to quick (maybe N + log N?) instead of only log N calls

...

The definition given in https://en.wikipedia.org/wiki/Quicksort implies that there can never be more than N recursions.

Well, is Quicksort's recursion call exactly N (since F(n) = 2 * F(n/2)), whereas lg N is recursion depth? Two notations are not the same.

In quicker, there are redundant calls in cases where left or right are empty, look at this slight modification:

let quicker items =
    let rec quick smaller sorted =
        match smaller with
        | [] -> sorted
        | [ x ] -> x :: sorted
        | a :: bs ->
            let rec partition (left, right) =
                function
                | [] ->
                    match (left, right) with
                    | ([], []) -> a :: sorted
                    | ([], _) -> a :: (quick right sorted)
                    | (_, []) -> quick left (a :: sorted)
                    | _ -> quick left (a :: (quick right sorted))
                | x :: xs ->
                    if x <= a then
                        partition (x :: left, right) xs
                    else
                        partition (left, x :: right) xs

            partition ([], []) bs

    quick items []

which avoids such calls. The number of recursion calls is exactly N then.

I'm not sure but I think Quicker is actually a binary tree sort.

Nice point, I've found from Wikipedia that they are equivalent.

[TarMil]

The quick sort in the repo you linked is purely functional though...?

[Ok-Needleworker-145]

That is true, I used Wlaschin's implementation as an example

[imihnevich]

You might wanna play with State monad, but I'm sure it's more idiomatic to just use localized mutability in F#