7 ms·

Higher-kinded types: the difference between giving up and moving forward

139 points by dmit 10y ago

chowes 10y ago
What I wish to see in these blog posts are real-world examples. My day job is coding an MVC app in Rails / Ember. Fine, I won't be able to get past Chapter 11 in a book, but what am I REALLY missing out on? Are these solutions meant for a different problem set, or would I be able to use these concepts in my day-to-day (assuming we were written in a Scala, Haskell, etc.)?
- deleted 10y ago
  [deleted]
- daxfohl 10y ago
  http://stackoverflow.com/questions/21170493/when-are-higher-kinded-types-useful/21174565 http://stackoverflow.com/questions/21170493/when-are-higher-... Also, my practical-oriented blog posts on the topic in .net (referenced in my own answer on that page): http://www.sparxeng.com/blog/software/an-example-of-what-higher-kinded-types-could-make-possible-in-c http://www.sparxeng.com/blog/software/an-example-of-what-hig... http://www.sparxeng.com/blog/software/higher-kinded-fun-in-haskell http://www.sparxeng.com/blog/software/higher-kinded-fun-in-h...
  - chowes 10y ago
    That first blog post of yours was great, FYI - exactly what I was looking for.
    - daxfohl 10y ago
      A simpler example would be say amplifying a signal functor. In Haskell, let amplify x f = fmap (x *) f amplify 2 [1,2,3] >> [2,4,6] cos pi >> 1.0 let doublecos = amplify 2 cos doublecos pi >> 2.0 You can't do anything that operates so generically in a language without HKTs. All that said, I don't find them all that useful in day-to-day work.
- willtim 10y ago
  First of all, a Ruby developer would need to be convinced of the value of static types, in his/her domain. For the maintenence of large complex systems, they are invaluable, for web development perhaps less so. Advanced type systems simply allow one to statically verify more invariants, or in the case of higher-kinded types, allow one to make more sophisticated abstractions and reduce boilerplate. It's important to remember that every statically typed language is capable of being dynamically typed also. I can use string-keyed dictionaries and runtime tagged types in Haskell if I ever need to. What you loose is ease-of-use, which I guess is why Ruby is more popular than Haskell.
  - marcosdumay 10y ago
    > What you loose is ease-of-use After a while using Haskell, I'm not sure about that anymore. I keep thinking that an "easier than rails" web framework is just one breakthrough by some random developer somewhere on the Internet away. Even if I can't imagine the form such library would take, the features I see every day are so powerful that it just look possible.
- harveywi 10y ago
  Are you familiar with C# or Visual Basic? LINQ [1] is a tragic example of what happens when a host language does not support higher-kinded types - every time you use a LINQ method on a concrete type that may have important semantics, its (static) type gets downgraded to a plain "IEnumerable<X>". This can cause major bugs and headaches when trying (intentionally or inadvertently) to write code to abstract over various combinations of LINQ flavors such as "LINQ to Objects" and, say, "LINQ to Entities/SQL". The LINQ abstraction is leaky, half-baked, and not as safe as it should be. Some of the various "LINQ to X" flavors are actually unable to support certain operations (cf. [2]), so your software can unexpectedly fail at runtime. If C# and Visual Basic had support for higher-kinded types, then your LINQ-equipped thing wouldn't have to be punted back to an IEnumerable - it could retain its (static) type after applying LINQ methods. [1] https://msdn.microsoft.com/en-us/library/mt693024.aspx https://msdn.microsoft.com/en-us/library/mt693024.aspx [2] https://msdn.microsoft.com/en-us/library/bb738550(v=vs.110).aspx https://msdn.microsoft.com/en-us/library/bb738550(v=vs.110)....
  - recursive 10y ago
    I assume by concrete type, you mean the actual run-time manifested type of an object. If that's true, you're slightly wrong. Most linq methods have parallel definitions for IQueryable<T>. (For those that don't, IQueryable<T> also extends IEnumerable<T>, so that's always a fallback.) In practice this means that not all linq methods return IEnumerable<T>. x.Where(...) may return a statically typed IEnumerable<T> or an IQueryable<T> depending on whether x was IQueryable<T>. Edit: I don't think linq would even actually improve by having this kind of fancy stuff. I don't want .Where() called on an array to return another array. I want a lazy IEnumerable<T> almost every time. I might want to consume only the first 10 elements from the filtered result. Allocating a whole 100000 array could be a tremendous waste of time.
    - harveywi 10y ago
      Thanks - you are right about the IQueryable/IEnumerable distinction - it's been a long time since I worked with C#. I think it is somewhat unfortunate that IQueryable is a subtype of IEnumerable because the semantics are so different and one can be so easily coerced into the other. For an alternative example of limitations induced by lack of higher-kinded type abstraction, imagine implementing an Option/Maybe type [1] in C# and piggybacking on LINQ. Under the LINQ API, if you try to do anything with an instance of your Option/Maybe, its static type gets obliterated into an IEnumerable, which destroys the semantics. (The fact that the thing is an Option/Maybe and not, say, a list of things, is important for reasoning about, building, and abstracting over things.) [1] https://en.wikipedia.org/wiki/Option_type https://en.wikipedia.org/wiki/Option_type
