Support type classes or implicits

[baronfel]

NOTE: Current response by @dsyme is here: https://github.com/fsharp/fslang-suggestions/issues/243#issuecomment-916079347

---

Submitted by exercitus vir on 4/12/2014 12:00:00 AM
392 votes on UserVoice prior to migration

(Updated the suggestion to "type classes or implicits", and edited it) Please add support for type classes or implicits. Currently, it's possible to hack type classes into F# using statically resolved type parameters and operators, but it is really ugly and not easily extensible. I'd like to see something similar to an interface declaration:

class Mappable = 
    abstract map : ('a -> 'b) -> 'm<'a> -> 'm<'b>

Existing types could then be made instances of a type classes by writing them as type extensions:

type Seq with
class Mappable with
    member map = Seq.map

type Option with
class Mappable with
    member map = Option.map

I know that the 'class' keyword could be confusing for OO-folks but I could not come up with a better keyword for a type class but since 'class' is not used in F# anyway, this is probably less of a problem.

Original UserVoice Submission Archived Uservoice Comments

[cloudRoutine]

For those who haven't seen it, there's an experimental implementation of type classes for F#

Hopefully if this is implemented as a language feature the verbose attribute syntax will be dropped in favor of proper keywords.

It's hard to see how

 [<Trait>]
 type Eq<'A> = 
     abstract equal: 'A -> 'A -> bool 

 [<Witness>] // a.k.a instance
 type EqInt = 
      interface Eq<int> with 
        member equal a b = a = b

presents any advantage over a more terse syntax like

trait Eq<'A> = 
    abstract equal: 'A -> 'A -> bool 

witness EqInt of Eq<int> = 
    member equal a b = a = b

which provides both brevity and clarity

[dsyme]

@cloudRoutine There are advantages of a kind.

• the compiled (and C#-interop) form is considerably more apparent from the first version. You can see that in the above link by the close relationship between existing F# code and the trait-F# version (basically add attributes). It is like looking at the compiled form. This is significant given that Eq probably has good uses as a normal type as well as a class-of-types/trait. It is also significant if you reflect over these, or explicitly instantiate the hidden type parameters
• it minimizes the actual additions to the F# language design to just a few attributes and a number of special rules. TBH that greatly reduced the number of things that can go wrong when doing the proof-of-concept.
• adding trait and witness as top-level declarations may be OTT, given that all similar things like Struct and AbstractClass and Literal and so on have been added using attributes. But that can be tuned later.

Note that the prototype has some significant limitations, specifically that if explicit instantiation of the witnesses is allowed, then the "dictionary" being passed can't easily "close" over any values - as envisaged it must be passed by passing Unchecked.defaultof<Dictionary>. Passing actual non-null (and perhaps non-struct-typed) objects as dictionaries might solve this.

[cloudRoutine]

It seems I misunderstood how this feature would work. I'd thought that a trait could only be used with witness and that a witness could only use a trait as its interface type.

If an interface with the [<Trait>] attribute can be used like a normal interface, would there be any reason not to adorn every interface with the attribute?

When an attribute needs to be used with a construct in all cases, isn't it effectively the same (from the programmer's perspective) as a top level declaration with extra boilerplate?

I suppose we'll have to rely on tooling to deal with the boilerplate 😞

[dsyme]

If an interface with the [<Trait>] attribute can be used like a normal interface, would there be any reason not to adorn every interface with the attribute?

Off the top of my head there's no reason. We should look at the prototype though (which I felt was in-depth enough to determine questions like this)

[kurtschelfthout]

Note that the prototype has some significant limitations, specifically that if explicit instantiation of the witnesses is allowed, then the "dictionary" being passed can't easily "close" over any values - as envisaged it must be passed by passing Unchecked.defaultof. Passing actual non-null (and perhaps non-struct-typed) objects as dictionaries might solve this.

I don't understand why this would be useful to allow - assuming you mean something like:

[<Witness>] // a.k.a instance
type EqInt(i:int) = 
    interface Eq<int> with 
        member equal a b = a = b
     member __.TheInt = i

Perhaps I'm missing something but allowing that looks very confusing to me.

[Rickasaurus]

I don't mind the attribute style at all. I'm all for keeping the number of keywords in F# as low as possible and building more and more one existing constructs in this manner, avoiding keyword salad.

I do rather like the jargon Rust uses for its type classes (trait and impl) though as I think it's more accessible to normal programmers, witness only makes intuitive sense to people in theorem proving circles, but I'm not super pushing for that to change here just noting my opinion.

One note: because these are written in terms of types it seems like they could never be extended to support statically resolved type parameters. Am I correct?

[Alxandr]

How would you support stuff like functor?

[<Trait>]
type Functor<'f> =
  abstract fmap: ???

[cloudRoutine]

@Rickasaurus can you explain how the example I posted, or one similar to it, creates a "keyword salad"? I don't follow the point you're trying to make. The keyword is already reserved, so it's not like we can use it for ourselves.

because these are written in terms of types it seems like they could never be extended to support statically resolved type parameters. Am I correct?

I can't follow what you mean here either, can you give an example of what you'd like to do?

@Alxandr it can't be supported because we don't have type constructors

[dsyme]

@kurtschelfthout

Re explicit witnesses that close over values

I don't understand why this would be useful to allow

e.g. dependency injection (i.e. parameterization of a witness over some dependency):

[<Witness>] // a.k.a instance
type SomeWitness(someDependency: int->int) = 
    interface SomeTypeConstraint<int> with 
        member SomeOperation a b = someDependency a + someDependency b

... SomeConstrainedOperation(SomeWitness(myDependency),...) ...

or

let f () = 
    let myDependency x = x + 1
    ... some declaration that brings SomeWitness(myDependency) into scope ...

   ... SomeConstrainedOperation(...) ... // witness implicitly added here

