CODEWITHSUNDEEP
f#
Tim Coker
Tim Coker

Reputation: 6524

Confusing anonymous function construct

I'm reading through an F# tutorial, and ran into an example of syntax that I don't understand. The link to the page I'm reading is at the bottom. Here's the example from that page:

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

// test code        
printfn "%A" (quicksort2 [1;5;23;18;9;1;3])

The part I don't understand is this: ((>=) first). What exactly is this? For contrast, this is an example from the MSDN documentation for List.partition:

let list1 = [ 1 .. 10 ]
let listEven, listOdd = List.partition (fun elem -> elem % 2 = 0) list1
printfn "Evens: %A\nOdds: %A" listEven listOdd

The first parameter (is this the right terminology?) to List.partition is obviously an anonymous function. I rewrote the line in question as this:

let smaller,larger = List.partition (fun e -> first >= e) rest

and it works the same as the example above. I just don't understand how this construct accomplishes the same thing: ((>=) first)

http://fsharpforfunandprofit.com/posts/fvsc-quicksort/

Upvotes: 4

Views: 109

Answers (2)

Fyodor Soikin
Fyodor Soikin

Reputation: 80915

This construct combines two features: operator call with prefix notation and partial function application.

First, let's look at calling operators with prefix notation. 

let x = a + b

The above code calls operator + with two arguments, a and b. Since this is a functional language, everything is a function, including operators, including operator +. It's just that operators have this funny call syntax, where you put the function between the arguments instead of in front of them. But you can still treat the operator just as any other normal function. To do that, you need to enclose it on parentheses:

let x = (+) a b     // same thing as a + b.

And when I say "as any other function", I totally mean it:

let f = (+)
let x = f a b     // still same thing.

Next, let's look at partial function application. Consider this function:

let f x y = x + y

We can call it and get a number in return:

let a = f 5 6    // a = 11

But we can also "almost" call it by supplying only one of two arguments:

let a = f 5    // a is a function
let b = a 6   // b = 11

The result of such "almost call" (technically called "partial application") is another function that still expects the remaining arguments.

And now, let's combine the two:

let a = (+) 5    // a is a function
let b = a 6      // b = 11

In general, one can write the following equivalency:

(+) x    ===    fun y -> x + y

Or, similarly, for your specific case:

(>=) first     ===     fun y -> first >= y

Upvotes: 3

Sehnsucht
Sehnsucht

Reputation: 5049

That's roughly the same thing as infix notation vs prefix notation
Operator are functions too and follow the same rule (ie. they can be partially applied)

So here (>=) first is the operator >= with first already applied as "first" operand, and gives back a function waiting for the second operand of the operator as you noticed when rewriting that line.

Upvotes: 5

Related Questions