- dragonwriter 10y ago
  > My day job is coding an MVC app in Rails / Ember. Fine, I won't be able to get past Chapter 11 in a book, but what am I REALLY missing out on? Being focused on Ruby (or any dynamic language) makes the value harder to see, perhaps, since a lot of what HKT get you in a static language you don't need in a dynamic language -- its stuff you lose going from a dynamic language to a static language with an insufficiently powerful type system in exchange for typesafety. HKT let you have your cake and it eat it too (that is, lets you keep powerful abstractions that operate on classes of related types, while remaining typesafe.)
  - chowes 10y ago
    Keeping your comment in mind while reading http://www.sparxeng.com/blog/software/an-example-of-what-higher-kinded-types-could-make-possible-in-c http://www.sparxeng.com/blog/software/an-example-of-what-hig... from below was super helpful. Thank you.
- talex5 10y ago
  Here's a common example. Some systems provide blocking operations: e.g. read_line waits for a line of text and then returns it as a string. Others use promises: read_line returns a promise of a string. What if you want to write a library that works with either blocking calls or asynchronous promises? The cohttp HTTP library is written that way. For example, the Transfer_io module[1] (supporting both chunking and non-chunking HTTP transfers) takes as an argument another module, IO[2], that provides a read_line function of type "ic -> string option t", where the type t is abstract and higher-kinded (and "ic" = input channel). You can instantiate the module with a blocking IO module (where a "string t" is just the same as a "string" and read_line blocks) or with a non-blocking one (where a "string t" is a promise for a "t" and read_line returns a promise). [1] https://github.com/mirage/ocaml-cohttp/blob/master/lib/transfer_io.mli https://github.com/mirage/ocaml-cohttp/blob/master/lib/trans... [2] https://github.com/mirage/ocaml-cohttp/blob/master/lib/s.mli https://github.com/mirage/ocaml-cohttp/blob/master/lib/s.mli (also useful if your language has multiple competing promise libraries...)
  - pierrebai 10y ago
    You don't need higher-kinded types for that. Just always return a promise, except the blocking version always return a promise that is already fulfilled. This is just a variation of 'any problem can be solved by adding a level of indirection' + 'any protocol can have a dummy implementation'.
    - yummyfajitas 10y ago
      The problem is that by doing this, you have made an operation that should be instantaneous - readLineFuture: () => Future[Line] - into something that now has built in lag. I.e. you've pulled the side effects (blocking) from the future to the present.
      - IpV8 10y ago
        That built in lag is so incredibly miniscule in the grand scheme of programming that 99.9999% of times it will not matter, and if it does you are using C or Assembly anyways.