The utility of this depends on the degree to which you use witnesses to propagate sets of functions which have a non-trivial dependency base. My understanding is that Scala implicits allow this technique. For example, witnesses propagated by implicits may capture a meta programming universe, which is a value.

[Alxandr]

I still think that not figuring out how to deal with type constructors will severely limit the usefulness of this proposal. Type classes without type constructors would allow for doing abstractions over numerical types, sure, but the lack of ability to do a generic bind and map (and similar) is in my experience what's hurting the most.

[kurtschelfthout]

@dsyme I see, thanks for the explanation.

I don't have extensive experience with Scala implicits. While allowing bringing witness values into scope is more powerful, you also lose ability to reason about code. Here is the argument in more detail in case anyone is interested: https://www.youtube.com/watch?v=hIZxTQP1ifo

Disallow explicit instantiation of witnesses also means we can make them stateless structs and defaultof always works.

It does mean we would have some shenanigans like having to add wrapper types if one type can be a witness of a trait in more than one way (e.g. 'Monoid' and 'int', via either '+' or '*') but it looks to me like that is the vast minority of cases.

We then also have to think about coherence and orphan instances, e.g if there is more than one possible witness is in scope, warn or error, and have some explicit mechanism to disambiguate. even though this somewhat goes against the current F# practice of resolving names to the first thing in scope. Perhaps it would be enough to disallow orphans (i.e. defining a witness in a compilation unit without also declaring either the trait or the type), which would also cover pretty much all use cases I expect.

@Alxandr What you're asking for are higher-kinded types. The feature request for that is here. I don't think the two should be conflated.

[dsyme]

@kurtschelfthout The video is good, thanks

While allowing bringing witness values into scope is more powerful, you also lose ability to reason about code.

I generally prefer arguments in utilitarian terms (bug reduction, safety under refactoring, stability of coding patterns under changing requirements, does a mechanism promote team-cooperation etc.). He makes some of these, though "reasoning about code" is not an end in itself, but can definitely give good utilitarian outcomes. But how many bugs (= lost developer time) are really caused by a lack of coherence, e.g. conflicting instances? I talked about this when last with Odersky and we figured it was very few. But how much time is spent fiddling around with type classes trying to get them to do the right thing, only later hitting some massive limitation like the inability to have local instances, or the inability to abstract instances with respect to a dependency?

A good example where lack of abstraction can hit is string culture. Let's say you create a huge amount of code that uses a swathe of string-related type classes that assume invariant culture (e.g. the ubiquitous show methods). Then you want to localize your code w.r.t. culture, and decide you want to do it properly (rather than via a thread local) and pass the culture as a captured parameter. But your type class instances can't be parameterized. So you either have to remove all those type classes from your code or resort to dynamic argument passing though thread-local state. Painful and discontinuous.

From what I see people in favor of type classes choose examples that are relatively context-free (no local instances required, or only in contrived examples), while people in favour of implicits choose examples where local instances are commonly needed (e.g. Scala meta programming examples, parameterizing by the meta-programming universe implied by a set of libraries). Both sets of examples also put on heavy pressure w.r.t. dependencies (e.g. types-with-nested-types as parameters - the scala meta-programming examples re replete with these) and higher-kinds.

Swift is another important comparison area since it is setting expectations in a new generation of devs.

[drvink]

@dsyme Scala implicits are plagued with problems, the least of which being that Scala's notion of parameterized modules is a runtime phenomenon, leading to issues like being able to have two instances of a Set parameterized by an ordering T and conflate them. This is claimed by some as an intentional benefit, but it seems categorically worse to have this "flexibility" than even the limitations of coherence that are imposed by a naive encoding of Haskell-style type classes, i.e. one lacking more complicated extensions like overlapping instances. The use cases for Scala-style implicits mostly seem to be either bandages for existing code or a form of syntactic sugar at best. Thread-local storage is indeed a hallmark of afterthought-oriented programming, but at least it's fairly explicit and gives no illusions of safety.

@kurtschelfthout Given that it's already possible to encode higher-kinded types to some degree via SRTP, this is probably the best time to have that discussion if we're already having the long-awaited one on type classes for F#, so I don't think @Alxandr is wrong to be bringing it up in this thread. It's difficult to imagine a type class mechanism incapable of Functor/Applicative/Monad bringing significant value; I don't think people want them in F# just so that they can write Show. (CEs are another good example of a feature that would be much more valuable if not for a limitation that feels too extreme; while the clumsiness of composing monads is not specific to F#, CEs and SRTP would at least be complementary features if CE implementation functions--Bind/Return/etc.--were allowed to be static members instead of only members.)

It's worth mentioning that the modular implicits¹ proposal for OCaml solves many (all?) of the concerns related to both voiced so far in this thread. There is a shorter and more recent presentation³ from some of the designers as well for those curious.

1: arXiv:1512.01895 [cs.PL] 2: Modular implicits for OCaml - how to assert success

[dsyme]

Scala implicits are plagued with problems

Yeah, I know.

... leading to issues like being able to have two instances of a Set parameterized by an ordering T and conflate them. ...

Yes, I know. However TBH I don't think the case is proven this causes bugs in practice. When talking to Odersky about this recently I said that I doubted that a any production bugs had been caused by this problem, or at least vanishingly few. And the workarounds (such as using a unique key type for sets/maps, which is basically what we already do in F# if you need a custom comparer) are not particularly problematic. Certainly the situation is no worse than the existing .NET collections.

Anyway I'd need to see much stronger utilitarian evidence that this truly is as critical as claimed - it seems like a well-intentioned article of mathematical faith (and one which I would wholeheartedly subscribe to from a purely academic perspective) more than one grounded in the reality of software practice. To contrast, the problems of "not being able to parameterize or localize my instances" are very much grounded in modern software reality and standard F# practice. In F#, being able to parameterize a thing by values is very fundamental, even if you have to plumb a parameter to each function of a module or member of a class explicitly. Active patterns, for example, can be parameterized, for good reasons.

