[Proposal] Higher Kinded Types (Monads, Functors, etc.)


(Will Fancher) #1

Hello,

A potent problem in my experience with Swift has been the lack of a way to generalize code that is repetitive on the basis of higher kinded types. For the uninitiated, higher kinded types are the ability to reason about generic types with their type parameters as variable. For example, the Haskell definition for Functor, and a corresponding definition for Maybe (Haskell's equivalent to Optional)

    typeclass Functor f where
        fmap :: (a -> b) -> f a -> f b

    instance Functor Maybe where
        fmap f (Just a) = Just (f a)
        fmap f Nothing = Nothing

This makes it possible to build functions which operate not just on Maybe, but on any Functor.

    fstrlen :: Functor f => f String -> f Int
    fstrlen fstr = fmap length fstr
    
    > -- In the Haskell REPL
    > fstrlen (Just "Hello") -- prints "Just 5"

In Swift, such an abstract function is not possible. There simply is no way to express that your function would like to accept a type that wraps something, and returns that same type wrapping something else.

I propose a new where clause in Swift's generics system that would allow for higher kinded type equality. The syntax would be some operator meant to appear to say "like" or "approximately equal", such as ~=. This operator would mean that the two operands are the same type, but with potentially different type parameters / typealiases. As an example, Functor could be implemented like this:

    protocol Functor {
        typealias A
        func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
    }

The map function declaration says

    A function, fmap, on the Self type (where Self is a Functor with typealias A)
    With type parameter FB, that is the same kind of Functor as Self, with an arbitrarily different A typealias.

This ensures at the type level that given a Functor f, calling f.fmap will result in the same type of Functor. For example, here is both an implementation of Functor, as well as a function which uses a Functor

    extension Optional: Functor {
        func fmap<Mapped>(f: Wrapped -> Mapped) -> Mapped? {
            if let wrapped = self {
                return f(wrapped)
            } else {
                return nil
            }
        }
    }
    
    func fstrlen<
            FString: Functor, FInt
        where
            FInt ~= FString, FString.A == String, FInt.A == Int>
    (str: FString) -> FInt {
        return str.fmap { $0.characters.count }
    }

As another example, the infamous Monad. Monads are everywhere. Countless data types can be expressed as Monads. It is useful to have an abstraction over them, as it provides a means to implement common operations on all of them without repetitive code.

    protocol Monad {
        typealias A
        static func point(a: A) -> Self
        func flatMap<MB where MB ~= Self>(f: A -> MB) -> MB
    }

A function which is relatively useful, join, can be implemented like this:

    func join<M: Monad, MM where MM ~= M, MM.A == M>(mm: MM) -> M {
        return mm.flatMap { $0 }
    }

There's a whole host of functions and theories that higher kinded types enable. This proposal fits nicely with Swift 3's goal of completing generics, and as far as I can see, there are no obvious conflicts with the Swift language. I imagine the implementation might be far from trivial, but that sounds like a discussion worth having.

I look forward to your feedback. Thank you for reading,

- Will Fancher


Generic associated type
(Will Fancher) #2

As a quick addendum, I'd like to point out that implementing Monad, Applicative, and Functor allows for some "free" code reuse. Functor can be defined expressly in terms of Applicative, which can be defined in terms of Monad.

    protocol Monad {
        typealias MonadType
        static func point(a: MonadType) -> Self
        func flatMap<MB where MB ~= Self>(f: MonadType -> MB) -> MB
    }

    protocol Applicative {
        typealias ApplicativeType
        static func pure(a: ApplicativeType) -> Self
        func apply<
                Func, Return
            where
                Func ~= Self, Return ~= Self,
                Func.ApplicativeType == (ApplicativeType -> Return.ApplicativeType)>
        (f: Func) -> Return
    }

    protocol Functor {
        typealias FunctorType
        func fmap<Return where Return ~= Self>(f: FunctorType -> Return.FunctorType) -> Return
    }

    extension Monad: Applicative {
        static func pure(a: MonadType) -> Self {
            return point(a)
        }

        func apply<
                Func, Return
            where
                Func ~= Self, Return ~= Self,
                Func.MonadType == (MonadType -> Return.MonadType)>
        (f: Func) -> Return {
            return f.flatMap { fn in
                return self.flatMap { m in
                    return point(fn(m))
                }
            }
        }
    }

    extension Applicative: Functor {
        func fmap<Return where Return ~= Self>(f: ApplicativeType -> Return.ApplicativeType) -> Return {
            return apply(pure(f))
        }
    }

The effect here is that just defining an implementation of Monad on a type gets Applicative and Functor for "free". Granted, those implementations are far from optimized, but they're free, and can be overridden for optimization. The point is, the higher kinded types in use here drastically reduce repetitive code by allowing common patterns like these definitions of Applicative and Functor to be abstracted.


(Douglas Gregor) #3

Without going into any specifics of higher-kinded types, I sent out a note last night about what the “Swift 3 Generics” effort entails, here:

  https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002718.html

One comment there is that I consider higher-kinded types out-of-scope for Swift 3. There is a *lot* of intended churn in generics already in Swift 3, and we will not be able to handle either the design or the implementation of higher-kinded types as well.

  - Doug

···

On Dec 16, 2015, at 3:11 AM, Will Fancher via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

A potent problem in my experience with Swift has been the lack of a way to generalize code that is repetitive on the basis of higher kinded types. For the uninitiated, higher kinded types are the ability to reason about generic types with their type parameters as variable. For example, the Haskell definition for Functor, and a corresponding definition for Maybe (Haskell's equivalent to Optional)

   typeclass Functor f where
       fmap :: (a -> b) -> f a -> f b

   instance Functor Maybe where
       fmap f (Just a) = Just (f a)
       fmap f Nothing = Nothing

This makes it possible to build functions which operate not just on Maybe, but on any Functor.

   fstrlen :: Functor f => f String -> f Int
   fstrlen fstr = fmap length fstr

-- In the Haskell REPL
fstrlen (Just "Hello") -- prints "Just 5"

In Swift, such an abstract function is not possible. There simply is no way to express that your function would like to accept a type that wraps something, and returns that same type wrapping something else.

I propose a new where clause in Swift's generics system that would allow for higher kinded type equality. The syntax would be some operator meant to appear to say "like" or "approximately equal", such as ~=. This operator would mean that the two operands are the same type, but with potentially different type parameters / typealiases. As an example, Functor could be implemented like this:

   protocol Functor {
       typealias A
       func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
   }

The map function declaration says

   A function, fmap, on the Self type (where Self is a Functor with typealias A)
   With type parameter FB, that is the same kind of Functor as Self, with an arbitrarily different A typealias.

This ensures at the type level that given a Functor f, calling f.fmap will result in the same type of Functor. For example, here is both an implementation of Functor, as well as a function which uses a Functor

   extension Optional: Functor {
       func fmap<Mapped>(f: Wrapped -> Mapped) -> Mapped? {
           if let wrapped = self {
               return f(wrapped)
           } else {
               return nil
           }
       }
   }

   func fstrlen<
           FString: Functor, FInt
       where
           FInt ~= FString, FString.A == String, FInt.A == Int>
   (str: FString) -> FInt {
       return str.fmap { $0.characters.count }
   }

As another example, the infamous Monad. Monads are everywhere. Countless data types can be expressed as Monads. It is useful to have an abstraction over them, as it provides a means to implement common operations on all of them without repetitive code.

   protocol Monad {
       typealias A
       static func point(a: A) -> Self
       func flatMap<MB where MB ~= Self>(f: A -> MB) -> MB
   }

A function which is relatively useful, join, can be implemented like this:

   func join<M: Monad, MM where MM ~= M, MM.A == M>(mm: MM) -> M {
       return mm.flatMap { $0 }
   }

There's a whole host of functions and theories that higher kinded types enable. This proposal fits nicely with Swift 3's goal of completing generics, and as far as I can see, there are no obvious conflicts with the Swift language. I imagine the implementation might be far from trivial, but that sounds like a discussion worth having.

I look forward to your feedback. Thank you for reading,


(Al Skipp) #4

For those thinking, “Hmm… What’s the benefit of all this crazy sounding stuff?”, there’s a rather good practical talk about Functors.

How I Learned to Stop Worrying and Love the Functor:
https://vimeo.com/132657092

Here’s an example that is used:

func sayHello(name: Optional<String>) -> Optional<String> {
  return name.map { "Hello \($0)" }
}

func sayHello(name: Array<String>) -> Array<String> {
  return name.map { "Hello \($0)" }
}

It doesn’t use the usual syntax sugar for Optionals and Array, to make it clear that the only difference between the 2 functions is the type signature. If were possible to express the concept of a Functor, we could write one function that would accept both Optionals and Arrays as parameters – and not just those 2, but any Functor (Result, Future, Signal…).

···

On 16 Dec 2015, at 11:11, Will Fancher via swift-evolution <swift-evolution@swift.org> wrote:

Hello,

A potent problem in my experience with Swift has been the lack of a way to generalize code that is repetitive on the basis of higher kinded types. For the uninitiated, higher kinded types are the ability to reason about generic types with their type parameters as variable.


(Andrey Tarantsov) #5

A tentative -1, based on the following two personal opinions:

First, I consider myself a smart person with a very broad experience with non-functional languages, but reading this makes my mind hurt, a lot:

   typeclass Functor f where
       fmap :: (a -> b) -> f a -> f b

<snip>

This makes it possible to build functions which operate not just on Maybe, but on any Functor.

   fstrlen :: Functor f => f String -> f Int
   fstrlen fstr = fmap length faster

<snip>

   protocol Functor {
       typealias A
       func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
   }

I understand what's going on here, but I never, ever want to see this code anywhere near (my) Swift.

Second, I consider this an anti-pattern:

func sayHello(name: Optional<String>) -> Optional<String> {
func sayHello(name: Array<String>) -> Array<String> {
It doesn’t use the usual syntax sugar for Optionals and Array, to make it clear that the only difference between the 2 functions is the type signature. If were possible to express the concept of a Functor, we could write one function that would accept both Optionals and Arrays as parameters – and not just those 2, but any Functor (Result, Future, Signal…).

Optional.map and Array.map do different things, and unifying them seems harmful.

I'm yet to see a compelling case where monads are useful either, for a real job (and not as a workaround for the idiosyncrasies of the type system).

I believe the way to convince the rest of us (and I would love to be convinced) is to provide a few real, “end-user” app-level use cases and explain the benefit in plain language. In particular, I don't understand the example by Jens Persson, although it seems like a valuable one.

A.


(Will Fancher) #6

Could you elaborate on why you think it's out of scope? Maybe it's just me, but it seems like a very pressing feature. Being unable to write higher kinded abstractions has been a big issue with using Swift generics. It has been impossible to do various kinds of abstractions. It makes generics feel very incomplete, so I feel that it lines up well with the "complete generics" goal.


(Andrew Bennett) #7

+100 to this.

I'm not a huge fan of ~= syntax, but higher kinded types are something
swift would benefit greatly from, particularly with stronger more concise
type constraints, more code reuse.

Another example, one I'm very keen on achieving, is this:

With Swift 1.2 how do you implement map on CollectionType that returns the
same type of collection?

Give it a go, I learnt a lot failing! You're aiming to be able to do this:

extension CollectionType {
    func myMap ....
}

let myDictionary: [String:Int] = ["test": 1]
var otherDictionary = myDictionary.myMap { ($0, Float($1)) }

// does not fail:

assert(otherDictionary is [String:Float])

let myArray: [Int] = [1]

// error: cannot convert '[Float]' to specified type '[String : Float]'

otherDictionary = myOptional.myMap { Float($0) }

The caveats are:
* it has to work regardless of what is implementing CollectionType, and
* it can't have an ambiguous return type

With higher kinded types you could do something like this:

extension CollectionType {
    func myMap<G: GeneratorType>(transform: Generator.Element->G.Element)
-> Self<G> {
        return Self(sequence: AnySequence(self).forEach(transform))
    }
}

···

On Wed, Dec 16, 2015 at 11:39 PM, Al Skipp via swift-evolution < swift-evolution@swift.org> wrote:

On 16 Dec 2015, at 11:11, Will Fancher via swift-evolution < > swift-evolution@swift.org> wrote:

Hello,

A potent problem in my experience with Swift has been the lack of a way to
generalize code that is repetitive on the basis of higher kinded types. For
the uninitiated, higher kinded types are the ability to reason about
generic types with their type parameters as variable.

For those thinking, “Hmm… What’s the benefit of all this crazy sounding
stuff?”, there’s a rather good practical talk about Functors.

*How I Learned to Stop Worrying and Love the Functor:*
https://vimeo.com/132657092

Here’s an example that is used:

func sayHello(name: Optional<String>) -> Optional<String> {
  return name.map { "Hello \($0)" }
}

func sayHello(name: Array<String>) -> Array<String> {
  return name.map { "Hello \($0)" }
}

It doesn’t use the usual syntax sugar for Optionals and Array, to make it
clear that the only difference between the 2 functions is the type
signature. If were possible to express the concept of a Functor, we could
write one function that would accept both Optionals and Arrays as
parameters – and not just those 2, but any Functor (Result, Future,
Signal…).

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Brent Royal-Gordon) #8

Optional.map and Array.map do different things, and unifying them seems harmful.

They actually don’t do different things. Optional can be thought of as an array of zero or one elements; from that point of view, operations like `map` and `flatMap` which are supported on both actually do the same thing.

···

--
Brent Royal-Gordon
Architechies


(Brent Royal-Gordon) #9

For the programmers without functional programming background HKTs gonna be misleading and non-readable. A thousand similar analogies: "<OneMonad> can be seen as <OtherMonad>" will need to be made. Those analogies are gonna break (for example, how would one explain monad transformers in those terms?) and lead to even more confusion.

Believe it or not, I’m actually *not* one of the functional astronauts who believes everything is a `map`. I can sometimes understand what they’re getting at, usually after reading about a dozen different “simple” explanations of a concept, but I think the human factors on the foundations of functional programming are an unmitigated disaster, and that many functional programmers are in deep denial about that. That’s why, when I wrote a Result type, I didn’t give it `map` and `flatMap` operations; I called them `convert` and `then`, to at least try to give some indication of what they actually mean in your code.

Nevertheless, I think the functional view is *useful* and *powerful* so long as it’s also *optional*. Swift should not start emitting sarcastic error messages about monoids in the category of endofunctors, but that doesn’t mean it shouldn’t *permit* people to use these things when they want to.

Support for higher-kinded types merely means that Swift will permit people to do weird abstract functional programming—and a few neat tricks that are more down-to-earth, like a collection-type-preserving `map`—if they want to. It won’t mean *you* will have to. I don’t think this feature is urgent, but I hope it’s supported eventually.

And I hope someone figures out a better name than “monad”. Ugh.

···

--
Brent Royal-Gordon
Architechies


(Krzysztof Siejkowski) #10

Optional.map and Array.map do different things, and unifying them seems harmful.

They actually don’t do different things. Optional can be thought of as an array of zero or one elements; from that point of view, operations like `map` and `flatMap` which are supported on both actually do the same thing.

This discussion convinces me to vote -1 for the HKTs in standard library.

For the programmers without functional programming background HKTs gonna be misleading and non-readable. A thousand similar analogies: "<OneMonad> can be seen as <OtherMonad>" will need to be made. Those analogies are gonna break (for example, how would one explain monad transformers in those terms?) and lead to even more confusion.

As long as the underlying theory is not widely adopted, I think HKTs should be provided by third-party libraries (like swiftz). Swift should just provide generics sophisticated enough to express the those concepts. Scala language uses similar approach (no HKTs in standard library, great generics) with success (scalaz, shapeless libraries).

Krzysztof

···

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Andrey Tarantsov) #11

Optional.map and Array.map do different things, and unifying them seems harmful.

They actually don’t do different things. Optional can be thought of as an array of zero or one elements; from that point of view, operations like `map` and `flatMap` which are supported on both actually do the same thing.

I understand that reasoning, but it's completely contrary to how I (and presumably many other people) normally think. To me, optional is not a 0..1 array, it's just an optional. I don't want a flatMap on optionals (which, I believe, was thankfully removed in Swift 2).

A.


(TJ Usiyan) #12

I am for this but I am sure that we won't get it in Swift 3. I do hope that
we at least consider it enough to ensure that the ABI supports it to some
extent.

TJ

···

On Wed, Dec 16, 2015 at 8:36 AM, Andrew Bennett via swift-evolution < swift-evolution@swift.org> wrote:

+100 to this.

I'm not a huge fan of ~= syntax, but higher kinded types are something
swift would benefit greatly from, particularly with stronger more concise
type constraints, more code reuse.

Another example, one I'm very keen on achieving, is this:

With Swift 1.2 how do you implement map on CollectionType that returns the
same type of collection?

Give it a go, I learnt a lot failing! You're aiming to be able to do this:

extension CollectionType {
    func myMap ....
}

let myDictionary: [String:Int] = ["test": 1]
var otherDictionary = myDictionary.myMap { ($0, Float($1)) }

// does not fail:

assert(otherDictionary is [String:Float])

let myArray: [Int] = [1]

// error: cannot convert '[Float]' to specified type '[String : Float]'

otherDictionary = myOptional.myMap { Float($0) }

The caveats are:
* it has to work regardless of what is implementing CollectionType, and
* it can't have an ambiguous return type

With higher kinded types you could do something like this:

extension CollectionType {
    func myMap<G: GeneratorType>(transform: Generator.Element->G.Element)
-> Self<G> {
        return Self(sequence: AnySequence(self).forEach(transform))
    }
}

On Wed, Dec 16, 2015 at 11:39 PM, Al Skipp via swift-evolution < > swift-evolution@swift.org> wrote:

On 16 Dec 2015, at 11:11, Will Fancher via swift-evolution < >> swift-evolution@swift.org> wrote:

Hello,

A potent problem in my experience with Swift has been the lack of a way
to generalize code that is repetitive on the basis of higher kinded types.
For the uninitiated, higher kinded types are the ability to reason about
generic types with their type parameters as variable.

For those thinking, “Hmm… What’s the benefit of all this crazy sounding
stuff?”, there’s a rather good practical talk about Functors.

*How I Learned to Stop Worrying and Love the Functor:*
https://vimeo.com/132657092

Here’s an example that is used:

func sayHello(name: Optional<String>) -> Optional<String> {
  return name.map { "Hello \($0)" }
}

func sayHello(name: Array<String>) -> Array<String> {
  return name.map { "Hello \($0)" }
}

It doesn’t use the usual syntax sugar for Optionals and Array, to make it
clear that the only difference between the 2 functions is the type
signature. If were possible to express the concept of a Functor, we could
write one function that would accept both Optionals and Arrays as
parameters – and not just those 2, but any Functor (Result, Future,
Signal…).

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Austin Zheng) #13

+1 on HKTs. By the way, there were a couple of people discussing the same
here (https://github.com/typelift/swift/issues/1); you may or may not want
to swap ideas with them and see if you can work together towards a formal
proposal. (However, since it doesn't seem HKTs are in scope for Swift 3, a
proposal might be deferred until next year.)

Austin

···

On Wed, Dec 16, 2015 at 9:08 AM, Matthew Johnson via swift-evolution < swift-evolution@swift.org> wrote:

IMO the keys in a dictionary are not part of the contained values and
therefore not part of the Functor mapping for Dictionary (obviously a map
with different semantics is possible as exhibited by the standard
library). Dictionary should implement Functor by mapping over the values
while preserving the keys.

A similar problem has been noted for Set. In that case it is not possible
to uphold the usual Functor laws. IMO that points to the need for a
protocol with weaker semantics than Functor. It would preserve the
essential structure without preserving the 1 to 1 projection. There are
likely a number of cases where this would make sense. Functor could
inherit from that protocol adding additional semantic requirements but no
additional syntactic requirements.

Matthew

Sent from my iPad

On Dec 16, 2015, at 8:13 AM, Al Skipp via swift-evolution < > swift-evolution@swift.org> wrote:

let myDictionary: [String:Int] = ["test": 1]
var otherDictionary = myDictionary.myMap { ($0, Float($1)) }

// does not fail:

assert(otherDictionary is [String:Float])

The trouble with Dictionary is that peculiar things can happen if we can
map over keys and return a Dictionary.

let dict = ["a":1, "b":2, "c":3]
let dict2 = dict.map { ("x", $1 * 2) } // [“x”:6]

We start with a Dictionary with 3 keys and end up with a Dictionary with 1
key! As the order of the keys is unknown, we have no idea what the value of
the key will be either, it might be 6, 4 or 2.

Swift currently avoids this bedlam by returning an Array of tuples when
‘mapping’ a Dictionary. Strictly speaking this isn’t ‘map’ in the Functor
sense, but then again Dictionary is a rogue that refuses to obey the
Functor laws anyway.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Matthew Johnson) #14

IMO the keys in a dictionary are not part of the contained values and therefore not part of the Functor mapping for Dictionary (obviously a map with different semantics is possible as exhibited by the standard library). Dictionary should implement Functor by mapping over the values while preserving the keys.

A similar problem has been noted for Set. In that case it is not possible to uphold the usual Functor laws. IMO that points to the need for a protocol with weaker semantics than Functor. It would preserve the essential structure without preserving the 1 to 1 projection. There are likely a number of cases where this would make sense. Functor could inherit from that protocol adding additional semantic requirements but no additional syntactic requirements.

Matthew

···

Sent from my iPad

On Dec 16, 2015, at 8:13 AM, Al Skipp via swift-evolution <swift-evolution@swift.org> wrote:

let myDictionary: [String:Int] = ["test": 1]
var otherDictionary = myDictionary.myMap { ($0, Float($1)) }
// does not fail:
assert(otherDictionary is [String:Float])

The trouble with Dictionary is that peculiar things can happen if we can map over keys and return a Dictionary.

let dict = ["a":1, "b":2, "c":3]
let dict2 = dict.map { ("x", $1 * 2) } // [“x”:6]

We start with a Dictionary with 3 keys and end up with a Dictionary with 1 key! As the order of the keys is unknown, we have no idea what the value of the key will be either, it might be 6, 4 or 2.

Swift currently avoids this bedlam by returning an Array of tuples when ‘mapping’ a Dictionary. Strictly speaking this isn’t ‘map’ in the Functor sense, but then again Dictionary is a rogue that refuses to obey the Functor laws anyway.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #15

Could you elaborate on why you think it's out of scope? Maybe it's just me, but it seems like a very pressing feature. Being unable to write higher kinded abstractions has been a big issue with using Swift generics. It has been impossible to do various kinds of abstractions.

I would like to better understand which abstractions you are blocked from implementing (other than the basic HKTs themselves). I understand how HKTs enable some more code reuse, but most of the abstractions that HKTs enable seem to be based on the structure of types rather than on semantics, which makes them:

a) hard to understand
b) hard to document
c) hard to compose into big “towers” of useful semantics.

