Higher Kinded Types (Monads, Functors, etc.)

Agreed ibut the reasons why something like HKTs or other parts of the generics manifesto is being pushed back is also important; re I think many have assumed that its just a matter of time and priority as to when everything in the manifesto will be permissible in some form in Swift.

If that's a wrong assumption and the low prioritisation implies as much, then that should also be clear as well.

As for HKTs I think it's an unfair assumption that everyone pushing for this does not either or in some way appreciate the edge cases or what exactly would be permissible by such a feature.

That's right: HKTs are needed where you need to express the changing of generic parameters in the same base structure: filter doesn't change generic parameters.

A possibility would be to specify explicitly which generic parameter is involved in the kind. For example, if I say that the kind of a type is A<B>, and want to make, say, Array<Element> and Dictionary<Key,Value> conform to that kind, we could write something like:

  • for Array<Element>, kind A<B> where A == Array<_>, B == Element;
  • for Dictionary<Key,Value>, kind A<B> where A == Dictionary<_,_>, B == Value;

Another option would be to simply follow the order of generic parameters, but in the Dictionary case the parameters are in the wrong order, so it wouldn't work.

For a kind like A<B,C>, like in Product<First,Second>, the conformance would be expressed in the same way.

While not having currying at the type level makes everything a little harder, I don't think it's impossible to cook up a format that's understandable: actually, even more understandable than the curried one.

Both the "maps" that you mentioned are not structure-preserving maps, which means that if we used the HTKs notation to create, say, a Functor protocol, we should document that protocol with the semantics (and laws) that must be preserved when conforming to it. This is already done in the standard library for a number of protocols.

Thus, I'd say that a map method on Set should probably return a neutral collection. Also, it should not be called map, in the same way as flatMap to mean "compact" on a collection should never have been called flatMap in the first place, and we're all more happy now that it was renamed into compactMap.

Of course an abstraction path could be wrong and eventually reverted: this could always happen, for a number of reason. In many other cases, abstractions prove to be successful, and they inspire new way to think about some computation problems. Your statement doesn't really add a lot to the conversation: we all make mistakes, but if we don't even have the tools to make those mistakes, we cannot really learn our lessons, and improve and move forward.

Of course you don't. But it turns out that being able to abstract over monads is pretty useful: monad transformers are actually a useful tool, and to use them for some combinations I had to generate thousands of lines of code. But if you're looking for something more frequently useful, simply consider abstracting over functors: there are countless applications to this kind of abstraction, and simply dismissing a small subset of cases as something that could have been done manually doesn't really make a compelling argument for dismissiing the whole possibility to have this kind of abstraction power.

I agree on both paragraphs, and I think there have been already a lot of great posts in this thread that would probably deserve a spot in an aggregate repository or relevant contributions to these complex matters.

6 Likes

I think there's just some disjunction between things that are perceived as cool, and things that are actually useful (possibly add "for the majority of users" here)...
Cool but useless features (not saying whether I consider some specific concept as useless here ;-) can help drawing attention to Swift, but "uncool" improvements like speeding up the compiler or better error messages probably make the existing community happier.

At the same time, we as developers are often easily distracted by complicated things... I bet that each year, we burn thousands of hours for fiddling with regular expressions instead of writing five lines of simple code that achieves the same result (but in a boring way).

Deciding to discard a feature is tougher than to include it - but restriction is often a vital aspect:
FP, for example, imho isn't that much defined by the features it offers, but rather by the things that you can't do with it.

That being said, I think it's best to focus on polishing rough edges and filling existing holes in the language now, instead of adding huge features like HKT or a Rust-like memory model... but imho it's not to early to decide wether Swift should include some big features in the future, just to give people a better idea where we are heading (of course, such decisions could be revised... so maybe some sort of priority list would be better ;-)

2 Likes

This is hardly a matter of cool versus not cool, plus let's not assume those pushing for these features are disinterested in the "uncool" stuff.

Many new language features in Swift could easily be painted over with this broad brush stroke; but that's hardly definitive conclusion.

Whoever said a codebase need to be a "100% pure" anything to be considered beneficial. Surely Swift is loved not only for its ability to excel at "old school" paradigms, but also its ability to bridge paradigms.

No arguments here; IMO Swift (and Xcode) could do with a release (post ABI) just focused on buttoning up e.g. performance, error messages, code completion, type inference, ...