The use cases for Scala-style implicits mostly seem to be either bandages for existing code or a form of syntactic sugar at best.

From the F# perspective the whole thing is really syntactic sugar just to pass some parameters implicitly :)

I would like to see an analysis of the extra powers of Scala implicits by someone who favors the mechanism and uses it well, or at least can speak to its use cases. Some of the use cases I've seen in the area of meta-programming look quite reasonable. The mechanism has problems though.

I'll look at the modular implicits work again, it's been a while. Last time I looked it would need extensive modification to be suitable for F#, and it didn't strike me that F# needed to aim for the same goals, but I'll look more carefully. It's a very tricky area to be honest, so many subtleties.

[Rickasaurus]

I rather like that Scala will give you an error with an ambiguous instance. Ideally it wouldn't matter, but F# is neither pure nor lazy and so it seems much safer to me to be sure about which instance you're using.

Along these lines I think tooling for this feature might be extremely important. It will certainly be necessary to have an easy way to figure out which instance is being used and where it lives.

@drvink Side note: I remember suggesting parameterized modules a long time ago, although I wasn't clever enough to see the relationship with type classes back then. What I wanted them for was mostly being able to avoid using classes in cases where some static parameterization was required up front. Also figured it might be used to make certain code more efficient, if the compiler was smart about it.

Modular implicits are pretty neat. I like that they are very explicit with their syntax and so it's more clear to beginners what is going on. One of the weakness (but also paradoxically a great strength) of Haskell is that there is so much magic going on that it ends up taking a lot of mental gymnastics to understand what complex code is doing because so much is inferred. Although, that magic also leads to very terse code.

[kurtschelfthout]

@dsyme

A good example where lack of abstraction can hit is string culture. Let's say you create a huge amount of code that uses a swathe of string-related type classes that assume invariant culture (e.g. the ubiquitous show methods). Then you want to localize your code w.r.t. culture, and decide you want to do it properly (rather than via a thread local) and pass the culture as a captured parameter. But your type class instances can't be parameterized. So you either have to remove all those type classes from your code or resort to dynamic argument passing though thread-local state. Painful and discontinuous.

You put the many possibilities we already have to propagate values implicitly (statics, thread locals, whatever the thing is called that propagates across async calls) in a negative light, perhaps rightly so. What is the advantage of adding another implicit value propagation mechanism - how is it that much better than the existing ways?

Concretely, in the string culture example. Without implicit value passing, we can change all the witnesses to take CultureInfo.CurrentCulture into account instead of the invariant culture, or refer to some other global. Then we have to make sure that the right value for that is set at the right places in the program. Where this sort of thing needs to be scoped statically I've usually resorted to using blocks in the past, and that seems to work out pretty well.

With implicit value passing, we very similarly have to change all the witnesses to take an extra constructor argument - the culture - and use it in the implementation. And then we have to make sure that the right implicit value is brought in scope at the right places in the program. Perhaps I am missing something but it feels very similar.

On the positive side, my main reasons for supporting this proposal is to:

1. Support open extensibility - i.e. allow existing types (that I don't control the code for or don't even know exist yet) to be treated as if they implement an interface (trait).
2. Support what I will loosely call abstraction over constructors - i.e. allow traits with methods like Create : 'T

Don't know if it's me but I keep running into this limitation, and there are no clean workarounds (I know, because I've worked around them many times in different ways). One example is FsCheck allows you to check any type that it can convert to a Property, which is unit, bool, and functions that return any of those (among other things). But the type of check can only be : 'P -> unit note no constraint or indication whatsoever on what this 'P can be, no way for the user to extend allowable types, and consequently hard to document what is actually going on here, leading to much confusion. Something like: Property 'P => 'P -> unit would be so much nicer, esp. if the tooling would catch up and you'd be able to look up straightforwardly what all the witnesses are for Property that are in the current scope. In my estimation, this would significantly reduce the learning curve for new users, improve the documentation, and give advanced users an extra useful (and easily discoverable) extension point.

I realize you can do all of that with implicit values too, because they're strictly more powerful, but I just feel I already have plenty of choice to access values implicitly - perhaps even too many :)

[Alxandr]

I've used implicits in scala (that being said I've used scala for all of about 2 weeks, so I'm no expert). And what it was used for was passing an execution context around to async code. Basically, it served the purpose of System.Threading.Tasks.TaskScheduler.Current. That being said, implicits might be a better way to handle this than static getters (backed by threadstatic values and other black magic), but I still think that it should be taken into consideration that .NET already has a idiomatic (I think I'm using this word correctly) way of dealing with ambient contexts. And if that needs to be changed I think that's something that should probably be agreed upon by the entirety of the .NET community. I also think these are two different issues. Type classes deals with abstractions of features, whereas implicits are way to implicitly "attach" context to functions. Not to mention the fact that they aren't even mutually exclusive since scala has both (sort of).

Also, I agree with @drvink that while allowing people to implement Show is cool and all, it might also cripple traits into being a niche feature that nobody uses without also figuring out how to deal with type constructors at the same time, with or without CLR support.

[Savelenko]

@Alxandr As a practicing "enterprise" software engineer, I can assure you, that traits are much needed today, while most of engineers in my immediate environment, which I consider typical, cannot and need not grasp the concept of type constructors in order to be more productive and output better architected programs due to traits. It's just that day-to-day programming does not involve writing (library) code which abstracts over type constructors. But also conceptually, it is not the case that traits as discussed here are "severely limited", because traits/type classes are about polymorphism/overloading, while type constructors are about which terms are considered legal types in a programming language. The two notions are quite orthogonal and we should not mix them here.

[yawaramin]