What I mean here is that there don’t seem to be many useful abstractions out there that can be built upon a “Monad” constraint (for example), and because “Monad” is such a general concept, when you *do* encounter such an abstraction it’s hard to understand what to do with it.

Therefore I have always thought that the costs in language and conceptual complexity vs benefits for HKTs is at least highly debatable. I have occasionally bumped up against the lack of HKTs, but IMO broadly speaking our users are not suffering from the inability to express “Monad” but many of the other generics features we are lacking prevent even the components we *do* provide from functioning completely and properly (e.g. Arrays are never Equatable).

It makes generics feel very incomplete, so I feel that it lines up well with the "complete generics" goal.

It does, but—just my personal opinion—it would probably be the first thing I would cut from the list when considering resource constraints.

-Dave

···

On Dec 16, 2015, at 12:15 PM, Will Fancher via swift-evolution <swift-evolution@swift.org> wrote:


(Al Skipp) #16

let myDictionary: [String:Int] = ["test": 1]
var otherDictionary = myDictionary.myMap { ($0, Float($1)) }
// does not fail:
assert(otherDictionary is [String:Float])

The trouble with Dictionary is that peculiar things can happen if we can map over keys and return a Dictionary.

let dict = ["a":1, "b":2, "c":3]
let dict2 = dict.map { ("x", $1 * 2) } // [“x”:6]

