Higher Kinded Types (Monads, Functors, etc.)

Well different background. For me his little code fragment and your explanation look like Hieroglyphics. Not something clicking in place with my brain.

Okay, imagine this abstract class:

public class AbstractFunctor<T> {
    // Must return Self<U>
    public func map<U>(_ transform: (T) -> U) -> AbstactFunctor<U> {
        fatalError("You must override this method")
    }
}

What we have been describing to you is this class as a protocol that can be applied to any kind of type (structs, enums, classes, etc.)

The important part here, is that we currently can't specify the Self<U> requirement in Swift. Even though that requirement is useful for lots of things; not just for functional stuff.

1 Like

I may be to stupid for fp. This class doesn't look any less cryptic. perhaps it's the very, very high amount of generics in it? Never got beyond generic lists before they start to make zero sense to me...

Okay, let's try something a little less abstract. Array<Element> is a collection of Elements. If you have an Array<Int> then Element is Int. So, if you call map on an Array<Int> then you need to give it a function that converts an Int to some other type. It then produces an array of that type containing each of the values of the first array converted into the new type. For instance [1, 2, 3].map { String($0) } will give you ["1", "2", "3"].

Optional either holds a value of Wrapped or it holds nothing. So, an Optional<Int> holds either an Int or nothing. If you call map on Optional<Int> then you must also give it a function that converts a value of Int into some other type and it'll return an Optional that can hold that type. So, Optional(1).map { String($0) } returns Optional("1") See the pattern?

A functor is any type that has that same map method as Array and Optional. Note: Set is not a functor because it's map doesn't return another Set.

4 Likes

Like Pinkamena, FP doesn't really click with me. However, this explanation of functors is perfect! IMO :slight_smile:

2 Likes

Very important to understand we are actually talking about discrete mathematics and higher algebra under the hood. Functional programming as a paradigm and a branch of discrete mathematics itself simply makes use of those fields in computer science.

The bottom line is, in terms of understanding, it's most likely the math involved rather than FP that doesn't click with one. If I'm wrong, a good idea would be to look up the mathematical definition of a functor; it might help in revealing the correlation between the shared code and your understanding of mathematics.

Thanks @r-peck @anandabits for helping me out, I really appreciate your efforts.
@anthonylatsis Here is my humble understanding. Overall, I agree with you that Programming and Mathematics are really closely related.
Their relationship is somehow revealed by Curry–Howard–Lambek correspondence and Curry–Howard correspondence
Moreover, in Elements of Programming, the author said, he thought Mathematics and Programming is literally the same discipline.
Furthermore, in Church–Turing thesis, it states that lambda-calculus is equivalent to Turing Machine.
And FP as you mentioned is kind of paradigm, and the theory behind that is about lambda-calculus, as we can see in Haskell with GHC complier, the System F is backbone of its type system. GHC, is a fantastic example depicting the link between lambda-calculus and programming.
Therefore, learning maths would deeper our understanding of programming.
(Excuse my shallow understanding about them :relaxed:)

While I agree that showing practical examples - especially used in production code, within the context of a team - is definitely an excellent way to generate pressure towards the addition of native, HKTs in Swift, but I disagree that these encodings should only be buried in a library.

I would accept (and actively contribute to) a library that unifies and standardizes a generic encoding of emulated HKTs in Swift, but I would then use that in my code, to solve practical problems: that's the only way I can really explore abstract concepts and find (and communicate to my collaborators) their utility.

In other words, I'd prefer having a library that provided both some ready-made functors to use, and the ability to cook up a new functor in my code, something that can be readily plugged in the existing framework given by the library.

I strongly disagree with the idea that software development should proceed with some elite subset of developers that masks abstractions within libraries with cool-sounding names, while the rest of the community only uses the final product without any notion of the theory behind, and something so basic as HTKs should really be encoded in the language itself. I tried to use in production code an emulated encoding (for profunctor optics) and it resulted in a massive mess of unreadable code: I probably didn't use an optimal solution in terms of readability, but the amount of boilerplate generic parameters just to make the compiler make assertions about the types involved was too much to bear. So I settled on a different encoding for optics, and a lot of code generation.

But I don't want to sound negative towards HKTs emulation: it's a valuable effort in itself. I simply think that it's just a surrogate of the real thing, a temporary substitute that makes sense in a roadmap that includes the eventual addition of the feature at the language level. Also because this way of programming becomes a true rabbit hole, where the insightful developer can discover wonderful structure that was not apparent at first sight, and encode new powerful abstractions.

3 Likes

A little late reply, but I just discovered this thread and wanted to comment on this. flatMap isn't generally renamed to compactMap. In fact, this rename was made because the so-called flat map on collections weren't really a flat map. But Optional.flatMap is.

In general, a flat map is a function that operates on monads and applies a transform that returns a new monad. And instead of returning a doubly nested structure, it "flattens" the result. To put it more simply:

  • Optional.flatMap takes a transform Wrapped → U? but doesn't return U??. It's flattened to U?
  • Array.flatMap (now) takes a transform Element → [U] but doesn't return [[U]]. It's flattened to [U]
  • Result.flatMap would normally flatten Result<Result<U>> to simply Result<U>
  • and so on.

The old Array.flatMap (and Collection.flatMap etc), confounded two unrelated monads into one. It turned an array of optionals into an array with the nil-optioanals unwrapped. That's fundamentally different that all other cases of flatMap, so this — and only this — version was renamed.

2 Likes