Fwiw, my 2c: I've been playing around recently with a very simple dictionary-passing approach to typeclasses (encode the instances as record values holding the operations as functions), see e.g. https://github.com/yawaramin/fsharp-typed-json/blob/ae4c808d3619e3703451211ba2bf079cb6c61bc0/test/TypedJson.Core.Test/to_json_test.fs

The core operation is a function to_json : 'a To_json.t -> 'a -> string which takes a typeclass instance and a value, and converts the value to a JSON string using the typeclass instance. This is fairly simple and easy to implement and use, but the thing that keeps it short of being 'magical' is that I have to manually pass in the instance. Here's the relevant part of the definitions:

module To_json =
  type 'a t = { apply : 'a -> string }
  ...
  module Ops = let to_json t = t.apply

Now, if I could instead mark parameters as implicit, say e.g. with #: let to_json (#t : 'a t) = #t.apply and we had a syntax rule that implicit parameters must always be declared first, perhaps.

And correspondingly declare the instances as: let #string : string t = { apply = sprintf "\"%s\"" }

The compiler would have to convert calls like to_json "a" into to_json #string "a", after finding the implicit with some implicit search mechanism. And that makes it 'magical' again.

[kurtschelfthout]

Swift is another important comparison area since it is setting expectations in a new generation of devs.

Indeed. I think the closest Swift comes to something like this is through protocols. Compared to interfaces, besides methods and properties they can impose static methods and constructors on the implementing entity. Also some requirements can be specified as optional (you then need to use optional chaining, like the ?. operator in C# to call these. Not really relevant to this discussion). Finally protocols can provide default implementations. So really they are a sort of halfway between interfaces and abstract classes. More possibilities than interfaces, less than abstract classes (in particular they can't define fields), but this allows more flexibility down the line (e.g. a type can be a subtype of multiple traits).

Swift then allows implementing these on types much in the same way as interfaces/abstract classes, but it also allows "protocol extensions". Again comparing to .NET these are like extension methods, but for entire protocols. In this sense, protocol extensions are close to what was proposed in #182.

It's interesting also that like extension methods, protocol extension can impose additional requirements on the extended type at the point of extension using type argument constraints. The example they give is, translated to fictional F# syntax:

//ICollection<'TElement> an existing type
//this extends all ICollections to be also TextRepresentable (another interface/protocol)
//_if_ their elements are also TextRepresentable.
type ICollection<'TElement when 'TElement:TextRepresentable> with
    interface TextRepresentable with
        member self.TextualDescription =
            let itemsAsText = self |> Seq.map (fun elem -> elem.TextualDescription)
            "[" + string.Join(", ", itemsAsText) + "]"

This is very close to how protocols in Clojure work - except they are not typed.

It seems to me that this is qualitatively different from type classes or implicits. In particular, type classes are a static overloading mechanism. Implicits are syntactic sugar to have the compiler pass implicit arguments to functions. UPDATE Protocols allow you to extend dynamic dispatch (the vtable, in some sense) on existing types after the fact. This is wrong, the methods on protocol extensions are statically dispatched, see here and here. I don't know enough about modular implicits in OCaml to comment how it related in one sentence.

In terms of votes this wide range of possibilities for this one suggestion seems problematic, but then of course we have a BDFL @dsyme so the votes are just to appease us unwashed masses anyway ;)

Perhaps it makes more sense to have a goal-directed discussion, instead of focusing on mechanisms. What can't you express right now (or is awkward to express) that you think this suggestion should address? (I gave my 2c on that in an earlier comment)

[dsyme]

Perhaps it makes more sense to have a goal-directed discussion,

@kurtschelfthout I'd like to see someone trawl through the various uses of protocols in Swift and pick out 3-4 examples (which couldn't be achieved by OO interfaces, and which feel different in application to type classes)

[kurtschelfthout]

@dsyme There are a number of use cases of protocols and protocol extensions in the video and slides here: https://developer.apple.com/videos/play/wwdc2015/408/

(note also my update in the comment above - protocol extensions are static constructs, closer to typeclasses than I originally thought, but with more of an OO "feel".).

[Alxandr]

I'd like to point out that protocols (from Objective-C) is in it's entirety implemented as interfaces in Xamarin last I checked. The only thing I wasn't able to do in C# that you could do with protocols was using default implementations of methods and id<Protocolo1, Protocol2> (which arguably is really cool).

[Rickasaurus]

The formulation we already have in the branch is pretty great, I especially like that it's almost zero cost. Small things like if fst/snd could be applied to all tuple types would be a huge quality of life improvement. (Although, I guess this could be done with SRTPs).

Mulling on it a bit, I think that the type type-name with syntax would be really clean for witnesses. Do we really need the witnesses to have names? Maybe it could look something like:

type int with
    [<Witness>]
    interface Eq<int> with 
      member equal a b = a = b

type Tuple<'a, 'b> with
   [<Witness>]
   interface TupleFst<'a> with
     member fst a = a.Item1

This seems more natural syntactically in F#. Just a thought.

[Alxandr]

At that point, do we even need [<Withness>]? The fact that you're implementing an interface in an extension should do the trick, no?

[cloudRoutine]

@Rickasaurus this is what those tuple functions look like when implemented with SRTP it causes as terrible explosion of IL and makes a giant dll for a tiny amount of code.

And the flatten function on the bottom used to break the compiler, I haven't tried compiling it since the upgrades to overload resolution were merged. Traits are so much cleaner and nicer than that hacky mess.

[gusty]

@Rickasaurus the example from @cloudRoutine uses SRTP with overloads, it's possible to define a simple SRTP function without overloads like:

