Function.prototype.compose

gabejohnson commented 7 years ago

This seems like a no-brainer. However, there're some things to consider:

Argument order
Static method?
Arity of composed functions
Arity of composing functions

Argument order

The newly introduced Semigroupoid specification gives an argument order of g.compose(f). I think this is fine. Dispatching functions (Ramda, Sanctuary, etc.) will flip the order anyway.

Static method?

Another possibility is to put this functionality on the Function object

Function.compose(f, g);
// equivalent to
g.compose(f);

Given the long-time variadic bent, I would expect (with my "pragmatic" JS dev hat on) to be able to pass n arguments to Function.compose

Function.compose(f, g, h);
// equivalent to
h.compose(g).compose(f);

Arity of composed functions

My thinking is compose is a binary method as laid out in the spec. See (2).

Arity of composing functions

The obvious answer is1. Another possibility is n for the first applied function and1 for the rest. A counter-intuitive option is to have no restriction. This would prevent future incompatibility. Imagine a native Tuple type and a future where

const sqr = x => x*x;
sqr 5; // 25

const sum = (x=0, ...xs) => xs.length === 0 ? x : sum(...xs);
const t = #(1,2,3,4);
sum t; // 10

const triple = x => #(x, x, x);
sqr.compose(triple).compose(sum)(5); // 75

const either = f => g => (l, r) => r == null ? l : r;
const right = #(null, 42);
const left = #("fail", null);

const incEither = either (x => x + 1) console.error.bind(console);
incEither right; // 43
incEither left; // "fail"

The above allows for an unrealistically FP friendly future, but I don't see the immediate requirement for an arity restriction (save "type" checking). Having such a restriction would rule out this possibility.

Edit: relabel/reorder section headings Edit: "Static function?" -> "Static method?" Edit: Remove "obviously"

gabejohnson commented 7 years ago

/cc @JAForbes @michaelficarra @i-am-tom

gabejohnson commented 7 years ago

Compiler support to do some sort of code fusion or stack frame reuse would be helpful for deep function composition trees.

i-am-tom commented 7 years ago

My immediate thought was that this is duplication of fantasyland/function-prototype-map#1, although, as you said, it's the same implementation for two different things, so 🤷‍♂️ Maybe

To port my concern over from that issue, both you and @safareli mentioned variadic arguments. In either Functor or Semigroupoid, this is inherently unlawful, but there's little chance of anyone going for it if this isn't the case. In both cases, I'm worried about deliberately pushing for something specifically called "compose" or "map" that's kinda doomed to bastardisation.

That said, it's working for Ramda, so maybe I'm just stubborn 🙃 Either way, both proposals are a move in the right direction. My only concern, as I said, is the misuse of meaningful terms; I'd almost be tempted to push for Function.prototype.pipe in lieu of compose (because it's not a loaded term), and then we can just write a strict compose in terms of pipe.

gabejohnson commented 7 years ago

but there's little chance of anyone going for it if this isn't the case.

This was my point in the "Static method?" section. I think a variadic static method is more likely to get traction. I would argue that the pipe/flowRight variant is also more ergonomic.

I'm worried about deliberately pushing for something specifically called "compose" or "map" that's kinda doomed to bastardisation

Agreed. I think a static method is more appropriate in this case.

gabejohnson commented 7 years ago

See https://gist.github.com/isiahmeadows/7b5b49469c08bd3ddc425d15b0bd65c8 for an operator based approach

gabejohnson commented 7 years ago

Just discovered mentions don't notify from gists so... /cc @isiahmeadows

dead-claudia commented 7 years ago

I'd personally prefer a new language operator over a method (conciseness, zero-cost), but I'd take either provided the engine is smart enough to optimize it. I haven't had the time to really push for significant feedback yet, though.

Probably should move it to a repo soon.

Edit: proposal now lives here.

gabejohnson commented 7 years ago

I'd personally prefer a new language operator over a method (conciseness, zero-cost), but I'd take either provided the engine is smart enough to optimize it.

My bias is in the other direction (method), but I'd be happy with one of them making it into the spec.

An operator only wins on conciseness for short composition chains:

pipe(f, g, h, i);
// vs
f >:> g >:> h >:> i

But if the compiler can't be convinced to optimize the method variant, I'll take an operator.

dead-claudia commented 7 years ago

@gabejohnson Either one could be optimized well. Just the operator version could result in optimized bytecode. And yes, it is slightly more verbose, but the operator choice really could stand to be improved (ideas welcome).

gabejohnson commented 7 years ago

Deleted the last two comments and moved them to https://github.com/isiahmeadows/function-composition-proposal/issues/1

i-am-tom commented 7 years ago