tengbretson 10y ago
I really hope that higher-kinded types can be brought to TypeScript. I really want that kind of power on the front-end, but I can't count on getting an entire team up to speed with PureScript.
- edko 10y ago
  Why not ScalaJS?
- svanderbleek 10y ago
  If TypeScript had these features would it not be as hard to get up to speed with as PureScript? Thus why not just get up to speed with PureScript. I believe in you and your team :)
- gcanti 10y ago
  Not sure about TypeScript but with Flow you can get HKT through some contortions https://github.com/gcanti/flow-static-land https://github.com/gcanti/flow-static-land (in Elm too)
deleted 10y ago
[deleted]
justusw 10y ago
Interesting article and funny to see the shout out to Elm. I think the first few code samples made it very clear that Elm is missing something, at least for this type of generic programming, namely higher order types. Too many times I had to re-implement something that could have been solved in a generic fashion. Kind of similar to how Go programmers have to reimplement instead of generalise. It is actively discussed in the Elm community (https://github.com/elm-lang/elm-compiler/issues/1039 https://github.com/elm-lang/elm-compiler/issues/1039), but with a Wait-And-See-Approach. In my opinion, this is really laudable, as it signals readiness to add higher order types, and at the same time keeps developer friendliness of the resulting feature extension in mind.
rjdevereux 10y ago
I thought this was gong to be an article on hiring kind people and that the title was screwed up.
vorotato 10y ago
I'm really confused is he saying that fsharp can't have functional combinators? That seems incorrect. Also the title is just generally abrasive. I could just as well say scala doesn't natively support dependent types, so clearly it's between F* and giving up.
- premium-concern 10y ago
  > doesn't natively support dependent types Well, it does.
  - vorotato 10y ago
    Scala supports dependent types like how F# supports higher kinded types. Kind of, some of the time, but you might be able to find a library which shims full support.
- wetmore 10y ago
  He's saying there is no abstraction over higher-kinded type constructors, i.e. no abstraction over types which accept their own type arguments.
tveita 10y ago
So tuple() for lists takes two lists and gives all combinations with one item from each list. We could call it product. For options it takes two options and return an option with a tuple of values if both are set, otherwise it return None. We could call it bothOrNone. For Either... It's not unambiguous, but presumably it's similar to option, returning either a tuple of Rights, or the first Left of the arguments, following convention of using Left for errors. We could call it bothRightsOrALeft. For State I'm just guessing. getBothWithStateOfLast? These may all have interesting mathematical similarities, but the way you would use them in a program would be pretty different. I don't think you are making your program clearer by giving them all the same name. Sometimes reading "overabstracted" code can feel similar to reading assembly code. Sure, add and mov are simple operations with a clear definition of input and output, just like flatMap and fold, but they say very little about the programmer's intent in using them. If you give me a chain of them without any comment, I'll need to work backwards to figure out what you're actually trying to accomplish.
- svanderbleek 10y ago
  But if you look at Haskell's Control.Monad you see why the abstraction is helpful [0]. We get things like foldM, it's similar to how you can fold across more than just lists, you can fold across trees and so on, but for all these different structures like State, Either, etc. And yes you are right to point out that some of them have multiple implementations, State can be combined "backwards" or "forwards" (or both). The trade off is you have to invest the time so these abstractions become natural, but once you do so you can use generic control structures that save tons of implementation time. [0] https://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Monad.html https://hackage.haskell.org/package/base-4.9.0.0/docs/Contro...
  - skybrian 10y ago
    I guess, but I don't think I need that library? Or at least, not badly enough to complicate the type system. It adds complexity, so I'm not convinced I'd save any time.
    - 10y ago
premium-concern 10y ago
Jesus Christ, don't be so salty.
- dang 10y ago
  Please post civilly and substantively, regardless of how wrong or annoying someone else's comment is. We detached this comment from https://news.ycombinator.com/item?id=12340160 https://news.ycombinator.com/item?id=12340160 and marked it off-topic.

139 points by dmit 10y ago

What I wish to see in these blog posts are real-world examples. My day job is coding an MVC app in Rails / Ember. Fine, I won't be able to get past Chapter 11 in a book, but what am I REALLY missing out on? Are these solutions meant for a different problem set, or would I be able to use these concepts in my day-to-day (assuming we were written in a Scala, Haskell, etc.)?

deleted 10y ago
[deleted]
daxfohl 10y ago
http://stackoverflow.com/questions/21170493/when-are-higher-kinded-types-useful/21174565 http://stackoverflow.com/questions/21170493/when-are-higher-... Also, my practical-oriented blog posts on the topic in .net (referenced in my own answer on that page): http://www.sparxeng.com/blog/software/an-example-of-what-higher-kinded-types-could-make-possible-in-c http://www.sparxeng.com/blog/software/an-example-of-what-hig... http://www.sparxeng.com/blog/software/higher-kinded-fun-in-haskell http://www.sparxeng.com/blog/software/higher-kinded-fun-in-h...
- chowes 10y ago
  That first blog post of yours was great, FYI - exactly what I was looking for.
  - daxfohl 10y ago
    A simpler example would be say amplifying a signal functor. In Haskell, let amplify x f = fmap (x *) f amplify 2 [1,2,3] >> [2,4,6] cos pi >> 1.0 let doublecos = amplify 2 cos doublecos pi >> 2.0 You can't do anything that operates so generically in a language without HKTs. All that said, I don't find them all that useful in day-to-day work.
willtim 10y ago
First of all, a Ruby developer would need to be convinced of the value of static types, in his/her domain. For the maintenence of large complex systems, they are invaluable, for web development perhaps less so. Advanced type systems simply allow one to statically verify more invariants, or in the case of higher-kinded types, allow one to make more sophisticated abstractions and reduce boilerplate. It's important to remember that every statically typed language is capable of being dynamically typed also. I can use string-keyed dictionaries and runtime tagged types in Haskell if I ever need to. What you loose is ease-of-use, which I guess is why Ruby is more popular than Haskell.
- marcosdumay 10y ago
  > What you loose is ease-of-use After a while using Haskell, I'm not sure about that anymore. I keep thinking that an "easier than rails" web framework is just one breakthrough by some random developer somewhere on the Internet away. Even if I can't imagine the form such library would take, the features I see every day are so powerful that it just look possible.
harveywi 10y ago
Are you familiar with C# or Visual Basic? LINQ [1] is a tragic example of what happens when a host language does not support higher-kinded types - every time you use a LINQ method on a concrete type that may have important semantics, its (static) type gets downgraded to a plain "IEnumerable<X>". This can cause major bugs and headaches when trying (intentionally or inadvertently) to write code to abstract over various combinations of LINQ flavors such as "LINQ to Objects" and, say, "LINQ to Entities/SQL". The LINQ abstraction is leaky, half-baked, and not as safe as it should be. Some of the various "LINQ to X" flavors are actually unable to support certain operations (cf. [2]), so your software can unexpectedly fail at runtime. If C# and Visual Basic had support for higher-kinded types, then your LINQ-equipped thing wouldn't have to be punted back to an IEnumerable - it could retain its (static) type after applying LINQ methods. [1] https://msdn.microsoft.com/en-us/library/mt693024.aspx https://msdn.microsoft.com/en-us/library/mt693024.aspx [2] https://msdn.microsoft.com/en-us/library/bb738550(v=vs.110).aspx https://msdn.microsoft.com/en-us/library/bb738550(v=vs.110)....
- recursive 10y ago
  I assume by concrete type, you mean the actual run-time manifested type of an object. If that's true, you're slightly wrong. Most linq methods have parallel definitions for IQueryable<T>. (For those that don't, IQueryable<T> also extends IEnumerable<T>, so that's always a fallback.) In practice this means that not all linq methods return IEnumerable<T>. x.Where(...) may return a statically typed IEnumerable<T> or an IQueryable<T> depending on whether x was IQueryable<T>. Edit: I don't think linq would even actually improve by having this kind of fancy stuff. I don't want .Where() called on an array to return another array. I want a lazy IEnumerable<T> almost every time. I might want to consume only the first 10 elements from the filtered result. Allocating a whole 100000 array could be a tremendous waste of time.
  - harveywi 10y ago
    Thanks - you are right about the IQueryable/IEnumerable distinction - it's been a long time since I worked with C#. I think it is somewhat unfortunate that IQueryable is a subtype of IEnumerable because the semantics are so different and one can be so easily coerced into the other. For an alternative example of limitations induced by lack of higher-kinded type abstraction, imagine implementing an Option/Maybe type [1] in C# and piggybacking on LINQ. Under the LINQ API, if you try to do anything with an instance of your Option/Maybe, its static type gets obliterated into an IEnumerable, which destroys the semantics. (The fact that the thing is an Option/Maybe and not, say, a list of things, is important for reasoning about, building, and abstracting over things.) [1] https://en.wikipedia.org/wiki/Option_type https://en.wikipedia.org/wiki/Option_type
dragonwriter 10y ago
> My day job is coding an MVC app in Rails / Ember. Fine, I won't be able to get past Chapter 11 in a book, but what am I REALLY missing out on? Being focused on Ruby (or any dynamic language) makes the value harder to see, perhaps, since a lot of what HKT get you in a static language you don't need in a dynamic language -- its stuff you lose going from a dynamic language to a static language with an insufficiently powerful type system in exchange for typesafety. HKT let you have your cake and it eat it too (that is, lets you keep powerful abstractions that operate on classes of related types, while remaining typesafe.)
- chowes 10y ago
  Keeping your comment in mind while reading http://www.sparxeng.com/blog/software/an-example-of-what-higher-kinded-types-could-make-possible-in-c http://www.sparxeng.com/blog/software/an-example-of-what-hig... from below was super helpful. Thank you.
talex5 10y ago
Here's a common example. Some systems provide blocking operations: e.g. read_line waits for a line of text and then returns it as a string. Others use promises: read_line returns a promise of a string. What if you want to write a library that works with either blocking calls or asynchronous promises? The cohttp HTTP library is written that way. For example, the Transfer_io module[1] (supporting both chunking and non-chunking HTTP transfers) takes as an argument another module, IO[2], that provides a read_line function of type "ic -> string option t", where the type t is abstract and higher-kinded (and "ic" = input channel). You can instantiate the module with a blocking IO module (where a "string t" is just the same as a "string" and read_line blocks) or with a non-blocking one (where a "string t" is a promise for a "t" and read_line returns a promise). [1] https://github.com/mirage/ocaml-cohttp/blob/master/lib/transfer_io.mli https://github.com/mirage/ocaml-cohttp/blob/master/lib/trans... [2] https://github.com/mirage/ocaml-cohttp/blob/master/lib/s.mli https://github.com/mirage/ocaml-cohttp/blob/master/lib/s.mli (also useful if your language has multiple competing promise libraries...)
- pierrebai 10y ago
  You don't need higher-kinded types for that. Just always return a promise, except the blocking version always return a promise that is already fulfilled. This is just a variation of 'any problem can be solved by adding a level of indirection' + 'any protocol can have a dummy implementation'.
  - yummyfajitas 10y ago
    The problem is that by doing this, you have made an operation that should be instantaneous - readLineFuture: () => Future[Line] - into something that now has built in lag. I.e. you've pulled the side effects (blocking) from the future to the present.
    - IpV8 10y ago
      That built in lag is so incredibly miniscule in the grand scheme of programming that 99.9999% of times it will not matter, and if it does you are using C or Assembly anyways.

tengbretson 10y ago

I really hope that higher-kinded types can be brought to TypeScript. I really want that kind of power on the front-end, but I can't count on getting an entire team up to speed with PureScript.

edko 10y ago
Why not ScalaJS?
svanderbleek 10y ago
If TypeScript had these features would it not be as hard to get up to speed with as PureScript? Thus why not just get up to speed with PureScript. I believe in you and your team :)
gcanti 10y ago
Not sure about TypeScript but with Flow you can get HKT through some contortions https://github.com/gcanti/flow-static-land https://github.com/gcanti/flow-static-land (in Elm too)