let inline item1 (t :'a ) = ((^a) : (member Item1: _ ) t)

but it would only work with the compiled representation of the tuples:

item1 (box (1,2,3) :?> Tuple<int,int,int> )

So the overloads is the only solution, in fact it's a partial solution since you will never cover all tuple sizes as in the item1 function above.

The same will apply to this type class implementation, you will need to add infinite witnesses for all tuple sizes.

It would be nice to have some basic generic functions over tuples to avoid doing that.

[radekm]

The same will apply to this type class implementation, you will need to add infinite witness for all tuple sizes.

Maybe we can extend type providers to provide these witnesses (like implicit macros in Scala).

[tldrlol]

I am very much in favor of adding Typeclasses to the language. However, I also think that implementing typeclasses without support for HKTs would be a huge missed opportunity for F#.

The argument of having to support HKTs on the framework level to allow for seamless interop with other languages has been raised before. And has been presented as a barrier to implementing this feature before. It is my opinion that this should not be a barrier for being able to implement this feature in F#.

Consider an example dictionary for a Functor typeclass:

type Functor<'a, 'b, 'fa, 'fb> = {
  fmap : ('a -> 'b) -> 'fa -> 'fb
}

I see no reason, why the F# compiler should not have the capacity of placing restrictions constraints on 'fa or 'fb to have the same type constructor, even if these contraints cannot be enforced by another language such as C#.

We have existing problems at the interop barrier with C# already. For example, there is nothing stopping a C# client from assigning null to any F# type which should supposedly prevent the null value. On the F# side of things, we also have to adhere to some hard rules, such that it would be easy for other .NET languages to consume. For example, we need to use class-wrappers and avoid DUs (which makes for the most gnarly side of F# in a sense).

I see no reason why we should not have the capability of being able to levelrage the power of HKTs on the F# side. Perhaps, with the addition of the suggestion of avoiding type constructor constraints in code that is meant to be consumed by other languages.

[cloudRoutine]

C# seems to be taking this approach

Shapes and Extensions

This is essentially a merger of two other proposals:

Extension everything, which allows types to be extended with most kinds of members in the manner of extension methods, and Type Classes, which provide abstraction over sets of operations that can be added to a type separate from the type itself.

https://github.com/dotnet/csharplang/issues/164

I hope whatever approach C# eventually settles on doesn't end up hamstringing the development of higher level abstractions for F# in order to maintain a level of construct compatibility.

@dsyme if C# is willing to go as far as type classes, shouldn't F# be able to push the boundary to HKTs?

[yawaramin]

... HKTs are, truth be told, not so esoteric in the ML world thanks to the traditional parameterised modules (functors) approach. F# has a great opportunity to leap ahead of C# here by doing a simple defunctorising implementation 😉

[dsyme]

if C# is willing to go as far as type classes, shouldn't F# be able to push the boundary to HKTs?

Please see the notes in this repo for how we (or at least I) approach the F# language design. I do not use the logic that F# has to have everything C# has and more. Where would that lead us? If Rust adds XYZ, should F# add XYZ and ABC? If Borland Delphi had EFG etc....?

If C# added type classes (and that is a very, very big if given the long history of C# saying they will add things and then, well, not doing it....) then we would have to consider interop. But honestly, one of the greatest advantages of F# over C# is relative simplicity. Do you really see 2 million C# programmers enjoy the experience of needing to master "shapes" and "extensions" in addition to "interfaces" and "abstract base classes" and "partial classes" and "abstract methods" and "delegates" and .... Honestly, using core OO well is very difficult to master. Adding two subtle new foundational concepts to C# may mess with the C# world (while also bringing some expressive benefits).

That's not to say "never" - but I'm also a sincere believer in "less is more" rather than "let's add a major new foundational construct every version because other people are doing it"

[yawaramin]

@dsyme is it fair to interpret your comment as (implicitly) saying, 'Closing, wontfix'?

[Savelenko]

On the other hand, it would be a pity if C# became a bloated, complex language, but with constructs very useful to a good programmer, if used carefully, and F# wouldn't have "better defined" and therefore simpler counterparts of these constructs.

I do agree that this should not be a universal must-have-feature-superset principle, but pattern matching is a good example. Folks knowing C# and a priori accepting all its extensions as good, high-tech or innovative have a chance to see how "real" pattern matching should be. Folks who use mainly F# or knowledgable of other FP languages are satisfied with not having to use incomplete and weird versions of this essential feature. Simplicity and a basic set of features done right can drive adoption of languages (e.g. F#) over half-baked, thrown-together and overcomplicated features of other languages (e.g. C#, Scala). PureScript is a great example of a simple language which does many things right, winning hearts of many die-hard haskellers.

Type classes (even without HKT) seem essential enough to belong to such features too, otherwise they will be missed even more by typical F# programmers when/if C# does get them. And for F# learners the situation could be "F# doesn't even have shapes", although it is indeed very good that F# "doesn't even have" a lot of other stuff.

[dsyme]

@dsyme is it fair to interpret your comment as (implicitly) saying, 'Closing, wontfix'?

@yawaramin No, please don't interpret it like that. I was just saying that the F# language design is not a feature arms race with other languages, nor is its F#'s mission to be C#++

I was part of the research team at MSR that did the prorotypes for type classes in C# and F# last year (Claudio Russo and Matt Windsor led the way, very impressively too). We iterated closer to a good design that would not intrude on the productive core of F# programming. However, I am extremely loathe to add a version of this mechanism that is incompatible with any future C# mechanism - among other things, the utility of type classification mechanisms goes up the more libraries share common notions.

I and many others will be keeping a close eye on the C# discussions and giving input. The prototypes we did convinced me that the F# compiler is in good shape to make adding this kind of feature relatively straight-forward once the design is stabilized.

[yawaramin]

@dsyme OK. Thank you for your care in stewarding F#. It's a language I can recommend to any level of programmer, from complete beginner to expert.

[kurtschelfthout]

No, please don't interpret it like that. I was just saying that the F# language design is not a feature arms race with other languages, nor is its F#'s mission to be C#++

Just make sure you don't wind up bringing a knife to a gun fight...

[dsyme]

Just to mention that a rough prototype of F# type classes from a hackathon last year is here: https://github.com/MattWindsor91/visualfsharp/tree/hackathon-vs. It's very "experimental", but did work at the time for some decent examples.

People on this thread might want to bring this branch up-to-date as a shared experimental fork? The branch is also potentially informative for other proposed suggestions too, e.g. solving operator constraints using extension members (which overlaps with type classes), since potential solution lists are added to the TAST data structure.

@MattWindsor91, Claudio Russo and others and may wish to help with this, I'm not sure (they did the initial work). I can advise if you need help too.

[dsyme]

@kurtschelfthout Note the diff for the branch mentioned above is not particularly large. However it is hard to make it satisfactory (in addition to all the caveats about C#, interop, complexity etc. mentioned above).

[kurtschelfthout]

@dsyme I'm down with giving that a go. I'm not underestimating the complexity of it, so I'll keep promises to a minimum...

One thing I would like to see is more specific and concrete areas of worry with this general proposal. There are pretty vague statements like the complexity isn't worth it etc. What kind of costs are we (most) worried about? Compiler implementation complexity? C# interop? Potential bifurcation from C#? Impact on the ecosystem? Can we think of ways to mitigate those?

[dsyme]

Concerns:

• Design complexity and mistakes? - Yes, especially interaction with existing features (subtyping, units of measure, existing kinds of types, quotations, reflection, type providers, whatever)

• Compiler implementation complexity? - Not so much, but mainly interaction with implementations of existing features

• C# interop? - Yes, I'm concerned about this, if they implement it. But I'm kind of assuming they won't.

• Potential bifurcation from C#? Yes, I'm very concerned about this if they implement it

• Impact on the ecosystem? - Yes, I'm concerned about this.

• Complexification? - Yes, very, very, very concerned about this. See https://wiki.haskell.org/Typeclassopedia. We don't seriously want all this kind of thinking to be prevalent and common in the F# ecosystem

• Feature creep? Yes, I'm very concerned by this. See the regular demands for HKT. Then Type Families. Then GADTs. Then ....

• Can we think of ways to mitigate those? - It's hard

[kurtschelfthout]

@dsyme I rebased the prototype on latest master; it seems to work at least as far as the trait examples included are concerned. It's entirely possible I've broken something else :) https://github.com/kurtschelfthout/visualfsharp/commits/traits

[kurtschelfthout]

@Rickasaurus

Do we really need the witnesses to have names?

From looking at the examples in the prototype: Yes - that means we can disambiguate at the call site, e.g. typical sum/prod monoid example:

concat<int, Sum> [1; 2; 3; 4]

where the Sum is the name of the witness you want to use here.

Although I was originally a bit sceptical about the syntax - it does tend to feel more verbose than strictly necessary esp on the witness side - on balance with reflection and C# interop in the picture a straightforward relation with the implementation is valuable.

Also consider that the proposed design makes both traits and witnesses first class constructs. Whereas say in Haskell both typeclass declarations and instances are special. For example, you can't really reuse a Haskell instance declaration anywhere else, or even refer to it (you can of course extract the implementation in separate functions or such, but that's not my point). Whereas here the witness is a named type that you can potentially say compose with others. You can reflect over it. You can implement it using reflection. Etc.