I believe few people are truly too stupid to comprehend some basic FP (or maths). It may certainly be that some people find this mode of thinking to be more readily available to them than others, but with enough effort, I think it can be learned.

In general, "I am too stupid" is a self-fulfilling prophecy. I hear a lot of people say these kinds of things about maths and/or technology but what they often don't realise is that when any mathematician has to read up on some new math they also don't understand everything right away. Highly abstract ideas cannot be comprehended by reading up on them as if you were reading a book of fiction. It requires careful, slow reading, something that needs to be practiced.

I don't want to convince you that you need to understand HKT; I think they are useful (and I think a language should have them, just so it can enable more abstract coding practices that might be useful in some domains), but I don't believe that every app developer needs to know them - it all depends on what you do. But if you are curious, I encourage you to read carefully, not give up because "it looks cryptic", live with the struggle and come back with concrete questions: "You write XY, but I don't understand it because YZ".

4 Likes

Of course you want the ability to conform your own types to a Functor protocol! On the other hand, you probably don't want to have to deal with all of the boilerplate of the HKT encoding every time you do that (I certainly don't!). That is why a library, possibly accompanied by a boilerplate generator, is essential. I'm glad to hear you would be willing to contribute!

This isn't about an "elite subset" as much as it is about those who have motivation and time to work on fundamental building blocks sharing their work. It would be silly for everyone to reinvent the basics and not everyone has time to do so.

A very important principle in Swift is that of progressive disclosure. I believe the best design for a library based on the abstractions and lessons of FP will embrace this principle. This means that users should be able to use the library and derive as much benefit as possible from it without understanding the theory behind it. Of course the library should also support those who wish to dive deeper as well.

Nobody is arguing with you here. In fact, we are working hard to build motivation for adding this feature to the language.

I would be very interested in seeing what you attempted. If you're willing to share, perhaps some of us will have ideas about how to make it work better.

This is a fact of life for working with some of these abstractions. I'm pretty sure Kotlin's Arrow library relies on generation in some places, I believe it is not uncommon in Scala, and even some Haskell libraries rely on boilerplate generation or Template Haskell. It's obviously not preferable to need code generation but it's also not a showstopper.

We're all in agreement here! That said, my impression is that language support for HKT is a ways off so it is much to our advantage to push the limits of the encoding in the meantime and make it as pragmatic as possible.

3 Likes

I agree with everything you wrote, but this bit in particular seems to me of utmost importance, other than a very interesting problem to solve. The progressive disclosure approach is maybe the thing I like the most about Swift philosophy.

A path towards "discovering" higher kinded types – similar to how you pass from bare protocols to protocols with associated types and constraints – would be a really interesting one to follow.

About the profunctor thing, I'm going to pm you some code ;).

1 Like

Absolutely. I don't have a lot of time for side projects right now, but the time I do have I am spending on this very problem. My focus is on delivering the benefits provided by a principled approach in a Swifty way without requiring users to understand the details of how those benefits are realized. At the same time, I am also focused on avoiding a closed environment like Elm where users cannot grow into more sophisticated approaches without leaving the tool they are comfortable with behind. I'm excited to see where this leads, but it's a slow process given my limited time.

5 Likes

I don't have any books on such esoteric math subjects. Sadly the wikipedia is very bad at these topics.

Me and math separated after a long liking when I hit partial differential equation. The only explanation my brain found was "this is madness" and shut down forever to math.

Your best bet in that case is to avoid this, and any other thread that delves into the theoretical aspects of functional programming. When HKT's land in Swift, you won't need to worry about them if you don't want to. That's the joy of working in a multi-paradigm language.

7 Likes

Well that is exactly what I fear - That this won't be possible because the std lib gets flooded by fp stuff. The std lib is complicated enough already. I never have seen such convoluted code in my 30 years of coding and wonder what advantage this really brings to the table... After all a simple string implentation is still miles away but we need esoteric fp stuff. Somehow the priorities in Evolution seem to be totally broken.

1 Like

I don't think anyone in the Swift community wants Swift to garner a reputation as being an impenetrable functional language like what happened to Haskell (which I'm not saying is impenetrable, it just has that reputation.) So if HKT do get support in Swift, you're probably not going to need to know the theory behind them, or implement your own. You may use them occasionally from the stdlib or elsewhere. But odds are you might not even know that what you're using is baked in a ton of category/language theory.

1 Like

I'll agree that, personally, I also feel there are current Swift pain points that seem more urgent to address than HKT (something like better Linux support, making SPM more feature-rich, etc...), but that's not a basis to shut down a discussion about HKT, not least of all because those people knowledgeable about and interested in HKT are not necessarily the same people that would in the same time do those other things; plus, nobody's talking about a timeline yet.

However, you can't just throw your hands up in the air at every explanation for HKT you get and then pretend that "you don't understand how they're useful". Either, you really want to know what they can bring to the table, then you'll have to do the work and actually understand what people are writing here (and argue from a position of knowledge). Or, and that's perfectably respectable and fair, you say "I don't care about this and don't need to", but then it would be good form to respect the opinions of people who do care about HKT and trust that they have some valid reasoning for their opinion.

4 Likes

You seem to think this is possible for everybody. It isn't. At least in Germany category theory and similar topics are VERY esoteric stuff only a small percentage of math majors even do. It's very hard to get books on this topics normal people would have any change of understanding. I have 2 math doctors in my department but neither of them ever had anything about this stuff. So how are normal coders supposed to learn this stuff?