We start with a Dictionary with 3 keys and end up with a Dictionary with 1 key! As the order of the keys is unknown, we have no idea what the value of the key will be either, it might be 6, 4 or 2.

Swift currently avoids this bedlam by returning an Array of tuples when ‘mapping’ a Dictionary. Strictly speaking this isn’t ‘map’ in the Functor sense, but then again Dictionary is a rogue that refuses to obey the Functor laws anyway.


(Will Fancher) #17

With respect specifically to Monads, there are numerous useful abstractions. For one, Applicative and Functor can be derived for free, requiring the no effort on the Monad instance's part. This alone eliminates a lot of code repetition. Additionally, the large majority of functions described for Haskell here are very useful:

https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html.

Those functions come as abstractions over monads which can be easily understood (if you understand monads) and which eliminate a lot of code repetition. The existence of these abstractions makes any Monad type much more robust that it would be on its own.

There are plenty of typeclasses in Haskell that could be implemented in Swift and would be useful if we had HKTs. Foldables and Traversables, for example, are simple and powerful abstractions that would be well worth having. And there are various simpler things besides Haskell typeclasses that can't be done in Swift as it stands. For example, you can't currently take a collection of type C1: CollectionType, and return a value of type C2 where C2 ~= C1, which means you can't perform arbitrary transformations on arbitrary collections. You have to choose an implementation type and use that one.