On the "arity of composing functions" section, I'd like to bring up this example:

  //+ map :: Functor f => (a -> b) -> f a -> f b
const map = f => xs => xs.map(f)

  //+ prop :: String -> StrMap a -> a
const prop = k => sm => sm[k]

  //+ compose :: (b -> c) -> (a -> b) -> a -> c
const compose = f => g => x => f(g(x))

  //+ pluck :: String -> [StrMap a] -> [a]
const pluck = compose(map)(prop)

With Haskell-style unary currying, this is exactly as much code as is needed to do this. Any binary operation can be lifted to operate on an array by applying it to compose(map). Of course, the luxury goes away if the first function's arguments must be completely applied before continuing.

Even more magic is lost if any function can have any number of args, as map will end up causing problems. As I see it, there are two big decisions here:

Can the first function be variadic? (Personally, I think allowing this of any and all will cause so many headaches for functional and imperative JSers alike that it should be discouraged).
If so, do we return a function that takes as many args as the first function? Or, do we return a function that keeps applying them until the first value isn't a function.

The first option of the second point seems sensible to me, because then it does give us ways to massage the spec into something useful. Thus, a potential (untested) implementation (thanks, @stoeffel) would probably be something like this:

const functionFatory = require('arity-n')

Function.pipe = function (f, ... fs) {
  if (f == void 0) throw new Error('>:(')

  return functionFactory((... xs) => {
    fs.reduce((x, f) => f(x), f(... xs)
  }, f.length)
}

The beauty of this is that it doesn't actually break any unary function code, but nor does it require that behaviour. So, we (as FP library contributors) are free to place that restriction at a higher level :)

dead-claudia commented 7 years ago

@i-am-tom I invite you to check out my proposal linked earlier in this bug. I've actually thought out several parts of this already.

i-am-tom commented 7 years ago

Apologies; missed the link!

The concept of an operator frightens me because, in all other situations, the compiler can be quite rigorous: does an async function await something or return a Promise, does a const-declared variable ever get touched, etc. However, beyond, "are they all functions", is there really that much that the compiler can contribute here? It's an open question; I'm confident that you've given it far more thought than I have!

Also, as someone who isn't a huge fan of async/await, how would this work with async composition? f :> await g :> await h?

dead-claudia commented 7 years ago

@i-am-tom

However, beyond, "are they all functions", is there really that much that the compiler can contribute here?

It can statically determine and perform after type checking the following with minimal effort:

Each function after the first can only be called with 1 argument.
The function's return value can be fed into the next, so it can avoid args allocation.
No type checking is required at runtime for each function.
It doesn't require a stack frame to create the functions, so it's even cheaper than a lambda to create.

Also, as someone who isn't a huge fan of async/await, how would this work with async composition? f :> await g :> await h?

It'd likely end up just f :> (await g) :> (await h), but I would instead do async composition as something different, so it'd be a little more concise and sensible. Something like async f :> g :> h instead would work more nicely.

i-am-tom commented 7 years ago

Interesting! Is that only-one-argument restriction disereable? Thinking about cases like parseInt where there's more than one possible arg (even though I most likely only care about the first day-to-day).

I like the syntax ideas, too! Have yourself an upvote ready when you are :) ✨

JAForbes commented 7 years ago

Re: https://gitter.im/sanctuary-js/sanctuary?at=596e241b329651f46e9c5830

I think we should try proposing a variadic Function.pipe first. I think we want a lawful API, especially for compose. And I think our chances of achieving that (and other lawful proposals) increases if we can convince the community that explicit behaviour is useful.

I think an on ramp for that conversation sticking is to get some kind of higher order function composition in the language with a simple proposal where we aren't going to be too bothered when they inevitably want it to become convenient.

It's easy to polyfill, implement, it exists in lots of popular libraries just like this proposal, but we won't get into the dreaded ivory tower vs pragmatic debate if we are proposing a function that isn't required to be lawful.

Getting one proposal over the line could be very useful when making future proposals.

dead-claudia commented 7 years ago

I do feel that it might be better to propose both simultaneously with their downsides, to see which TC39 would prefer. They honestly could go either way.

Syntactic composition

Pros:

Easier to apply optimizations (they can be done at bytecode compile time)
Easier to model for implementation

Cons:

Unusual syntax (for some)
Not polyfillable

New `Function.pipe` (or similar)

Pros:

Familiar syntax (Lodash's _.flow, Ramda's R.pipe, etc.)
Polyfillable

Cons:

Harder to apply optimization (new special cases in the JIT)
Requires a native builtin to avoid a pathological slowdown (worse than promises) in the baseline

Tangentially related, but check out this new proposal, and my alternate, coincidentally simultaneous proposal.

fantasyland / ECMAScript-proposals