Practical use of K-combinator (Kestrel) in javascript

Question

The K-combinator can be implemented as below and the implementation should not have any side-effects.

const K = x => y => x;

It is sometimes called "const" (as in Haskell). The K function might be defined as, "takes a value and returns a (constant) unary function that always returns that value."

When is it useful? Please help me with practical examples.

Catto

cs.stackexchange.com/questions/55441/… – Joby

It looks like CL function constanty which is quite useful sometimes. – Badenpowell

In curried languages, you'd use it whenever you want a callback to ignore the first argument. – Atomizer

Answer 1

Sort of an broad question, but it's nice, I like it.

To support my example, in this answer I'm going to implement …

abuild :: Number -> (Number -> a) -> [a]

… which as the type suggests, takes a number and a function to build an array. This could be useful if you want to build an array of a known size based on some computation.

---

Let's build an array with 5 elements using the identity function, id. As you can see, a sequential numerical index starting with 0 is given to your builder function

abuild (5) (id) // => [0,1,2,3,4]

Let's do something mathy with the builder this time. We'll square the input. Very advanced.

abuild (5) (x=> x * x)
// => [0,1,4,9,16]

Or maybe we don't care about the input. I always love a good laugh. I laugh at things constantly. One could say I K('ha') …

abuild (5) (K('ha'))
// => ['ha','ha','ha','ha','ha']

Boom ! Pretty useful, right? That's K

---

Implementation

Go ahead and run it to see K in action!

// id :: a -> a
const id = x=> x

// K :: a -> b -> a
const K = x=> y=> x

// add :: Number -> Number -> Number
const add = x=> y=> y + x

// reduce :: (a -> b) -> b -> [a] -> b 
const reduce = f=> y=> ([x,...xs])=> {
  if (x === undefined)
    return y
  else
    return reduce (f) (f (y) (x)) (xs)
}

// map :: (a -> b) -> [a] -> [b]
const map = f=> reduce (xs=> x=> [...xs, f(x)]) ([])

// iterate :: Number -> (a -> a) -> a -> [a]
const iterate = n=> f=> x=>
  n > 0 ? [x, ...iterate (n - 1) (f) (f(x))] : []

// abuild :: Number -> (Number -> a) -> [a]
const abuild = n=> f=>
  map (f) (iterate (n) (add (1)) (0))

console.log(abuild (5) (id))
// => [0,1,2,3,4]

console.log(abuild (5) (x=> x * x))
// => [0,1,4,9,16]

console.log(abuild (5) (K('ha')))
// => ['ha','ha','ha','ha','ha']

Gumbo

I like functions with humor :D Is K("ha") laughing with or about someone?! – Gunshy

It is only a little insight into me ! I like to make light of any situation ^_^ – Gumbo

But how is generating ["ha", "ha", "ha"] useful? – Textbook

Answer 2

The problem with K as with all primitive combinators is that you can't consider it on its own. Primitive combinators are the fundamental building blocks of functional programming. You need a proper context to watch them at work. The challenge is to grok this context, if you are new to the functional paradigm.

Here is a "typical context": Option. Instances of the Option type are like values that may be null, but never throw an error when applied to a function:

// the option type

const Option = {
  some: Symbol.for("ftor/Option.some"),

  none: Symbol.for("ftor/Option.none"),

  of: x => factory(Option.some) (x),

  cata: pattern => o => pattern[o.tag](o.x),

  fold: f => g => o => Option.cata({[Option.some]: f, [Option.none]: g}) (o),

  map: f => o => Option.fold(x => Option.of(f(x))) (K(o)) (o)
  //                                                ^^^^
}


// a generic map function

const map = type => f => o => type.map(f) (o);


// functor factory

const factory = tag => value => (
  {x: value === undefined ? null : value, tag: tag}
);


// auxiliary functions

const K = x => y => x;
const sqr = x => x * x;


// a few data to play around

const o = factory(Option.some) (5);
const p = factory(Option.none) ();



// and run

let r1 = map(Option) (sqr) (o);
let r2 = map(Option) (sqr) (p);

console.log("map over o", r1);
console.log("map over p", r2);

What does K do in this implementation? Let's examine the crucial line:

f => o => Option.fold(x => Option.of(f(x))) (K(o)) (o)

Option.fold expects two functions. The first passed function x => Option.of(f(x)) is for the some case (there is a value). The second K(o) for the none case (there is no value). Let's recall that K expects two argument K = x => y => {return x}. K(o) assigns o to x. No matter what is passed as second argument, K will always ignore y and return x instead.

But what does o represent in the expression K(o)? It represents Option.none that is, the absence of a value. So when someone tries to map a function f over none, none is just returned, no matter what f passes as second argument to K.

Gunshy

Where is the precondition function "precon"? – Catto

Answer 3

K combinator can be also used as truth-value, when using church-encoded booleans. I.e. IF-TEST THEN ELSE: if your "IF-TEST" returns K, then "else" would be dropped and "then" would be executed.

Stitch

Answer 4

Suppose you have an array of numbers xs:

[10, 5, 12, 7]

You need to transform it in two ways:

xs.map(x => x % 2 == 0 ? x + 1 : x + 2);
//=> [11, 7, 13, 9]

xs.map(x => x % 2 == 0 ? x + 10 : x + 20);
//=> [20, 25, 22, 27]

I'll quickly acknowledge that the ternary expressions are probably just fine but for the purpose of answering the question I'll make them pointfree:

const ifelse = (p, t, f) => x => p(x) ? t(x) : f(x);
const add = a => x => a + x;
const even = x => x % 2 == 0;

xs.map(ifelse(even, add(1), add(2)));
//=> [11, 7, 13, 9]

xs.map(ifelse(even, add(10), add(20)));
//=> [20, 25, 22, 27]

Now let's say that we just want to return 'even' or 'odd':

xs.map(ifelse(even, () => 'even', () => 'odd'));
//=> ['even', 'odd', 'even', 'odd']

The two lambdas behave in the same way: they completely ignore x and always return the same value. This is exactly what the Kestrel combinator is about:

const K = a => x => a;

xs.map(ifelse(even, K('even'), K('odd')));
//=> ['even', 'odd', 'even', 'odd']

Hundredweight

Answer 5

This seems to be the always function in the Ramda javascript library, because it always returns the same thing.

I've used it a couple of times in my current (typescript) project, basically to have a constant value in places where the typings expect a function.

To display a table column named Quantity where all lines have 1 as a quantity. The column definition has a compute: always(1) property.

To initialize a react state that tracks if a cell has been saved or not.

const initialSavedState = (listData: Base[]) => listData.map(always(CellSavedState.NotSaved))

const [savedState, setSavedState] = useState<CellSavedState[]>(initialSavedState(listData))

There are a lot of tiny functions in Ramda, like identity, identical, add, etc. that don't do more than the language can do with its syntax.

Since ES6 you can just to this in javascript () => undefined instead of always(undefined), or something => something instead of identity(something).

But if you like having the word "identity" or "always", if you feel like it makes the code clearer then why not?

Even the add function that supports multiple arguments or currying with one argument, isn't too useful when you can just do something like this: (a) => a + 5.

Even for something like map, sometimes it feels better to use the standard .map javascript, or sometimes the Ramda map function. It's up to you in the end.

Asteriated