3 ms·

I wonder if this formalism can be applied to Typescript. I occasionally come across tricky typing problems with higher order functions like "flatten" that this

I wonder if this formalism can be applied to Typescript. I occasionally come across tricky typing problems with higher order functions like "flatten" that this might be helpful for.

wwwigham 8y ago
This is just a guess, but since TS is structural and it's inference engine is based on pattern matching instead of constraint solving some of this already applies. Minimally, the generalized type traversal constructors described as a use for higher kinds are already possible.[1] Then again, it was _also_ already similarly possible in Haskell, just _incredibly_ verbose, as it is there. The concepts don't quite transfer 1:1, due to implementation and type system differences (for example, TS doesn't have a solver relying on certain identities holding to generate new inferences or equations), but I think the gist of it (adding what amounts to a "is possibly a higher kind" constraint) could be portable and form the basis of a higher-kinded algebra in TS and allow for a wider array of patterns to be expressed more succinctly. Unfortunately I'm not immediately sure how structural subtyping would work out for something with that kind of constraint, which would need to be solved, too. [1] https://github.com/DefinitelyTyped/DefinitelyTyped/blob/master/types/ramda/tools.d.ts https://github.com/DefinitelyTyped/DefinitelyTyped/blob/mast...
fro0116 8y ago
Being somewhat of a functional programming zealot (coming from the Clojure camp, so please excuse me if these are stupid questions, considering my lack of familiarity with typed functional programming in general), this is something that has always bothered me about TypeScript's type system, the poor support for higher order functions. For a prime example of this, take a look at the type definition for the ramda pipe function: https://github.com/DefinitelyTyped/DefinitelyTyped/blob/master/types/ramda/index.d.ts#L1941 https://github.com/DefinitelyTyped/DefinitelyTyped/blob/mast... It's a hard coded list of 10 signature overrides that allows it to support up to 10 piped functions. Obviously the actual ramda pipe function can support an arbitrary number of piped functions at runtime, but the types as written only supports 10. This seems awfully inelegant and inflexible. I assume there is some fundamental deficiency in TypeScript's type system that forces people to specify types this way, otherwise it would have been rewritten by now. Is higher kinded types what's missing to be able to express higher order functions and functional composition in an elegant way? If so, can someone provide an example of what the type signature of a pipe function would look like with higher kinded types? Any ideas if higher kinded types are being considered as additions in future versions of TypeScript, or if that's even feasible at all?
- mjburgess 8y ago
  I don't think HKTs are the solution here. The problem is that functions have curried type signatures (ie., they are typed st. all the arguments "come together", so the arity is part of the type). In Haskell I believe when you write fn :: a -> b a can be inferred to be (Int -> Int -> Int), say. Here when you write pipe<A, B>(A => B): A => B 'A => B' just means a function from one-arg A to one-arg B. The solution is some sort of type-level function, but it also requires new sorts of type variables.
  - ratmice 8y ago
    One can do this sort of thing in Ur i believe, which uses system F-omega with row polymorphic types, http://www.impredicative.com/ur/ http://www.impredicative.com/ur/
- sfvisser 8y ago
  In Haskell you usually solve this by just creating an infix operator and use chaining. No need for complicated constructions to type your varargs. Like composition: `f . g . h $ a`
- bontaq 8y ago
  They actually just merged a very important PR: https://github.com/Microsoft/TypeScript/pull/30215 https://github.com/Microsoft/TypeScript/pull/30215 It adds inference for higher order functions, and, from a bit of playing with the Typescript nightly build, ramda works much better. Once 3.4 comes out it's going to make life a lot easier for ramda/functional/clojure-like programming

I wonder if this formalism can be applied to Typescript. I occasionally come across tricky typing problems with higher order functions like "flatten" that this might be helpful for.

wwwigham 8y ago

This is just a guess, but since TS is structural and it's inference engine is based on pattern matching instead of constraint solving some of this already applies. Minimally, the generalized type traversal constructors described as a use for higher kinds are already possible.[1] Then again, it was _also_ already similarly possible in Haskell, just _incredibly_ verbose, as it is there. The concepts don't quite transfer 1:1, due to implementation and type system differences (for example, TS doesn't have a solver relying on certain identities holding to generate new inferences or equations), but I think the gist of it (adding what amounts to a "is possibly a higher kind" constraint) could be portable and form the basis of a higher-kinded algebra in TS and allow for a wider array of patterns to be expressed more succinctly. Unfortunately I'm not immediately sure how structural subtyping would work out for something with that kind of constraint, which would need to be solved, too. [1] https://github.com/DefinitelyTyped/DefinitelyTyped/blob/master/types/ramda/tools.d.ts https://github.com/DefinitelyTyped/DefinitelyTyped/blob/mast...

fro0116 8y ago

Being somewhat of a functional programming zealot (coming from the Clojure camp, so please excuse me if these are stupid questions, considering my lack of familiarity with typed functional programming in general), this is something that has always bothered me about TypeScript's type system, the poor support for higher order functions. For a prime example of this, take a look at the type definition for the ramda pipe function: https://github.com/DefinitelyTyped/DefinitelyTyped/blob/master/types/ramda/index.d.ts#L1941 https://github.com/DefinitelyTyped/DefinitelyTyped/blob/mast... It's a hard coded list of 10 signature overrides that allows it to support up to 10 piped functions. Obviously the actual ramda pipe function can support an arbitrary number of piped functions at runtime, but the types as written only supports 10. This seems awfully inelegant and inflexible. I assume there is some fundamental deficiency in TypeScript's type system that forces people to specify types this way, otherwise it would have been rewritten by now. Is higher kinded types what's missing to be able to express higher order functions and functional composition in an elegant way? If so, can someone provide an example of what the type signature of a pipe function would look like with higher kinded types? Any ideas if higher kinded types are being considered as additions in future versions of TypeScript, or if that's even feasible at all?

mjburgess 8y ago
I don't think HKTs are the solution here. The problem is that functions have curried type signatures (ie., they are typed st. all the arguments "come together", so the arity is part of the type). In Haskell I believe when you write fn :: a -> b a can be inferred to be (Int -> Int -> Int), say. Here when you write pipe<A, B>(A => B): A => B 'A => B' just means a function from one-arg A to one-arg B. The solution is some sort of type-level function, but it also requires new sorts of type variables.
- ratmice 8y ago
  One can do this sort of thing in Ur i believe, which uses system F-omega with row polymorphic types, http://www.impredicative.com/ur/ http://www.impredicative.com/ur/
sfvisser 8y ago
In Haskell you usually solve this by just creating an infix operator and use chaining. No need for complicated constructions to type your varargs. Like composition: `f . g . h $ a`
bontaq 8y ago
They actually just merged a very important PR: https://github.com/Microsoft/TypeScript/pull/30215 https://github.com/Microsoft/TypeScript/pull/30215 It adds inference for higher order functions, and, from a bit of playing with the Typescript nightly build, ramda works much better. Once 3.4 comes out it's going to make life a lot easier for ramda/functional/clojure-like programming