[dsyme]

@dsyme I rebased the prototype on latest master; it seems to work at least as far as the trait examples included are concerned. It's entirely possible I've broken something else :) https://github.com/kurtschelfthout/visualfsharp/commits/traits

@kurtschelfthout Thanks. Perhaps we should start fsprojects\fsharp-variations for holding community speculative branches and variations? (Just wondering how to get this out of personal copies of repos, not critical to do that though)

[kurtschelfthout]

@dsyme

Perhaps we should start fsprojects\fsharp-variations for holding community speculative branches and variations? (Just wondering how to get this out of personal copies of repos, not critical to do that though)

I am neutral. I checked what the prototype for accepting types for a TP was doing and noticed it was on a personal account too. I think what would be useful though is if we could have long lived experimental branches in the main visualfsharp repo - that would also allow us to run the full test suite and so do impact analysis etc.

[dsyme]

I am neutral. I checked what the prototype for accepting types for a TP was doing and noticed it was on a personal account too.

ok, thanks

[kurtschelfthout]

re: old comment from @dsyme

@kurtschelfthout I'd like to see someone trawl through the various uses of protocols in Swift and pick out 3-4 examples (which couldn't be achieved by OO interfaces, and which feel different in application to type classes)

So I've trawled for as long as I can stand it ;) with the help of https://swiftunboxed.com/protocols/swift-standard-library-protocols-lessons/ and the http://swiftdoc.org/ (scroll down to see all the protocols in the standard library).

I don't know what you meant exactly by "feel different in application to type classes" but my feeling on the use of protocols in swift is that they tie together cleanly and with a single, more uniform and discoverable concept what F# and .NET does with a potpourri of operators, attributes, interfaces, SRTPs and ad hoc compiler features like equality/comparison constraints. Protocol usage in Swift's standard library certainly feels different to the type classes in Haskell's prelude in that they are simply pragmatic - basic things like equality, collections, conversions instead of Haskell's group theory or category theory based classes.

Anyway, so you'll find the Equatable, Comparable and Hashable. As everyone knows, these are handled by ad hoc compiler magic in F# and otherwise badly in C#. These use cases are not well handled by interfaces because you can't conditionally implement an interface - e.g. Example<'T> is only comparable if 'T is comparable.