deleted 10y ago

[deleted]

justusw 10y ago

Interesting article and funny to see the shout out to Elm. I think the first few code samples made it very clear that Elm is missing something, at least for this type of generic programming, namely higher order types. Too many times I had to re-implement something that could have been solved in a generic fashion. Kind of similar to how Go programmers have to reimplement instead of generalise. It is actively discussed in the Elm community (https://github.com/elm-lang/elm-compiler/issues/1039 https://github.com/elm-lang/elm-compiler/issues/1039), but with a Wait-And-See-Approach. In my opinion, this is really laudable, as it signals readiness to add higher order types, and at the same time keeps developer friendliness of the resulting feature extension in mind.

rjdevereux 10y ago

I thought this was gong to be an article on hiring kind people and that the title was screwed up.

vorotato 10y ago

I'm really confused is he saying that fsharp can't have functional combinators? That seems incorrect. Also the title is just generally abrasive. I could just as well say scala doesn't natively support dependent types, so clearly it's between F* and giving up.

premium-concern 10y ago
> doesn't natively support dependent types Well, it does.
- vorotato 10y ago
  Scala supports dependent types like how F# supports higher kinded types. Kind of, some of the time, but you might be able to find a library which shims full support.
wetmore 10y ago
He's saying there is no abstraction over higher-kinded type constructors, i.e. no abstraction over types which accept their own type arguments.

tveita 10y ago

So tuple() for lists takes two lists and gives all combinations with one item from each list. We could call it product. For options it takes two options and return an option with a tuple of values if both are set, otherwise it return None. We could call it bothOrNone. For Either... It's not unambiguous, but presumably it's similar to option, returning either a tuple of Rights, or the first Left of the arguments, following convention of using Left for errors. We could call it bothRightsOrALeft. For State I'm just guessing. getBothWithStateOfLast? These may all have interesting mathematical similarities, but the way you would use them in a program would be pretty different. I don't think you are making your program clearer by giving them all the same name. Sometimes reading "overabstracted" code can feel similar to reading assembly code. Sure, add and mov are simple operations with a clear definition of input and output, just like flatMap and fold, but they say very little about the programmer's intent in using them. If you give me a chain of them without any comment, I'll need to work backwards to figure out what you're actually trying to accomplish.

svanderbleek 10y ago
But if you look at Haskell's Control.Monad you see why the abstraction is helpful [0]. We get things like foldM, it's similar to how you can fold across more than just lists, you can fold across trees and so on, but for all these different structures like State, Either, etc. And yes you are right to point out that some of them have multiple implementations, State can be combined "backwards" or "forwards" (or both). The trade off is you have to invest the time so these abstractions become natural, but once you do so you can use generic control structures that save tons of implementation time. [0] https://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Monad.html https://hackage.haskell.org/package/base-4.9.0.0/docs/Contro...
- skybrian 10y ago
  I guess, but I don't think I need that library? Or at least, not badly enough to complicate the type system. It adds complexity, so I'm not convinced I'd save any time.
  - 10y ago

premium-concern 10y ago

Jesus Christ, don't be so salty.

dang 10y ago
Please post civilly and substantively, regardless of how wrong or annoying someone else's comment is. We detached this comment from https://news.ycombinator.com/item?id=12340160 https://news.ycombinator.com/item?id=12340160 and marked it off-topic.