This isn't to say this should all be in the standard library. I think most of these protocols would be best off in a separate package, to keep the standard simple for newcomers and for those who don't need these features. So I'm not suggesting that the Swift team create Monad, Functor, etc. in the standard library and then extend all the appropriate types to implement those (although it'd be a bonus if the team wanted to). That job would be up to whoever wants to write the package for it. But, in my opinion, the ability for such a package to exist seems very important.


(Andrew Bennett) #18

Good point Al, I avoided Set for similar reasons. Feel free to substitute
Dictionary for String.CharacterView in my example. Unrelated to this
proposal I would like to see a mapValues method on Dictionary.

The main point though was that you can't unambiguously resolve the return
type. A similar example to yours, is that without higher kind types myMap
on CollectionType could allow this to compile:

let oops: String? = [1,2,3].myMap {"\($0)"}

···

On Thu, Dec 17, 2015 at 1:13 AM, Al Skipp <al_skipp@fastmail.fm> wrote:

let myDictionary: [String:Int] = ["test": 1]
var otherDictionary = myDictionary.myMap { ($0, Float($1)) }

// does not fail:

assert(otherDictionary is [String:Float])

The trouble with Dictionary is that peculiar things can happen if we can
map over keys and return a Dictionary.

let dict = ["a":1, "b":2, "c":3]
let dict2 = dict.map { ("x", $1 * 2) } // [“x”:6]