Swift also uses protocols for various forms of conversion of types to and from other representations (strings, binary, whatever), e.g. LossLessStringConvertible. For these in .NET we have the detestable SerializableAttribute (as I hope anyone who relies on this in a large-ish codebase can attest to: there's always someone who adds a new type and forgets to add the SerializableAttribute, which then breaks serialization much later in production). We can't use interfaces here because of no conditional implementation; and also protocols play much nicer if you are writing a serialization library that is not part of the standard library like this Swift lib because of course you want to handle the primitive types like string and int, and you can't implement interfaces on those. But you can make them conform to protocols. Typically in .NET this is handled by reflection and basically giving up types/documentation/discoverability. WIth a Serializable protocol, here's how you can express things in Swift: https://github.com/typelift/Alchemy/blob/9a009928b7e20d934fc3427ace886957519f3372/Tests/AlchemyTests/AlchemySpec.swift#L13 Note if you see that you immediately know all there is to know about how to make your types serializable - you don't need to go an look up which attribute to apply, and whether serialization per field is opt-in or opt-out, and how to opt-out etc.

Then there are protocols like Arithmetic and BitwiseOperations which are generally handled in .NET by a fixed set of operators. I think the problems with expressing simple things like "addable" and "can take absolute value" as interfaces are well known, and it feels like the OO-world has given up on even trying. Just to re-iterate: most of these operations are symmetric in some way, while interface implementations force you to choose a first argument that is special. Return type cannot be easily specialized. Hierarchies just aren't a natural way to model basic math - it is mostly based on overloading (which is basically what typeclasses/protocols/traits are a direct mechanism for).

Last ones I'd like to highlight briefly:

• CustomReflectable Swift seems to use mirror-based reflection framework which has as advantage over GetType in that its extensible i.e. a type can control how it would like to be represented via reflection.
• CustomPlaygroundQuickLookable Bit of a silly name perhaps but plays the role of something like fsi.AddPrinter and imo infinitely better discoverable and clear.
• There are also some Haskell's Show equivalents, which again I like better than ToString + StructuralFormatAttribute + DebugVisualizers etc because hey I never programmed Swift in my life but by just looking at the documentation website I already know how to customize how my type looks in the playground, the debugger etc. I bet lots of .NET devs have never written a debugger visualizer, used the attribute, and most F# devs have not used fsi.AddPrinter or know of its existence.

EDIT: One important difference between the traits proposal here and Swift protocols is that Swift does not support type-parametrized (generic) protocols, but does support protocols with associated types. This has interesting and pretty far-reaching practical consequences. The comparisons here are still valuable but keep that in the back of your head.

[kurtschelfthout]

On equality and comparison constraints. @dsyme's original blog post when these were introduced makes for some interesting reading on this topic, esp. the paragraph "Design Alternatives. Could interface constraints suffice? What about type classes?"

Extract for the tldr crowd (though given all of the above, who am I kidding....):

The underlying (and well known) problem is that interface implementation in .NET is unconditional – a type either supports an interface or it doesn’t. This is a fundamental limitation of .NET generics. In F#, it is part of our design methodology to add additional, erased constraints to work around such limitations. ... As a result, .NET interface constraints are not sufficient to allow us to tackle equality and comparison constraints in F#. This underlies the decision to include equality and comparison constraints as new, erased constraints in the F# language. Readers familiar with Haskell and other functional languages will be well informed of all the issues relating to equality and comparison, since the issues are fundamental to equality and comparison in any typed language, but particularly functional languages. The mechanisms used to address these points in F# are reminiscent of a weak form of type classes, particularly in the way equality and comparison are dependent on the structure of types, and the way these dependencies can be declared for any type. Haskell also lets users define their own constraints, in a very rich (and sometimes fairly complicated!) way. Now, equality and comparison are the only operations in the F# Core Library that are statically conditional on the structure of types. This raises the question as to why F# doesn’t allow user-defined constraints (beyond interface constraints), and why other constraints can’t be declared conditional. After all, it is well known that it can be useful to make other operations conditional on structure too, e.g. printing and serialization. The answer is two-fold. Firstly, in future versions of F# we may consider extending the mechanisms used to implement equality and comparison constraints to include user-defined constraints. Secondly, however, for many common used constraints (such as formatting and serializability), there are other ways to achieve the same thing in F# that are not particularly amenable to using constraints. Also, in each case there are serious interactions with .NET libraries and existing design practice to consider. Finally, some conditional constraints would require a “dictionary passing” implementation. This brings added difficulties. Equality and comparison constraints are not dictionary passing – they are ultimately implemented via interfaces and overrides. As a result, for F# in Visual Studio 2010, we concentrated on resolving the interactions with .NET for the critical cases of equality and comparison, rather than adding a completely general mechanism.

And see also other requests for adding more constraints like equality and comparison which have similar properties: https://github.com/fsharp/fslang-suggestions/issues/317

I thought it might strengthen this proposal if we can figure out a way for traits to somehow subsume the existing equality and comparison constraints. You could see an equality constraint as an empty trait with witnesses that are provided by the compiler automatically for a type if it satisfies certain conditions.

On the ambitious end of the spectrum perhaps programmers can express "witness derivation" rules by hooking into the type provider machinery: "witness provider" ;) since in the prototype witnesses are just types anyway this doesn't sound so far fetched. For example, you'd be able to express that a type has a witness for the serializiable trait if it has a SerializableAttribute or is an Exception with a serialization ctor. In these cases no actual witness needs to be provided since the trait has no methods; it's the (potentially) conditional type constraint that needs to be picked up.

