(Kestrel) K-combinator: why is it useful?

Question

I have been taking up F# recently (my background is C#) and am reading the site http://fsharpforfunandprofit.com, which I am finding very helpful.

I've got to http://fsharpforfunandprofit.com/posts/defining-functions/ which is the section on combinators. I understand them all (although the Y combinator or Sage bird screws with my mind!) with the exception of the Kestrel. Scott Wlaschin gives the definition (in F#) as:

let K x y = x

I can't understand for the life of me any situation in which this would be useful. At first I thought it might be used as chain operator, so that you can pass a value to a function and then get back the original value. I've written such an operator myself before, but as you can see it's not the same:

let (>|) x f = f x; x

If we partially apply the K combinator (with the value 5) then we get back a function that ignores its argument and instead returns 5. Again, not useful.

(K 5) = fun y -> 5

Can anyone give me an easy example of where this might be used please?

Housum

:D have a look at this: en.wikipedia.org/wiki/SKI_combinator_calculus - it's really just academic fun - even if you find some uses in F# you should not call it just K ^^ – Anarchy

BTW if you don't find it right away - K is for example used to implement things like booleans, tuples, numbers, ... in the SKI calculuse (well it's a basic building block ;) ) - just think of it as a kind of projection to the first component – Anarchy

Thanks, I'd read the Wikipedia page but it didn't give any more information than I already had. – Housum

What exactly do you want to know (this is a huge topic) – Anarchy

The K-Combinator becomes useful when used with partial application. It sets up a 'start over' function. – Butterball

This is called 'const' or 'konst' is most systems, for 80 years now. 'Kestrel' is a terrible name, imo. – Addict

Answer 1

Here is a very easy example:

Let's suppose I have a structure, like a list where I can map functions.

let K x y = x

let lst = [3;5;13;2]

I can map math functions like this:

let plus5  = lst |> List.map ((+)5) // instead of writing List.map (fun x -> 5 + x)
// val plus5 : int list = [8; 10; 18; 7]

let times3 = lst |> List.map ((*)3) // instead of writing List.map (fun x -> 3 * x)
// val times3 : int list = [9; 15; 39; 6]

What if I want to map a constant function?

let tens = lst |> List.map (K 10) // instead of writing List.map (fun x -> 10)
// val tens : int list = [10; 10; 10; 10]

Given that in FP you typically pass functions as arguments, the K combinator allows you to specify a constant function with a few keystrokes.

Voroshilovsk

Thanks Gustavo, that did occur to me too, it's times like that when I would use id as well (such as lst |> sortBy id) but still wasn't getting the point of a constant function in a map. The equivalent SQL would be select 5 from dbo.Customers. Maybe I'll keep thinking. – Housum

Yes, that's kind of equivalent in SQL, but in FP you can compose functions in such a way that you can separate the logic of a rule evaluator and a rule. Think the rules as functions and you may have a straightforward rule which doesn't need an additional parameter. I use the K combinator from time to time in cases like that to avoid repeating my self writing fun x -> something – Voroshilovsk

while true and a nice example in the real situation you would of course use the much more readable List.replicate 4 10 (or 10 |> List.replicate 4) – Anarchy

True, or just write [10;10;10;10] but then I'm no longer mapping functions. – Voroshilovsk

Thanks for your input guys. I guess the reason I'm really struggling is that, although I feel that I understand the F# language well, I still haven't done very much functional programming, and I've never written a function like fun x -> something. I'll get it one day :) – Housum