Your toy example, even generalised, has no practical use. If I can write this:

  compose(f, f1, f2, f3)

  f . f3 . f2 . f1

  f1 |- f2 |- f3 |- f

  let (|-) f g = fun x -> g (f x)
  (|-): (’a -> ’b) -> (’b -> ’c) -> (’a -> ’c)

let f be a overload set matching the signatures {a -> b, i -> j} let g be a overload set matching the signatures {b -> c, j -> k}

compose(g, f) could be given a to return c or i to return k

My point was that we are almost never hurt by that reduction.

> you are specifying that each function cannot have multiple overloads

Haskell has type classes, and if we restrict ourselves to local type inference it's fairly easy to have C++ style overloads without even that. So no, I'm not specifying such a thing.

This is only because people are using statically typed language that place arbitrary restrictions on such functions and make them harder to use. In dynamically typed languages, vararg functions are widely used and enable patterns that are pretty nice.

[1] The need to test much more, the need for a better, more accurate documentation, the higher cost of refactoring, even the higher prototyping times (I prototype faster with a REPL that has static typing, because I don't to debug type errors).

On the other hand, because Common Lisp has resumable exceptions and on-the-fly redefinition of just about everything, I prototype significantly faster in CL because I can just let the debugger stay open until I fix the issue and then hit “continue”.

I no longer believe the “static faster for development than dynamic” thesis because I think a lot depends on how the programmer thinks about programming and which tools are available.

See, if I have an unexpected error, that's because I fucked up my program. And because of that, my runtime state is likely screwed as well. So not only do I have to correct my error, I have to correct its consequences before I restart the program. I can't just resume its execution and hope for the best, I need to know that whatever state I keep is not rotten.

On the other hand, that way of doing things is not exclusive to dynamic languages. There's thing things called "dynamically loaded libraries", that you can use even in C. Game programmers routinely recompile & reload specific dlls just so they can correct their mistakes without restarting the whole game. And those who have written in-game editors have a very powerful stop-debug-restart cycle. On top of a statically typed language.

https://godbolt.org/z/h7n8Y7qf1

Like sure, you can't write out a type for the entire overload set. Overload sets don't have types, but functions do. However, I don't think you'd ever actually want to write out the type of the compose function. Instead, I think it would be more reasonable to request that every intermediate function call is type-checked with fully specified types. In C++ this is the case.

(very minor nitpick: I'd pick `auto&& x` over `auto x`)

True. A more interesting question might be what level of static safety and performance benefits you'd be willing to sacrifice to be able to write functions like this.

Personally, I don't find the kind of code I can't fit into static types particularly appealing, but I find the code navigation, error checking, and optimizations of static types to be priceless.

However, the intersection of programs I encounter in practice with the number of programs that can be statically checked is rather large.

And once there are two types T1 and T2 which are neither subtypes, nor supertypes of each other, and 2 expressions A1 and A2 of types T1 and T2, and a statically undecideable expression p, then statically typing "if p then A else B" is a problem.

And yes, I agree: Most if not all practical type systems will not accept an if-else statement if they cannot unify both branches of the conditional into a single type. Which makes sense. Because you have to act on the result of the expression, and then it needs to have some common type.

But on a purely theoretical basis, it is entirely possible and valid to have an undecideable type system. Which, btw, happens for a lot of languages: https://3fx.ch/typing-is-hard.html . There are C++ programs which are provably impossible to type at compile time.

    sealed class Program
    class HaltingProgram : Program()
    class InfiniteProgram : Program()

    fun checkIsHalting(p: ByteArray) = if (halts(p)) HaltingProgram() else InfiniteProgram()

Here I defined a simple `Pipeline` GADT for the argument list, which is just a list of functions with some extra type constraints to ensure that they can be composed. You could do the same thing with a more general type like HList but the type signature for the `compose` function would be much more verbose since you would need to define the relationships between each pair of adjacent function types through explicit constraints involving type families, whereas the `Pipeline` type handles that internally.

Perhaps you don't consider Haskell "mainstream" enough?

  from typing import Callable, Any

  def compose(start: Callable[[Any], Any], *args: Callable[[Any], Any] -> Callable[[Any], Any]:
    def helper(x: Any) -> Any:
      for func in reversed(args):
        x = func(x)
      return start(x)
    return helper

Found this implementation which also provides pre-expanded forms that are first class functions for specific lengths of arguments docs: https://docs.racket-lang.org/typed-compose/index.html implementation: https://git.marvid.fr/scolobb/typed-compose/src/branch/maste...

Something like:

  fn compose<X, T>(start: Box<Fn(T) -> X>, args: Vec<Box<Fn(T) -> T>>) -> Fn(T) -> X {
    move |x: X| {
      let mut x = x;
      for func in args.iter(). reversed() {
        x = func(x);
      }
      start(x)
    }
  }