Less ambitiously, it may be possible to declare equality and comparison as empty traits in FSharp.Core and have the compiler "translate" the existing constraints to these new traits (in a backwards compatible way), without allowing the user (or perhaps anything outside FSharp.Core) to add such translations. This may remove some of the learning curve as equality and comparison are at least optically part of an overarching trait concept (i.e. the type constraints would be shown with the same syntax, you wouldn't see when a : equality anymore, but however we choose to syntactically show trait constraints. I can also see the other side of the argument here though - it would be a pretty leaky abstraction.

[dsyme]

@kurtschelfthout These are really very good notes, thank you for taking the time to write them (and to dig up my old notes on equality/comparison constraints)

[kurtschelfthout]

In this instalment of my continuing brain-dump ;) I look at one particular concrete example of where I'd like to use traits, and compare it with a bunch of alternatives, and try to explain where I think they fall short. Rest assured, it has nothing to do with category theory - it is a design problem in FsCheck that continues to annoy me. I'll explain from first principles.

In almost all frameworks for testing in .NET I'm aware of, one expresses tests as unit -> unit functions: such a test function fails if an exception is thrown, and succeeds otherwise. Presto: a cottage industry of assertion frameworks comes into existence to basically throw informative exceptions. This adds, imo, considerably to the learning curve of using a test runner (I for one can never remember if the expected value goes left or right). As Expecto shows a test runner really just runs a bunch of named functions. What if instead of this meagre type unit->unit, we write a new test library that allows more than one type to be testable? For example:

• bool is testable.
• unit->unit is testable
• but also unit->bool is testable
• in fact anything like unit->'a when 'a is testable is testable.
• Lazy<testable> is also testable
• Like support for parametrized tests? Perhaps ['a] * 'a -> testable should be testable.
• ...

And I'd like to provide a function to the user of some type like test : testable -> unit which prints the result of the test to the console, say.

This sounds nice, but if we're authoring such a test library we have some criteria:

• Discoverability. Users of the library should be able to see or infer at a glance which types are testable, ideally by looking at the API docs so that they know for sure it's up to date and correct. Tooling should be able to list suggestions on which types are testable.
• Extensible. The set of types that are testable should be extensible,
  • by the creator of the library: e.g. to add support for testing asynchronous functions by implementing something to make Async<'a> when 'a is testable testable. And Task<'a> while we're at it.
  • but also by users of the library. After all perhaps Scott likes railway-oriented programming - why shouldn't he be able to make his Either type testable too?
• Type-safe. If we're going to allow a variable number of types to be returned from test functions, we'd like some support from the compiler to make sure that the type that the user returns is really something that can be tested by our test library - otherwise some confusion will ensue. Who tests the tests?
• Composable. I'd like to add some API to combine testable things. For example, I'd like to be able to write a function, and allow users of the library to write functions, of the form and: testable -> testable -> testable which would take two testables, test them, and creates a testable that succeeds if both testables succeed.

Now let's take a look at the tools F# gives the library author to write such an API.

1. Interfaces. Pretty much out on the first strike, because I can't implement interfaces retroactively on function types, bool or any of the other existing types I'd like to make testable.
2. Create a Testable type (e.g. a union type Success | Failure) and create a bunch of overloaded functions to lift the testable types into Testable: Testable.ofUnit, Testable.ofBool and so on. The test function has signature test: Testable -> unit. The problem with this is two-fold:
   • as soon as you add a generic type to the list of testables, the number of overloads you have to write explodes. Effectively, you can't implement fully a rule like "unit->'a is testable if 'a is testable because it means that unit->unit->unit->bool is testable, and so you'd have to add essentially an infinite number of overloads.
   • You could of course compromise and only add unit, bool and generic types of those. But it's an uncomfortable compromise.
   • It's actually worse, because for every API function like and: testable -> testable -> testable you have to add the same overloads; and for all the combinations of the n arguments. Or force the user of the library to sprinkle Testable.ofXXX everywhere.
   • Overall, such an approach is only practical if you are dealing with a small set of primitive types.
3. We can create a Testable type as in option 2 but instead of writing all the overloads we can use reflection to analyse the passed in "testable" (statically this is perhaps just a generic type with a naming convention like 'testable) and so create the Testable that we want. The test function has signature test: 'testable ->unit where 'testable is just a generic type.
   • Clearly this gives up almost all of the criteria above. But it's the most flexible to use as long as you don't care about documentation, type-safety and extensibility outside the library itself.
   • Note implementing this reflective analysis of a type is quite subtle. For example there are different methods in the reflection API to get at the generic type argument of an array vs a generic type.
4. We can use SRTPs which at the core really satisfy most if not all of the criteria above. I'm not going to go into implementation details, just imagine a load of ^a symbols everywhere.
   • It feels like feature abuse, and tightrope walking ("if I change this, will things still work? Wait, what is the syntax for that again?")
   • the inline becomes infectious and needs to go all over the place. This must do something bad with code size and I'm not sure what inlining happens across assembly boundaries.
   • the biggest problem I have with this approach though is that you effectively can't write recursive functions with testables because of the inline. So if you're thinking of writing an andAll : [testable] -> testable by recursively calling and, forget about it. I realise you can write things iteratively instead, but it feels like a pretty big thing to take away, and it stings pretty badly when you realise this limitation after having carefully navigated all the pitfalls with this approach.

So my contention is there is currently no good solution or workaround in F#. While with traits, the solution becomes absolutely standard and ticks all the boxes: create a trait Testable and implement a witness for each type you'd like to be testable, and use induction over the generic type argument to implement witnesses for generic types. This is pretty short code to write, it's extensible easily within the library and outside, and the compiler provides documentation and type checking.

I hope it doesn't sound too smooth or like I'm setting you up for a foregone conclusion. As a sort of evidence that I just didn't make this up for the purpose of this request, FsCheck currently uses option 3. Quite a bit of code is dedicated to doing the type analysis. A lot of work has gone into documentation to clarify what is testable and what is not to users. I struggle with this; for v3 I actually considered to drop the whole testable thing and just allow functions that return unit. (I can provide links as evidence for all of these but I've spent quite some time on this post already so I'm going to hope you'll believe me on this. "The struggle is real" and all that ;) ) In conclusion, if traits were available in F# I would use them for this problem in a heartbeat.