Higher Kinded Types (Monads, Functors, etc.)

That's quite an over simplification for a 2 year thread.
As I've said before I can appreciate there are many more higher priority features still missing in Swift plus the long overdue fixes for all the stuff that's just not working. So with that in mind; I can't see HKT's getting much priority in the short to medium term and that's ok -- but let's not forget that no language is ever cast in concrete; Swift will have to evolve to stay relevant and HKTs is IMO an inevitable conclusion -- hence keeping it on the radar is not lost cause.

HKTs are abstractions over type constructors, that is in Swift, generic types. A programmer that's not a heavy generics user has absolutely nothing to say about HKTs.

I don't use abstract classes and inheritance: this means that I wouldn't enter into a discussion about improving Swift in that area, save for cases where eventual changes would damage my approach, like features that required breaking changes in areas that I care about.

The Swift community, or general populace, is not a uniform mass, and we should stop talking about potential features as useful to the majority: the usefulness of a language feature is a a priori, theoretical matter (supported with, or even bootstrapped by, applications of course), that has nothing to do with the way some people use the language on average right now.

On a side note, compile time parametric polymorphism based on generics is strictly better in terms of safety and correctness than runtime dynamicism, and the fact that Swift has a powerful generics system makes it better than many other languages in the same terms: this means that if you don't take advantage of this parametricity, you're going to write, on average, worse code. Thankfully the people who designed Swift in the first place know this very well, and decided that it was the way to go for the language. There's a similar argument for algebraic data types.

On the other hand, Swift is less opinionated than many other languages on some core matters (some see this as a point of weakness, I don't), which means that one can write Swift code the way they like; and which also means that inevitably some discussions will be about things one has no idea about: this is fine, and actually expected.

So let's please stop with this pointless backwards arguments and go back to the point, that is, keep working on some examples - in this thread only I can see already more than enough to justify the addition of this feature to the language -, keep explaining the theory (which is the most important thing to do when discussing a new potential language feature) and maybe start sketching some ideas on how make HKTs ergonomic and discoverable in Swift.

10 Likes

The relevance of my analogy to Higher Order Functions is perhaps made more clear by the following quote from a somewhat related article about HKTs:

map functions are obvious candidates for essential parts of a usable library for functional programming. This is the first-order abstraction—it eliminates the concrete loops, recursive functions, or State lambda specifications, you would need to write otherwise.

When we note a commonality in patterns and define an abstraction over that commonality, we move “one order up”. When we stopped simply defining functions, and started taking functions as arguments, we moved from the first order to the second order.

It is not enough for a modern general-purpose functional library in Scala to simply have a bunch of map functions. It must also provide the second-order feature: the ability to abstract over map functions, as well as many, many other functions numerous type constructors have in common. Let’s not give up; let’s move forward.

1 Like

At the same time, Scala is sometimes criticized as being too complex. Citing the definition of map from this one example:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

…I can see how this may be a problem.

1 Like

Sure, that's what I wish people more knowledgable than me would be discussing in this thread, ie examples of how HKTs should/could be best designed for Swift.

5 Likes

Any code (out of context) could easily be categorised as too complex.

As for map and Scala -- would your complexity comment still apply to this?

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

// Example implementation for Option
implicit val functorForOption: Functor[Option] = new Functor[Option] {
  def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
    case None    => None
    case Some(a) => Some(f(a))
  }
}

From something I observed: Is there a hate for speaking names in the fp community? What's with all this 1 letter names over all examples?

3 Likes

What would a name help with? They're placeholders

Names explain the function of the placeholder. 1 letter names are normally considered very, very bad coding style because their function is very hard to understand.

1 Like

Exactly... the examples I assume he is criticising are of course generic over any two types. So something as verbose as this:

def map[InputType, TransformedType](inputFunctor: F[InputType])(transform: InputType => TransformedType): F[TransformedType]

...would just be IMO verbosity for no good reason.

You mean like the A, B and F? Being generic type parameters, they have no intrinsic meaning, they could be called X, Y, Z, or X1, X2, X3. A more textual option could be InputTypeParameter, OutputTypeParameter, FunctorType but it would be pointlessly verbose because the meaning is clearly inferred from the context, and if you don't understand A, B and F you probably wouldn't understand InputTypeParameter, OutputTypeParameter, FunctorType either. Meaning comes from structure, and the latter could be hidden away by verbosity

About your remark on the "bad coding style" (and your question related to single letters), you're projecting a "best practice" used within a paradigm where meaning is literally only conveyed by names of variables, methods and classes, to a set of abstractions where meaning is deduced by structure and you take advantage of a bunch of well-established conventional names (like functor and map) with clear semantics.