While I agree on the fact that many things have greater priority over the addition of HKTs to Swift (to me, for example, completing the generics manifesto as soon as possible is of utmost importance), please try to assume that many of us have enough background, and have put enough thought on the matter, to have carefully considered both where to put the balance between "cool" and "uncool" features, and what features could actually add value to the language instead of being pointlessly complicated and redundant.

I think we should really consider and elaborate on the single, specific arguments in favor of a position or another, instead of overusing generalizations and generic statements about our perceived state of the world of software development. For example, while there's certainly a distinction between "cool" and "useful", there's no way to assign any of those labels to any possibile feature in an objective way, so that distinction is not a useful argument.

2 Likes

Not many things are binary.

I certainly never easily transitioned through many of the historical language advancements; e.g. I was quite content with spaghetti code, but I did transition to procedural, similarly OOP and in the last decade to FP.

...but I agree it's overly difficult to find a single FP source that is truly beginner centric; most just skirt around abstract topics with very esoteric examples that mere mortals can't fathom why these would be advantageous in a codebase, and probably more pertinent where and how to use this. This is sadly a failing of the FP community overall... but even an old programmer like me has to finally acknowledge that learning FP has become advantageous... but we probably should pick this type of discussion up in this thread: Functional programming in Swift - #13 by endofunk

2 Likes

From my humble understanding, programming language is a way to express our reasoning process (computation) step by step into source code and then be compiled and be executed. That means the expressive power of a language shapes how we express our reasoning in coding.

Quoting some statements from @ExFalsoQuodlibet that I agreed on.

Those two ways show where the expressive power comes from.
Even though we can express the same algorithm with/without sophisticated type system, provided the language is Turing complete, but with sophisticated type system, we can express it easily and neatly (personal opinion).

For example of fibonacci sequence in Haskell, it is pretty concise and clean.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
We know that fibonacci sequence is 0, 1, 1, 2 ... ( f(n) = f(n-2) + f(n-1) ), then we can see a fibonacci sequence as a element-wise added up sequence of one fibonacci sequence and one element left shifted fibonacci sequence started from the 3rd element.
_, _, _, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
+, _, _, 1, 1, 2, 3, 5, 8, 13, 21, ...
_, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

A new type feature added to a type system may open a new territory for expressing our program intent while keeping the language small compared with adding syntax sugar.
Therefore I think HKTs or more type feature (Generics Manifesto) would get more priority on the list.

If you could write a functor protocol

protocol Functor<T> {

	func map<U>(_ transform: (T) -> U) -> Self<U>

}

you would be able to write replacing(_:)

extension Functor {

	func replacing<U>(_ u: U) -> Self<U> {
		return map { u }
	}

}

Kinda cool, something similar was just added to Rust**, would be handy on Result*** and Either, but maybe not the strongest motivation for HKTs.
** See RFC: Add `Option::replace` to the core library by Kerollmops · Pull Request #2296 · rust-lang/rfcs · GitHub . A couple of qualifications apply: (1) The value has to be of the same type. In this setup it'd be mutating func replace(by t: T). (2) It was only added on Optional.
*** Often enough code like this crops up: result.map{ _ in () } which replaces a Result's value with ().