We start with a Dictionary with 3 keys and end up with a Dictionary with 1
key! As the order of the keys is unknown, we have no idea what the value of
the key will be either, it might be 6, 4 or 2.

Swift currently avoids this bedlam by returning an Array of tuples when
‘mapping’ a Dictionary. Strictly speaking this isn’t ‘map’ in the Functor
sense, but then again Dictionary is a rogue that refuses to obey the
Functor laws anyway.


(Will Fancher) #19

Optional.map and Array.map do different things, and unifying them seems harmful.

In terms of category theory, they're not different. They are both arrows from a to b in the Functor category. Obviously that's horribly abstract, so I'll put it this way: If you think of these map functions not as operations on Optional and Array, and instead think of them simply as ways to compose an arbitrary data structure, they are in fact doing the same thing. On an implementation level, and on a runtime level, they perform differently. But on a type level, a theoretical level, and a categorical level, they are the same. You merely need to accept that when using this abstraction without knowledge of the concrete type, you have no reason to make any assumptions about how the implementation and runtime will behave. At that point, all you need is to be sure that the Functor being passed in abides by the Functor laws, and that's just a matter of convention.

First, I consider myself a smart person with a very broad experience with non-functional languages, but reading this makes my mind hurt, a lot:

   typeclass Functor f where
       fmap :: (a -> b) -> f a -> f b