4 Likes

No definitely no. We left this structure madness behind us with assembler and Cobol. verbose names are always helping and of course something like InputType, OutputType and Functor would be much easier to read and understand then A,B and F. That someone in this year really believes that the later is better shocks me deeply.

3 Likes

I whole-heartedly agree with @anon27714269. InputType, OutputType, and Functor are infinitely more clear than A, B, and F.

The original code snippet was completely over my head and I had no idea what anything was, now I at least have an idea about what is going on.

Descriptive type names > single character type names.

4 Likes

I prefer @Jens' position.

I can't wait for this thread to jump over the trolls. Instead, I wish I could read daring proposals that go beyond discussions about the benefits of functor/monad/monoid/etc and actually jump into Swift and spawns pitches.

For example, Chris Lattner and friends have been quite daring with their take on, for example, optionals and error handling. Those are two topics with strong FP foundations that have been digested with both brio... and caveats. You can feel those caveats when you read threads about the Result type, or the inconsistencies in how try? interacts with optional chaining (two recent topics on this forum). You can feel the brio as well, even if I can't really put my finger on it. Optionals and error handling are incomplete, but will follow you quite far despite that. This is brilliant engineering.

If I follow this trend of thought, is it true that HKT have to be considered as a whole? Could there be any benefit in splitting the subject into several sub-subjects that could be addressed independently? This won't give something as perfect as sheer HKT at once, but this may pave the way to immensely interesting language features.

7 Likes

jan has a point. the reality is that generics are not as important as everyone acts like they are. I can mostly think of three kinds of cases where i use this feature

  • I need to abstract over many built-in types for some usage with UnsafeRawPointer. the main purpose of the type parameter is so I can access MemoryLayout<T>. example:
func upload<T>(data:[T]) 
  • I already know what concrete type I want to use but am writing the function generically because Swift’s protocol hierarchy makes it easy. example:
func crossProduct<F>(_ a:(F, F, F), _ b:(F, F, F)) -> (F, F, F) where F:FloatingPoint
  • I’m writing a library that accepts any user-defined type that conforms to some protocol i specified. example:
public 
func mix<C>(_ a:C, _ b:C, factor:C.Element) where C:ColorFormat

However, with the current state of the language, the third one is useless for anything but experimentation and tinkering until the cross-module inlining and specialization system is finished. The second one doesn’t really add much, it’s just a nice to have in the language.

Are generics important? yes! But is the usage of generics proportional to the amount of bandwidth they take up on this forum? i don’t know. I feel like people on here like to talk about generics and the type system on here because it exercises the brain and it’s a nice clean “mathy” topic but really i think this feature follows the 80-20 rule: we spent 20% of the design effort to get 80% of the utility, and now we’re spending 80% of the effort to get that remaining 20% of utility. Similarly, there are less daunting features like cross-module specialization that don’t involve extending the type system, but still yield substantial benefits for generics, as well as the rest of the language. we shouldn’t overlook these.

5 Likes

I think people who ask for and discuss HKTs in Swift do this simply because they find themselves hitting this limitation of Swift's type system (in actual real world code, not just in "mathy" brain exercises).

I don't think they do it for fun or in order to look smart.

Writing reusable data structures and algorithms is part of any (reasonably sized) software project, not just the standard library or other libraries.

Or compile everything from source until it's fixed.


Again, I would rather see some discussion and suggestions about how HKTs could/should be designed for Swift, than endless debates about eg how important or unimportant generics are.

5 Likes

If only... problem is that any potential for that is constantly being undermined by those that see no place for generics in their code -- which is ok; because exploring this topic or topics like these in no way undermines their ability to avoid generics entirely or even to add copious amounts of verbose type signatures to their code, and the like.

Have to wonder if people are really so insecure that this disapproval needs to constantly be regurgitated?

2 Likes

Based on what I have seen from information between people bike-shedding the philosophy of HKTs, I believe the next 96% (80% + (80% of 20%)) of the way to HKTs is to implement generic associatedtypes and generalized existentials. The first of which is also proposed for rust, and I believe would have already been implemented if generic typealiases were added before the typealias-associatedtype split.

13 Likes

I am just shutting down this thread for a while. The number of complaints I get from here is just totally out of whack. Some people seem to feel that their point about not understanding the purpose of HKTs will somehow get missed if they don't repeat it every few days for months on end, and other people seem to feel that any request for justification is a personal affront to their dignity. We can talk about this later; it's not happening in Swift 5 anyway.

I apologize to those of you who are earnestly trying to have a respectful conversation; there have been some very good posts in here as well, and I particularly like Dante's just now.

14 Likes