While useful, it's the kind of thing that it'd be feasible with a bit of elbow grease to add to your (and the standard library's) functorial types by hand.

Language-level HKT support really shines on methods which are generic over HKTs. For example, the traverse method is defined on Traversable and takes a function involving Applicative:

protocol Traversable<T> {

	func traverse<U, A : Applicative>(_ action: (T) -> A<U>) -> A<Self<U>>

}

( Data.Traversable )

This is a function that folks have been adding themselves in real-world situations: Should the function be called `map` or `flatMap`? . In that thread, a completely concrete version of this method is written:

extension Notification /*generic over T*/ {

	// Optional is substituted for A : Applicative.
	func traverse<U>(_ action: (T) -> Optional<U>) -> Optional<Notification<U>> {...}

}

That's great--folks were able to write a version of this helpful method without using HKTs.

What happens, though, when we want to create an Array of Notifications or a Result of a Notification?

Using the same technique, we'd have to add a couple of overloads:

extension Notification /*generic over T*/ {

	// Array is substituted for A : Applicative.
	func traverse<U>(_ action: (T) -> Array<U>) -> Array<Notification<U>> {...}


	// Result is substituted for A : Applicative.
	func traverse<U>(_ action: (T) -> Result<U>) -> Result<Notification<U>> {...}

}

That is doable too.

The trouble is that we would now have written three overloads which are conceptually identical because the language doesn't support HKTs. Any time you want to allow one of your types to be the kind of thing that can be traversed, you'll add** these three methods to it. And if you add a new type which is applicative to use in these traverse functions, you'll add** a new overload of traverse to each of the types that already have the three overloads.
** Of course, you could incrementally add those overloads as you come across pairs of Traversable and Applicative on which you want to use traverse. YAGNI may apply here, but deferring adding the method until it is needed seriously hinders discoverability--you have to know that both types in question are the kinds of things which can be used with traverse(_:)--and also hinders adoption--you have to go write another version of traverse(_:) in addition to writing what you were working on.

7 Likes

Yeah, the replacing example is a great example of the sort of abstraction that I had in mind when I said that often people think “well, I could write this if only I had HKTs!”, and then when they actually can write it they realize it’s not a very good idea. I don’t think you’d actually want that operation to be defined on all Functors; it’s really only appropriate for Functors that carry at most one value of the parameter type, as a generalization over result-ish types.

The traverse example is more compelling.

4 Likes

Don't intended as bugging but what are these 2 funcs supposed to do? I see the definition but I fail to see what they are supposed to accomplish.

I think a first step of helping other accept and perhaps join the fp group would be explaining in real world examples advantages and not some cryptic code that no one understands...

traverse came up in the context of a question stemming from real world code recently. You might find the discussion very interesting and informative. Should the function be called `map` or `flatMap`? - #6 by mbrandonw

2 Likes

One of the major difficulties in learning about functional programming is that the terminology is…almost entirely terrible.

That “Monad” concept you always hear about? Call it “Chainable” instead.

“Functor”? More like “Mappable”.

“join”, “bind”, and “traverse”? They…don’t do anything at all related to the meanings of those words.

It’s like someone chose deliberately obfuscatory names for everything involved.

7 Likes

Traverse as the name implies is a higher order function (like map) that performs a traversal between 1 container type and another', for example:

// The Either type typical captures positive outcomes as a .right and failures as a .left
// Either<String, Int> implies the .left is String and the .right is Int 

func even(_ value: Int) -> Either<String, Int> {
  return value % 2 == 0 ? .right(value) : left("Failed: Not All Even")c
}

let input = [2, 4, 6, 8] // Array of Ints
let result = input.traverse(even) 
// the result would be of type Either<String, [Int]>.right([2, 4, 6, 8]) 
// We've traversed from an Array of Ints to a Either where the .right is an Int Array
// Whereas an odd number in the input array would have returned a Either<String, Int>.left("Failed: Not All Even") and the traversal would typically .have stopped further computation of the input array.

Haskell Reference:

traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
Map each element of a structure to an action, evaluate these actions from left to right, and collect the results.

I think the problem comes from the naming beeng terrible. You can traverse a tree, a list, a forest - What you describe sounds more like some kind of conversion.

2 Likes

Uh huh..

"There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors."

3 Likes

Well it appears that fp is very "good" at the naming part. Nearly every time I finally understand a fragment the problem was grounded in confusing naming.

Example: Lambda was always very confusing, obj-c blocks instantly hit understanding as it's a clear concept for most coders: a piece of code that can be stored. Yeah it may be mathematical incorrect but it's way better naming.

4 Likes

Certainly not a problem unique to FP; granted the math speak is where FP is truly arcane.... those mathematicians truly shift up a gear when it comes to picking names.

2 Likes

I and @mbrandonw literally explained some use cases for traverse a few posts ago in this very thread, here and here.

Names are just conventions, they are never the point. Also, names usually come from history: a mathematical "monad" came before its software counterpart, and the latter appeared because someone (Prof. Eugenio Moggi) took the concept from the abstract algebraic domain and transferred it to computation, and luckily he wasn't so arrogant to invent new arbitrary names without solid roots in theory.

There are reasons why something is named in a certain way, and has been for a long time, and one could simply learn what they don't know, or complain that for them that particular name means nothing: of course in learning a new domain one should familiarize themselves with the vocabulary, that happens all the time in all the fields, including OOP and design patterns.

That being said, I could pick arbitrary names out of a hat just to draw analogies with other, more familiar concepts, maybe as a teaching tool, but eventually the shared vocabulary stands, and doesn't stand as something rigid and unmovable: it can adapt to times (for example, the notion of a pure function felt to the community eventually more clear than haskell's return).

3 Likes

Can’t share that line of thinking - we are not the general fp community. Our targets should be making Swift as easy and powerful to use for Swift coders, not adhere to some high concept that provided only a hard time for decades to most coders.

Ease of use and understanding should trump principles and “has been done so forever”.

3 Likes