<snip>

This makes it possible to build functions which operate not just on Maybe, but on any Functor.

   fstrlen :: Functor f => f String -> f Int
   fstrlen fstr = fmap length faster

<snip>

   protocol Functor {
       typealias A
       func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
   }

I understand what's going on here, but I never, ever want to see this code anywhere near (my) Swift.

HKTs that come from category theory tend to have this effect. They are hard to understand by reading the protocol definition. Admittedly, this is a big flaw with Monads and with Haskell. It takes a reasonable understanding of category theory for the purpose of this code to be obvious to the reader.

(I will point out that in those code examples, I used absolutely abysmal naming conventions. It could be made marginally more readable and understandable if the naming were better)

I'll take this time to make the point that just because you don't like the way the Functor protocol looks, doesn't mean Array and Optional aren't both Functors and Monads. As a matter of mathematics, if the Monad functions can exist on a type, and they would follow the Monad laws, that type is a Monad whether the implementor likes it or not. Of course it still needs manual implementing, but regardless, the type is theoretically a Monad. (This realization is the reason that the Java team decided to implement flatMap for Java 8's Optional class.)

I believe the way to convince the rest of us (and I would love to be convinced) is to provide a few real, “end-user” app-level use cases and explain the benefit in plain language. In particular, I don't understand the example by Jens Persson, although it seems like a valuable one.

I can (again) link to just a few of the abstract Monadic functions, all of which are very useful in practical applications.

https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html

But perhaps it would also help to describe the architectural decisions that abiding by Monad imposes.

Being Monadic makes you think about data composition, which cleans up the way you design your code. Going back to the Futures example, I could implement future, and subsequently use it, like this:

    public class Promise<T> {
        private var handlers: [T -> ()] = []
        private var completed: T? = nil
        
        public init() {
        }
        
        private func onComplete(handler: T -> ()) {
            if let completed = completed {
                handler(completed)
            } else {
                handlers.append(handler)
            }
        }
        
        public func complete(t: T) {
            completed = t
            for handler in handlers {
                handler(t)
            }
            handlers = []
        }
        
        public var future: Future<T> {
            return Future(promise: self)
        }
    }

    public struct Future<T> {
        private let promise: Promise<T>
        
        private init(promise: Promise<T>) {
            self.promise = promise
        }
        
        public func onComplete(handler: T -> ()) {
            promise.onComplete(handler)
        }
    }

    public func useFutures() {
        downloadURLInFuture().onComplete { content in
            processContentAsync(content).onComplete { processed in
                processed.calculateSomethingAsync().onComplete {
                    ...
                        ...
                            print(finalProduct)
                        ...
                    ...
                }
            }
        }
    }

You can see how this resembles the infamous Node.js issue of callback hell, and how the nesting could quickly get out of hand. If only we had some form of composition... Arrows between Futures... Luckily, Future is a Monad (whether I like it or not!)

    // Monad

    public extension Future {
        public static func point<T>(t: T) -> Future<T> {
            let promise = Promise<T>()
            promise.complete(t)
            return promise.future
        }
        
        public func flatMap<U>(f: T -> Future<U>) -> Future<U> {
            let uPromise = Promise<U>()
            
            onComplete { t in
                f(t).onComplete { u in
                    uPromise.complete(u)
                }
            }
            
            return uPromise.future
        }
    }

Not only do I now get map and apply for free, but I also get a great method of composing Futures. The example from above can now be rewritten to be much more well composed.

    public func useFutures() {
        downloadURLInFuture()
            .flatMap(processContentAsync)
            .flatMap { $0.calculateSomethingAsync() }
            ...
            .onComplete { finalProduct in
                print(finalProduct)
            }
    }

The important thing here is that thinking about Monads helped me discover a better composition model. Now my code can be more readable and well composed.

And again, I'll mention the enormous world of functions and capabilities that can be gotten for free for the sake of even more well-composed code.

I don't want a flatMap on optionals (which, I believe, was thankfully removed in Swift 2).

And why on Earth not? The concrete implementation of it on Optional is very simple and easy to understand, and the method is incredibly useful. Personally, I use it all the time (it was not removed). And again, just because you don't like using flatMap doesn't mean Optional isn't a Monad.

Finally, I'd like to point out that it doesn't hurt any end users not familiar with Monads if Array implements a higher kinded Monad protocol. As far as they have to be concerned, Array just has these useful map and flatMap functions. Meanwhile, those of us who wish to abstract over Monads in general can write our abstract code and implement Monad on our various types which mathematically have to be Monads. It's a layer of robustness and improvement that unconcerned end users don't have to bother themselves with.

While I understand that the Swift team doesn't have the resources to implement everything that everyone wants, and that HKTs aren't very high on their list of priorities, it seems unreasonable to me that one could think of HKTs and Monads as somehow detrimental to the language.


(Will Fancher) #20

As long as the underlying theory is not widely adopted, I think HKTs should be provided by third-party libraries (like swiftz).

I wholeheartedly agree that protocols like Monad and Functor shouldn't be in the standard library. I really think they need their own external package.

But HKTs can't be provided by third party libraries! HKTs are a language level feature! HKTs aren't a collection of types we wish were implemented. HKTs are the language level construct that allows for generic types to be re-parameterized. An HKT proposal would NOT insist that Monad and co. be written into the standard library. It would simply insist that HKTs become physically possible, which they currently are not.