Support type classes or implicits #243

baronfel · Oct 20, 2016

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

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

cloudRoutine · Oct 30, 2016

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

@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.

dsyme · Oct 31, 2016

@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.

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 😞

cloudRoutine · Nov 3, 2016

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 😞

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)

dsyme · Nov 3, 2016

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)

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.

kurtschelfthout · Nov 10, 2016

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.

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?

Rickasaurus · Nov 10, 2016

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?

How would you support stuff like functor?

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

Alxandr · Nov 13, 2016

How would you support stuff like functor?

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

@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

cloudRoutine · Nov 13, 2016

@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

@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.

dsyme · Nov 14, 2016

@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.

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.

Alxandr · Nov 15, 2016

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.

@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.

kurtschelfthout · Nov 15, 2016

@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.

@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.

dsyme · Nov 15, 2016

@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.

@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

drvink · Nov 15, 2016

@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

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.

dsyme · Nov 15, 2016

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.

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.

Rickasaurus · Nov 16, 2016

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.

@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:

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).
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 :)

kurtschelfthout · Nov 16, 2016

@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:

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).
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 :)

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.

Alxandr · Nov 16, 2016

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.

@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.

Savelenko · Nov 18, 2016

@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.

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.

yawaramin · Nov 20, 2016

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.

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)

kurtschelfthout · Nov 24, 2016

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)

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)

dsyme · Nov 25, 2016

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)

@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".).

kurtschelfthout · Nov 25, 2016

@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".).

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).

Alxandr · Nov 25, 2016

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).

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.

Rickasaurus · Nov 30, 2016

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.

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

Alxandr · Nov 30, 2016

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

@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.

cloudRoutine · Nov 30, 2016

@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.

@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.

gusty · Dec 1, 2016

@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.

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).

radekm · Dec 1, 2016

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).

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.

tldrlol · Jan 4, 2017

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.

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.

dotnet/csharplang#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?

cloudRoutine · Feb 24, 2017

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.

dotnet/csharplang#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?

... 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 😉

yawaramin · Feb 25, 2017

... 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 😉

@robkuz Let's be realistic though, SRTPs have much further to go than your toy example implies. Show me a trait with multiple methods, in a trait hierarchy, with default implementations, where one of the trait methods is overloaded by return type only (e.g. member pi : 'a), and a witness with a generic type argument where the witness implementation requires a trait constraint. What happens when there is a trait defined in library A, and then you have multiple witnesses for the same type (say in project B and C, but doesn't really matter) how do you disambiguate?

Note all that works in the current trait prototype and already looks relatively nice and intuitive to me, e.g. see the examples: https://github.com/kurtschelfthout/visualfsharp/tree/traits/examples

Not saying it's ready to go and all problems are solved, far from it, but imo much closer than SRTPs. The syntactic improvement you mention - also note that only covers instance member SRTP calls - is really an insignificant step in comparison to where it needs to be.

kurtschelfthout · May 28, 2017

@robkuz Let's be realistic though, SRTPs have much further to go than your toy example implies. Show me a trait with multiple methods, in a trait hierarchy, with default implementations, where one of the trait methods is overloaded by return type only (e.g. member pi : 'a), and a witness with a generic type argument where the witness implementation requires a trait constraint. What happens when there is a trait defined in library A, and then you have multiple witnesses for the same type (say in project B and C, but doesn't really matter) how do you disambiguate?

Note all that works in the current trait prototype and already looks relatively nice and intuitive to me, e.g. see the examples: https://github.com/kurtschelfthout/visualfsharp/tree/traits/examples

Not saying it's ready to go and all problems are solved, far from it, but imo much closer than SRTPs. The syntactic improvement you mention - also note that only covers instance member SRTP calls - is really an insignificant step in comparison to where it needs to be.

@kurtschelfthout sure SRTPs are limited and I wouldn't know how to express hierarchies or default implementations (multiple methods thou are possible). In anyway I am not opposed against Traits. Not at all. The better/stronger the features the better.
The only thing is that I am worried that this Trait proposal will never happen or maybe only when C# has implemented it (bc interop etc.) and meanwhile we struggle to express certain kinds of abstractions that are hard to express at the moment with F# (as you have laid out in your own examples about FSCheck).

robkuz · May 29, 2017

@kurtschelfthout sure SRTPs are limited and I wouldn't know how to express hierarchies or default implementations (multiple methods thou are possible). In anyway I am not opposed against Traits. Not at all. The better/stronger the features the better.
The only thing is that I am worried that this Trait proposal will never happen or maybe only when C# has implemented it (bc interop etc.) and meanwhile we struggle to express certain kinds of abstractions that are hard to express at the moment with F# (as you have laid out in your own examples about FSCheck).

I mostly like the trait proposal as it stands currently, I would just like to take into consideration that while it might not be for the first version, it would likely be a good idea to think about some way to extend/improve whatever construct we decide to go for to something that is able to express fmap and/or bind eventually.

Alxandr · May 29, 2017

I mostly like the trait proposal as it stands currently, I would just like to take into consideration that while it might not be for the first version, it would likely be a good idea to think about some way to extend/improve whatever construct we decide to go for to something that is able to express fmap and/or bind eventually.

One question about the actual implementation (I don't have it running on my machine) - Do SRTPs pick up methods defined in Traits?

robkuz · May 29, 2017

One question about the actual implementation (I don't have it running on my machine) - Do SRTPs pick up methods defined in Traits?

@robkuz Tried it, but without success: https://gist.github.com/jindraivanek/4d461800cfc9d1bf33507c783aec5712. But maybe my SRTP-fu is too low :)

jindraivanek · May 31, 2017

@robkuz Tried it, but without success: https://gist.github.com/jindraivanek/4d461800cfc9d1bf33507c783aec5712. But maybe my SRTP-fu is too low :)

@robkuz @jindraivanek No they won't. Because (somewhat similar to methods defined in extensions) the methods are not defined on the actual class. To make this somewhat clearer, the type of something like Show.show in @jindraivanek's example (which is how you would call the trait, e.g. Show.show 1 or Show.show 1.0) is:

> Show.show;;
val it : ('a -> string) when 'a implies 'b and 'b :> Show<'a> and 'b : struct

This reveals the implementation strategy: beside the actual value of type 'a that you pass in, the method has an additional parameter 'b which represents the witness - and the compiler allows you to omit the witness type because it is implied by 'a. Essentially what the compiler does is track witnesses in scope and compiles Show.show 1 to something like defaultof<ShowInt>.show 1 because it figured out that ShowInt is the type that implements Show<int> and you're passing in an int.

(Note that to make member constraints work with extension methods the compiler would have to do a similar thing as tracking witnesses - track extension members in scope).

All that said - I think since the compiler now passes the witnesses around in a lot of places, perhaps it is not too hard to add resolution of member constraints to witnesses. Not convinced it's desirable though.

kurtschelfthout · May 31, 2017

@robkuz @jindraivanek No they won't. Because (somewhat similar to methods defined in extensions) the methods are not defined on the actual class. To make this somewhat clearer, the type of something like Show.show in @jindraivanek's example (which is how you would call the trait, e.g. Show.show 1 or Show.show 1.0) is:

> Show.show;;
val it : ('a -> string) when 'a implies 'b and 'b :> Show<'a> and 'b : struct

This reveals the implementation strategy: beside the actual value of type 'a that you pass in, the method has an additional parameter 'b which represents the witness - and the compiler allows you to omit the witness type because it is implied by 'a. Essentially what the compiler does is track witnesses in scope and compiles Show.show 1 to something like defaultof<ShowInt>.show 1 because it figured out that ShowInt is the type that implements Show<int> and you're passing in an int.

(Note that to make member constraints work with extension methods the compiler would have to do a similar thing as tracking witnesses - track extension members in scope).

All that said - I think since the compiler now passes the witnesses around in a lot of places, perhaps it is not too hard to add resolution of member constraints to witnesses. Not convinced it's desirable though.

@jindraivanek thanks for trying this out.
@kurtschelfthout Thanks for the explanation. As for the "desirability" ... give me a release of this for a month and I will come back with at least 2 instances where it will be ;-)

A question to the SRTP that you are showing. Can the implies part be written verbatim? or is that only available in the fsi?

robkuz · Jun 2, 2017

@jindraivanek thanks for trying this out.
@kurtschelfthout Thanks for the explanation. As for the "desirability" ... give me a release of this for a month and I will come back with at least 2 instances where it will be ;-)

A question to the SRTP that you are showing. Can the implies part be written verbatim? or is that only available in the fsi?

Here is some code by @jindraivanek that stresses the actuall type class implementation. Can anybody explain why this fails? https://gist.github.com/jindraivanek/e217d9352fa67f1adf9dedd441c45154

robkuz · Jun 2, 2017

Here is some code by @jindraivanek that stresses the actuall type class implementation. Can anybody explain why this fails? https://gist.github.com/jindraivanek/e217d9352fa67f1adf9dedd441c45154

This might be a bit late in response @dsyme but I didn't see any similar arguments. Your language already has all the complexity of Typeclassopedia, you just don't have explicit names for them defined in the language. Your language has functors, applicatives, monads, and monoids. So to say you don't want that level of complexity is really saying you don't want people talking about the complexity which is already there. What is a fair argument is that you should not be required to speak with this level of preciseness but it seems strange to bar people from being able to.

voronoipotato · Jun 28, 2017

This might be a bit late in response @dsyme but I didn't see any similar arguments. Your language already has all the complexity of Typeclassopedia, you just don't have explicit names for them defined in the language. Your language has functors, applicatives, monads, and monoids. So to say you don't want that level of complexity is really saying you don't want people talking about the complexity which is already there. What is a fair argument is that you should not be required to speak with this level of preciseness but it seems strange to bar people from being able to.

(BTW, I'm now back interning with @crusso - it may be possible that I'll be diving back into F# traits, but it depends on what the lie of the land is. I need to catch up with this discussion first!)

EDIT: Just to clarify, this is neither definite nor official, just a possibility at this stage. I just wanted to ping to say that I'm still interested and back in the wider area.

MattWindsor91 · Aug 7, 2017

(BTW, I'm now back interning with @crusso - it may be possible that I'll be diving back into F# traits, but it depends on what the lie of the land is. I need to catch up with this discussion first!)

EDIT: Just to clarify, this is neither definite nor official, just a possibility at this stage. I just wanted to ping to say that I'm still interested and back in the wider area.

So, I wanted to play around and try implement some limited form of this via SRTP working with type extensions. My strategy was to pass the NameResolutionEnv to the point at which GetRelevantMethodsForTrait was called such that the ExtensionMethods could be found through there.

My problem was that the type variables did not align in the way I hoped. While I could fully view the relevant ExtensionMethods of the correct name at the correct point of execution, naively passing them along to the constraint solver didn't give the desired behaviour (duh!).

Could anyone with more knowledge of this area of the codebase give me some hints as to where to go from here? Even if not accepted into the codebase I'd love to understand the compiler a bit more in this regard.

TobyShaw · Aug 17, 2017

So, I wanted to play around and try implement some limited form of this via SRTP working with type extensions. My strategy was to pass the NameResolutionEnv to the point at which GetRelevantMethodsForTrait was called such that the ExtensionMethods could be found through there.

My problem was that the type variables did not align in the way I hoped. While I could fully view the relevant ExtensionMethods of the correct name at the correct point of execution, naively passing them along to the constraint solver didn't give the desired behaviour (duh!).

Could anyone with more knowledge of this area of the codebase give me some hints as to where to go from here? Even if not accepted into the codebase I'd love to understand the compiler a bit more in this regard.

@TobyShaw If you look at the implementation in https://github.com/kurtschelfthout/visualfsharp/tree/traits/ then it may give you some inspiration about how to propagate the "solutions" to constraints through the constraint solver etc. These are the solution to type class constraints, though I think you could use much the same technique for the solutions to SRTP trait constraints

dsyme · Aug 17, 2017

@TobyShaw If you look at the implementation in https://github.com/kurtschelfthout/visualfsharp/tree/traits/ then it may give you some inspiration about how to propagate the "solutions" to constraints through the constraint solver etc. These are the solution to type class constraints, though I think you could use much the same technique for the solutions to SRTP trait constraints

@TobyShaw Actually, looking again it wasn't quite as clear as I remembered :) Some notes

We add a WitnessEnv to the constraint solver env made here
We check the WitnessEnv in the constraint solver when constructing coercion constraints - you would check it when constructing MayResolveMember constraints
The CoercesTo constraint data is extended to have a small portion of the witness environment (just a list of possible type solutions) recorded as part of the constraint. You would have to do the same for MayResolveMember cosntraints - recording a set of possible solutions from extension members. These would be ValRef which may potentially cause problems, I'm not sure

dsyme · Aug 17, 2017

@TobyShaw Actually, looking again it wasn't quite as clear as I remembered :) Some notes

We add a WitnessEnv to the constraint solver env made here
We check the WitnessEnv in the constraint solver when constructing coercion constraints - you would check it when constructing MayResolveMember constraints
The CoercesTo constraint data is extended to have a small portion of the witness environment (just a list of possible type solutions) recorded as part of the constraint. You would have to do the same for MayResolveMember cosntraints - recording a set of possible solutions from extension members. These would be ValRef which may potentially cause problems, I'm not sure

Awesome, thanks very much!

I'm sure this sort of thing has been done loads of times before, still fun nonetheless.

TobyShaw · Aug 17, 2017

Awesome, thanks very much!

I'm sure this sort of thing has been done loads of times before, still fun nonetheless.

@TobyShaw No, it hasn't - and I've been meaning to do exactly this for some time now :) Let me know if you get anywhere

dsyme · Aug 17, 2017

@TobyShaw No, it hasn't - and I've been meaning to do exactly this for some time now :) Let me know if you get anywhere

See also this: #230

Well, it seems I managed to a get working example rewriting @jindraivanek gist. The idea was to find an expression where the Unchecked.defaultof<MyGenericType<_>> instantiation is a value type.
It works well with reference types too. Update: Unfortunately it only works for ToString...

F# Interactive:

> typeof<Show<int>>.IsValueType;;      
val it : bool = false
> typeof<StructShow<int>>.IsValueType;;
val it : bool = true
> Unchecked.defaultof<Show<int>>;;      
val it : Show<int> = null
> Unchecked.defaultof<StructShow<int>>;;
[<Struct>]
val it : StructShow<int> = StructShow

Example:

    open System

    type Show<'a> = 
        abstract member show: 'a -> string
    
    [<Struct>] 
    type StructShow<'a> =
        member __.show x = x.ToString()
    
    [<Struct>]
    type MyStruct =
        override __.ToString() = "MyStruct.ToString()"


    type MyClass() =
        override __.ToString() = "MyClass.ToString()"


    let inline show'< ^w, ^a when ^w : (member show : ^a -> string)> (w: 'w, a: 'a) =
        (^w: (member show : 'a -> string) Unchecked.defaultof<'w>, a)
    let inline show (x: 'T) = show'(Unchecked.defaultof<StructShow<_>>, x)
    
    show 1 |> printfn "%s"
    show 1.1 |> printfn "%s"
    show (MyStruct()) |> printfn "%s"
    show (MyClass()) |> printfn "%s"

1
1.1
MyStruct.ToString()
MyClass.ToString()

zpodlovics · Aug 23, 2017

Well, it seems I managed to a get working example rewriting @jindraivanek gist. The idea was to find an expression where the Unchecked.defaultof<MyGenericType<_>> instantiation is a value type.
It works well with reference types too. Update: Unfortunately it only works for ToString...

F# Interactive:

> typeof<Show<int>>.IsValueType;;      
val it : bool = false
> typeof<StructShow<int>>.IsValueType;;
val it : bool = true
> Unchecked.defaultof<Show<int>>;;      
val it : Show<int> = null
> Unchecked.defaultof<StructShow<int>>;;
[<Struct>]
val it : StructShow<int> = StructShow

Example:

    open System

    type Show<'a> = 
        abstract member show: 'a -> string
    
    [<Struct>] 
    type StructShow<'a> =
        member __.show x = x.ToString()
    
    [<Struct>]
    type MyStruct =
        override __.ToString() = "MyStruct.ToString()"


    type MyClass() =
        override __.ToString() = "MyClass.ToString()"


    let inline show'< ^w, ^a when ^w : (member show : ^a -> string)> (w: 'w, a: 'a) =
        (^w: (member show : 'a -> string) Unchecked.defaultof<'w>, a)
    let inline show (x: 'T) = show'(Unchecked.defaultof<StructShow<_>>, x)
    
    show 1 |> printfn "%s"
    show 1.1 |> printfn "%s"
    show (MyStruct()) |> printfn "%s"
    show (MyClass()) |> printfn "%s"

1
1.1
MyStruct.ToString()
MyClass.ToString()

Sadly, I didn't have much luck taking your approach @dsyme, I'm not sure I have a good enough mental model of the constraint solving code to get anywhere with it.

Could you comment on the likely effectiveness of the approach I suggested last time? I got the impression you didn't think it was going to be an effective solution, but I'm not sure why that is.

I have the NameResolutionEnv in scope at the point in which I call GetRelevantMethodsForTrait, so while it currently only searches through intrinsic methods, it ought to be possible to adapt it to search through the extensions members stored in the name resolution env. The only problem is that the types attached to the extension members won't match the types stored in the trait.

I need to be updating the types stored in the NRE any time I freshen type variables in other constraints, otherwise they'll be out of date by the time I want to search through it.

So the solution is just to:
Update NRE in step with when I'm updating typars (not sure how easy this is)
Pass the NRE to GetRelevantMethodsForTrait, and search it for a trait which matches in name and types. (this is easy)

TobyShaw · Sep 13, 2017

Sadly, I didn't have much luck taking your approach @dsyme, I'm not sure I have a good enough mental model of the constraint solving code to get anywhere with it.

Could you comment on the likely effectiveness of the approach I suggested last time? I got the impression you didn't think it was going to be an effective solution, but I'm not sure why that is.

I have the NameResolutionEnv in scope at the point in which I call GetRelevantMethodsForTrait, so while it currently only searches through intrinsic methods, it ought to be possible to adapt it to search through the extensions members stored in the name resolution env. The only problem is that the types attached to the extension members won't match the types stored in the trait.

I need to be updating the types stored in the NRE any time I freshen type variables in other constraints, otherwise they'll be out of date by the time I want to search through it.

So the solution is just to:
Update NRE in step with when I'm updating typars (not sure how easy this is)
Pass the NRE to GetRelevantMethodsForTrait, and search it for a trait which matches in name and types. (this is easy)

After posting this, I realised how what you were suggesting would work.

It's effectively the same idea is what I proposed, you store the extensions members in the constraint rather than in the NRE (the NRE is used to populate the constraints). This way, the algorithm for freshening type variables needs less modification, since it's just one type of constraint that needs changing, rather than a whole new thing (the NRE).

Thanks for being a rubber duck, I guess :) I'll give it another go tomorrow.

TobyShaw · Sep 13, 2017

After posting this, I realised how what you were suggesting would work.

It's effectively the same idea is what I proposed, you store the extensions members in the constraint rather than in the NRE (the NRE is used to populate the constraints). This way, the algorithm for freshening type variables needs less modification, since it's just one type of constraint that needs changing, rather than a whole new thing (the NRE).

Thanks for being a rubber duck, I guess :) I'll give it another go tomorrow.

So, small update:

Using this test program:

type System.Int32 with static member TestMethod(a : System.Int32, b : System.Int32) = a + b

type System.Boolean with static member TestMethod(a : System.Boolean, b : System.Boolean) = a && b

type MyType = | MyType of int static member TestMethod(MyType(a),MyType(b)) = MyType(a + b)

let inline myTestMethod< ^A when ^A : (static member TestMethod : ^A * ^A -> ^A) > (a : ^A) (b : ^A) =
    ( ^A : (static member TestMethod : ^A * ^A -> ^A) (a,b) )

[<EntryPoint>]
let main args = ignore (myTestMethod true false); 0

Seems like I'm able to select the correct extension method.

However, despite being recorded as I hoped, it still gives an error message of:

"fsharptest.fs(11,25): error FS0193: The type 'Microsoft.FSharp.Core.bool' does not support the operator 'TestMethod'"

May have to take a break for today, but any thoughts on this would be much appreciated.

TobyShaw · Sep 14, 2017

So, small update:

Using this test program:

type System.Int32 with static member TestMethod(a : System.Int32, b : System.Int32) = a + b

type System.Boolean with static member TestMethod(a : System.Boolean, b : System.Boolean) = a && b

type MyType = | MyType of int static member TestMethod(MyType(a),MyType(b)) = MyType(a + b)

let inline myTestMethod< ^A when ^A : (static member TestMethod : ^A * ^A -> ^A) > (a : ^A) (b : ^A) =
    ( ^A : (static member TestMethod : ^A * ^A -> ^A) (a,b) )

[<EntryPoint>]
let main args = ignore (myTestMethod true false); 0

Seems like I'm able to select the correct extension method.

However, despite being recorded as I hoped, it still gives an error message of:

"fsharptest.fs(11,25): error FS0193: The type 'Microsoft.FSharp.Core.bool' does not support the operator 'TestMethod'"

May have to take a break for today, but any thoughts on this would be much appreciated.

@dsyme I lied, didn't take a break. Got it compiling as expected (though it's definitely not a clean solution at the moment).

Haven't checked whether the resulting IL generated works as expected, although I can't see why it wouldn't.

Microsoft/visualfsharp#3582

TobyShaw · Sep 14, 2017

@dsyme I lied, didn't take a break. Got it compiling as expected (though it's definitely not a clean solution at the moment).

Haven't checked whether the resulting IL generated works as expected, although I can't see why it wouldn't.

Microsoft/visualfsharp#3582

@TobyShaw does that already work with generic and recursive types as well?
so that this would work

let inline show< ^A when ^A : (static member show : ^A  -> string) > (a : ^A) =
    ( ^A : (static member Show : ^A -> string) a )

type System.String with static member Show(a : System.String) = sprintf "{String: %A}" a

type System.Boolean with static member Show(a : System.Boolean) = sprintf "{Boolean: %A}" a

type MyType<'a> = | MyType of 'a 

type MyType<'a> = with
    static member Show(v: MyType<'a>) = 
        match v with
        | MyType a -> sprintf "{MyType: %A}" (show a)

[<EntryPoint>]
let main args = 
    let o = show "myself"               // {String: myself}
    let p = show true                   // {Boolean: true}
    let q = show 1                      // compiler error as no Int.Show in place
    let r = show (MyType "my way")      // {MyType: {String: my way}}
    let s = show (MyType 1)             // compiler error as no Int.Show in place
    let s = show (MyType (MyType true)) // {MyType: {MyType: {String: true}}}

    0

robkuz · Sep 15, 2017

@TobyShaw does that already work with generic and recursive types as well?
so that this would work

let inline show< ^A when ^A : (static member show : ^A  -> string) > (a : ^A) =
    ( ^A : (static member Show : ^A -> string) a )

type System.String with static member Show(a : System.String) = sprintf "{String: %A}" a

type System.Boolean with static member Show(a : System.Boolean) = sprintf "{Boolean: %A}" a

type MyType<'a> = | MyType of 'a 

type MyType<'a> = with
    static member Show(v: MyType<'a>) = 
        match v with
        | MyType a -> sprintf "{MyType: %A}" (show a)

[<EntryPoint>]
let main args = 
    let o = show "myself"               // {String: myself}
    let p = show true                   // {Boolean: true}
    let q = show 1                      // compiler error as no Int.Show in place
    let r = show (MyType "my way")      // {MyType: {String: my way}}
    let s = show (MyType 1)             // compiler error as no Int.Show in place
    let s = show (MyType (MyType true)) // {MyType: {MyType: {String: true}}}

    0

So, you currently can't write that extension member on MyType in F#, it won't compile. Since for some reason, extension members can't have constrained type parameters on.

My patch does not address this, but I agree it would be a necessary addition in order for this to fully recreate the benefits of typeclasses.

TobyShaw · Sep 15, 2017

So, you currently can't write that extension member on MyType in F#, it won't compile. Since for some reason, extension members can't have constrained type parameters on.

My patch does not address this, but I agree it would be a necessary addition in order for this to fully recreate the benefits of typeclasses.

The problem with this is that there is no type safety in static member Show(v: MyType<'a>) =. This can result in major headaches because of you having misspelled something because you can't state the contract you're trying to fulfill.

Alxandr · Sep 15, 2017

The problem with this is that there is no type safety in static member Show(v: MyType<'a>) =. This can result in major headaches because of you having misspelled something because you can't state the contract you're trying to fulfill.

Why would that be?

type MyType<'A> = with
    static member Show< ^B when ^B : (static member show : ^B  -> string) >(v: MyType< ^B >) = 
        match v with
        | MyType a -> sprintf "{MyType: %A}" (show a)

That should do the trick (disregarding that fact that the way to state this is really awful)

robkuz · Sep 15, 2017

Why would that be?

type MyType<'A> = with
    static member Show< ^B when ^B : (static member show : ^B  -> string) >(v: MyType< ^B >) = 
        match v with
        | MyType a -> sprintf "{MyType: %A}" (show a)

That should do the trick (disregarding that fact that the way to state this is really awful)

@Alxandr also this works out of the box today (F# 4.1) if the method is defined directly on the type (and not as an extension method in another module) and the type inferrer correctly infers that B needs to provide static member Show

    let inline show (a : ^A) = ( ^A : (static member Show : ^A -> string) a )

    type System.String with static member Show(a : System.String) = sprintf "{String: %A}" a

    type System.Boolean with static member Show(a : System.Boolean) = sprintf "{Boolean: %A}" a

    type Stop = 
        | Stop
        with
        static member Show(v: Stop) = "{Stop}"

    type MyType<'A> = 
        | MyType of 'A
        with
        static member inline Show(v: MyType< ^B >) = 
            match v with
            | MyType a -> sprintf "{MyType: %A}" (show a)

    let p = show (MyType Stop)
    let s = show (MyType (MyType Stop))
    let s = show (MyType (MyType "foo")) // error as extension methods are not picked up atm

If this was not type safe and you could misspell something the whole effort would be in vain, wouldn't it?

robkuz · Sep 15, 2017

@Alxandr also this works out of the box today (F# 4.1) if the method is defined directly on the type (and not as an extension method in another module) and the type inferrer correctly infers that B needs to provide static member Show

    let inline show (a : ^A) = ( ^A : (static member Show : ^A -> string) a )

    type System.String with static member Show(a : System.String) = sprintf "{String: %A}" a

    type System.Boolean with static member Show(a : System.Boolean) = sprintf "{Boolean: %A}" a

    type Stop = 
        | Stop
        with
        static member Show(v: Stop) = "{Stop}"

    type MyType<'A> = 
        | MyType of 'A
        with
        static member inline Show(v: MyType< ^B >) = 
            match v with
            | MyType a -> sprintf "{MyType: %A}" (show a)

    let p = show (MyType Stop)
    let s = show (MyType (MyType Stop))
    let s = show (MyType (MyType "foo")) // error as extension methods are not picked up atm

If this was not type safe and you could misspell something the whole effort would be in vain, wouldn't it?

Ahh, without the inline it doesn't compile. I admit I did not know about inline static members, learned something new today.

TobyShaw · Sep 15, 2017

Ahh, without the inline it doesn't compile. I admit I did not know about inline static members, learned something new today.

On phone, so I apologize for bad reply. You misunderstood me, @robkuz, or rather I wrote it in a bad way. The problem is that there is no good way to state that you want this static method to implement the Show protocol/trait/typeclass. This means it could be refactored away for instance without anyone being the wiser until you compile. And you get errors at callsites, rather than where you make the class.

Alxandr · Sep 16, 2017

On phone, so I apologize for bad reply. You misunderstood me, @robkuz, or rather I wrote it in a bad way. The problem is that there is no good way to state that you want this static method to implement the Show protocol/trait/typeclass. This means it could be refactored away for instance without anyone being the wiser until you compile. And you get errors at callsites, rather than where you make the class.

@Alxandr I agree, it would be nice if we could explictly state intention here and I agree in the absence of this the error messages at the call site will be pretty surprising especially for newbies.
However the stuff that @TobyShaw is working on is more to extend SRTPs to allow something type-classish.
My hope would be that real TCs will be much easier (and more feature rich) than this. But since its not clear when (or for that matter IF) TCs come I am happy to work with allowing extension methods to be picked up by constrained functions

robkuz · Sep 17, 2017

@Alxandr I agree, it would be nice if we could explictly state intention here and I agree in the absence of this the error messages at the call site will be pretty surprising especially for newbies.
However the stuff that @TobyShaw is working on is more to extend SRTPs to allow something type-classish.
My hope would be that real TCs will be much easier (and more feature rich) than this. But since its not clear when (or for that matter IF) TCs come I am happy to work with allowing extension methods to be picked up by constrained functions

@robkuz that I agree with :)

Alxandr · Sep 17, 2017

@robkuz that I agree with :)

I would like to see it in F#,
+inf

sighoya · Oct 14, 2017

I would like to see it in F#,
+inf

Just want to mention recent paper Familia: Unifying Interfaces, Type Classes, and Family Polymorphism - their ideas may be helpful.

radekm · Dec 4, 2017

Just want to mention recent paper Familia: Unifying Interfaces, Type Classes, and Family Polymorphism - their ideas may be helpful.

I've been doing some experiments using SRTP and "shapes" (more or less as defined by the C# proposal). The end result seems to be pretty decent, though you won't be able to encode monads ofc. I still need to figure out a good way to encode shapes that extend/implement other shapes, but besides from that this seems to be both working and producing fairly efficient code:

[<Struct>]
type Proxy<'t> = 
  member __.Type = typeof<'t>

module Proxy =
  let inline forType<'t> = Proxy<'t> ()
  let inline forInst<'t> (_: 't) = forType<'t>

module Read =

  type Shape<'t> =
    abstract member read: string -> 't

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member impl_Read: ^impl)> =
    (^t: (static member impl_Read: ^impl) ())
  
  let inline read s =
    shape.read s

module Show =
  
  type Shape<'t> =
    abstract member show: 't -> string

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member impl_Show: ^impl)> =
    (^t: (static member impl_Show: ^impl) ())
  
  let inline show t =
    shape.show t

module Identity =
  
  // TODO: Figure out how to make Identity require Read and Show := (Read, Show) => Identity
  type Shape<'t> =
    abstract member kind: Proxy<'t> -> string
  
  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member impl_Identity: ^impl)> =
    (^t: (static member impl_Identity: ^impl) ())
  
  let inline kind p =
    shape.kind p

module SomeModule =

  type Id =
    private
    | Id of string
  
    static member inline impl_Read = IdReadShape ()
    static member inline impl_Show = IdShowShape ()
    static member inline impl_Identity = IdIdentityShape ()

  and [<Struct>] IdReadShape =
    interface Read.Shape<Id> with
      member __.read s = Id s
  
  and [<Struct>] IdShowShape =
    interface Show.Shape<Id> with
      member __.show (Id s) = sprintf "Id \"%s\"" s
  
  and [<Struct>] IdIdentityShape =
    interface Identity.Shape<Id> with
      member __.kind _ = "id-kind"

[<EntryPoint>]
let main _ =
    let test : SomeModule.Id = Read.read "foo"
    let kind = Identity.kind (Proxy.forInst test)
    let str = Show.show test
    printfn "%s (%s)" str kind
    0

[Edit]

Actually, this seems to work for "inheritance":

  let inline shape< ^t, ^impl, ^read, ^show 
                              when ^impl : struct
                              and ^read : struct
                              and ^show : struct
                              and ^impl :> Shape< ^t> 
                              and ^read :> Read.Shape< ^t>
                              and ^show :> Show.Shape< ^t>
                              and ^t: (static member impl_Identity: ^impl)
                              and ^t: (static member impl_Read: ^read)
                              and ^t: (static member impl_Show: ^show)> =
    (^t: (static member impl_Identity: ^impl) ())

Alxandr · Mar 16, 2018

I've been doing some experiments using SRTP and "shapes" (more or less as defined by the C# proposal). The end result seems to be pretty decent, though you won't be able to encode monads ofc. I still need to figure out a good way to encode shapes that extend/implement other shapes, but besides from that this seems to be both working and producing fairly efficient code:

[<Struct>]
type Proxy<'t> = 
  member __.Type = typeof<'t>

module Proxy =
  let inline forType<'t> = Proxy<'t> ()
  let inline forInst<'t> (_: 't) = forType<'t>

module Read =

  type Shape<'t> =
    abstract member read: string -> 't

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member impl_Read: ^impl)> =
    (^t: (static member impl_Read: ^impl) ())
  
  let inline read s =
    shape.read s

module Show =
  
  type Shape<'t> =
    abstract member show: 't -> string

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member impl_Show: ^impl)> =
    (^t: (static member impl_Show: ^impl) ())
  
  let inline show t =
    shape.show t

module Identity =
  
  // TODO: Figure out how to make Identity require Read and Show := (Read, Show) => Identity
  type Shape<'t> =
    abstract member kind: Proxy<'t> -> string
  
  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member impl_Identity: ^impl)> =
    (^t: (static member impl_Identity: ^impl) ())
  
  let inline kind p =
    shape.kind p

module SomeModule =

  type Id =
    private
    | Id of string
  
    static member inline impl_Read = IdReadShape ()
    static member inline impl_Show = IdShowShape ()
    static member inline impl_Identity = IdIdentityShape ()

  and [<Struct>] IdReadShape =
    interface Read.Shape<Id> with
      member __.read s = Id s
  
  and [<Struct>] IdShowShape =
    interface Show.Shape<Id> with
      member __.show (Id s) = sprintf "Id \"%s\"" s
  
  and [<Struct>] IdIdentityShape =
    interface Identity.Shape<Id> with
      member __.kind _ = "id-kind"

[<EntryPoint>]
let main _ =
    let test : SomeModule.Id = Read.read "foo"
    let kind = Identity.kind (Proxy.forInst test)
    let str = Show.show test
    printfn "%s (%s)" str kind
    0

[Edit]

Actually, this seems to work for "inheritance":

  let inline shape< ^t, ^impl, ^read, ^show 
                              when ^impl : struct
                              and ^read : struct
                              and ^show : struct
                              and ^impl :> Shape< ^t> 
                              and ^read :> Read.Shape< ^t>
                              and ^show :> Show.Shape< ^t>
                              and ^t: (static member impl_Identity: ^impl)
                              and ^t: (static member impl_Read: ^read)
                              and ^t: (static member impl_Show: ^show)> =
    (^t: (static member impl_Identity: ^impl) ())

I tried doing the same using operators, but it seems F# doesn't like multiple SRTP constraints on a method group:

[<Struct>]
type Proxy<'t> = 
  member __.Type = typeof<'t>

module Proxy =
  let inline forType<'t> = Proxy<'t> ()
  let inline forInst<'t> (_: 't) = forType<'t>

module Read =
  type [<Struct>] Tag =
    static member name = "Read"

  type Shape<'t> =
    abstract member read: string -> 't

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member (~~): Tag -> ^impl)> =
    (^t: (static member (~~): Tag -> ^impl) (Tag ()))
  
  let inline read s =
    shape.read s

module Show =
  type [<Struct>] Tag =
    static member name = "Show"
  
  type Shape<'t> =
    abstract member show: 't -> string

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member (~~): Tag -> ^impl)> =
    (^t: (static member (~~): Tag -> ^impl) (Tag ()))
  
  let inline show t =
    shape.show t

module Identity =
  type [<Struct>] Tag =
    static member name = "Identity"

  type Shape<'t> =
    abstract member kind: Proxy<'t> -> string
  
  let inline shape< ^t, ^impl(*, ^read, ^show *)
                              when ^impl : struct
                              //and ^read : struct
                              //and ^show : struct
                              and ^impl :> Shape< ^t> 
                              //and ^read :> Read.Shape< ^t>
                              //and ^show :> Show.Shape< ^t>
                              and ^t: (static member (~~): Tag -> ^impl)
                              (*and ^t: (static member (~~): Read.Tag -> ^read)
                              and ^t: (static member (~~): Show.Tag -> ^show)*)> =
    (^t: (static member (~~): Tag -> ^impl) (Tag ()))
  
  let inline kind p =
    shape.kind p

module SomeModule =

  type Id =
    private
    | Id of string
  
    static member inline (~~) (_: Read.Tag) = IdReadShape ()
    static member inline (~~) (_: Show.Tag) = IdShowShape ()
    static member inline (~~) (_: Identity.Tag) = IdIdentityShape ()

  and [<Struct>] IdReadShape =
    interface Read.Shape<Id> with
      member __.read s = Id s
  
  and [<Struct>] IdShowShape =
    interface Show.Shape<Id> with
      member __.show (Id s) = sprintf "Id \"%s\"" s
  
  and [<Struct>] IdIdentityShape =
    interface Identity.Shape<Id> with
      member __.kind _ = "id-kind"

[<EntryPoint>]
let main _ =
    let test : SomeModule.Id = Read.read "foo"
    let kind = Identity.kind (Proxy.forInst test)
    let str = Show.show test
    printfn "%s (%s)" str kind
    0

So it seems it's either nice-er syntax or ability to define hierarchies for now... Also, the hierarchies will quickly stop working as you need to include all of the parents (transitively).

Alxandr · Mar 16, 2018

I tried doing the same using operators, but it seems F# doesn't like multiple SRTP constraints on a method group:

[<Struct>]
type Proxy<'t> = 
  member __.Type = typeof<'t>

module Proxy =
  let inline forType<'t> = Proxy<'t> ()
  let inline forInst<'t> (_: 't) = forType<'t>

module Read =
  type [<Struct>] Tag =
    static member name = "Read"

  type Shape<'t> =
    abstract member read: string -> 't

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member (~~): Tag -> ^impl)> =
    (^t: (static member (~~): Tag -> ^impl) (Tag ()))
  
  let inline read s =
    shape.read s

module Show =
  type [<Struct>] Tag =
    static member name = "Show"
  
  type Shape<'t> =
    abstract member show: 't -> string

  let inline shape< ^t, ^impl when ^impl :> Shape< ^t> 
                              and ^impl : struct
                              and ^t: (static member (~~): Tag -> ^impl)> =
    (^t: (static member (~~): Tag -> ^impl) (Tag ()))
  
  let inline show t =
    shape.show t

module Identity =
  type [<Struct>] Tag =
    static member name = "Identity"

  type Shape<'t> =
    abstract member kind: Proxy<'t> -> string
  
  let inline shape< ^t, ^impl(*, ^read, ^show *)
                              when ^impl : struct
                              //and ^read : struct
                              //and ^show : struct
                              and ^impl :> Shape< ^t> 
                              //and ^read :> Read.Shape< ^t>
                              //and ^show :> Show.Shape< ^t>
                              and ^t: (static member (~~): Tag -> ^impl)
                              (*and ^t: (static member (~~): Read.Tag -> ^read)
                              and ^t: (static member (~~): Show.Tag -> ^show)*)> =
    (^t: (static member (~~): Tag -> ^impl) (Tag ()))
  
  let inline kind p =
    shape.kind p

module SomeModule =

  type Id =
    private
    | Id of string
  
    static member inline (~~) (_: Read.Tag) = IdReadShape ()
    static member inline (~~) (_: Show.Tag) = IdShowShape ()
    static member inline (~~) (_: Identity.Tag) = IdIdentityShape ()

  and [<Struct>] IdReadShape =
    interface Read.Shape<Id> with
      member __.read s = Id s
  
  and [<Struct>] IdShowShape =
    interface Show.Shape<Id> with
      member __.show (Id s) = sprintf "Id \"%s\"" s
  
  and [<Struct>] IdIdentityShape =
    interface Identity.Shape<Id> with
      member __.kind _ = "id-kind"

[<EntryPoint>]
let main _ =
    let test : SomeModule.Id = Read.read "foo"
    let kind = Identity.kind (Proxy.forInst test)
    let str = Show.show test
    printfn "%s (%s)" str kind
    0

So it seems it's either nice-er syntax or ability to define hierarchies for now... Also, the hierarchies will quickly stop working as you need to include all of the parents (transitively).

Typeclass Traits proposal for Dotty
lampepfl/dotty#4153

gsomix · Apr 2, 2018

Typeclass Traits proposal for Dotty
lampepfl/dotty#4153

I'll focus in the next months on helping to get PR's merge ready which address problems and features for SRTP's.

realvictorprm · Apr 14, 2018

I'll focus in the next months on helping to get PR's merge ready which address problems and features for SRTP's.

It seems that interface default methods is coming to dotnet (note: clr runtime changes required):
dotnet/csharplang#52

Why it's important? It may help to support traits. Example: Scala traits are implemented as interface default methods:
scala/scala-dev#35

However if SRTP encoding is better, than that should be the default choice.

zpodlovics · May 12, 2018

It seems that interface default methods is coming to dotnet (note: clr runtime changes required):
dotnet/csharplang#52

Why it's important? It may help to support traits. Example: Scala traits are implemented as interface default methods:
scala/scala-dev#35

However if SRTP encoding is better, than that should be the default choice.

I just watched The F# Path To Relaxation talk given by @dsyme at NDC Oslo 2018 and type classes as well as HKT was mentioned as something we don't do in F# partly because of implementation issues and partly because of not having complete control of the .NET library-design.

Is this final? I would personally love to see these features make it into the language some day..

erbaman · Aug 7, 2018

I just watched The F# Path To Relaxation talk given by @dsyme at NDC Oslo 2018 and type classes as well as HKT was mentioned as something we don't do in F# partly because of implementation issues and partly because of not having complete control of the .NET library-design.

Is this final? I would personally love to see these features make it into the language some day..

baronfel added open old votes:300+ labels Oct 20, 2016

dsyme removed the open label Oct 29, 2016

dsyme referenced this issue Oct 29, 2016
Closed
Allow extension interfaces #182

dsyme added area: type constraints and removed area: type constraints labels Oct 29, 2016

dsyme changed the title from Support for type classes or implicits to Support type classes or implicits Oct 29, 2016

cloudRoutine referenced this issue Nov 16, 2016
Closed
Allow Getters and Setters for Primitive Types To Validate and Coerce Values #517
5 of 6 tasks complete

gusty referenced this issue Dec 22, 2016
Open
Slow compiler performance in Monad Transformers sample with Visual Studio, and can't give hints. #24

TobyShaw referenced this issue Sep 14, 2017
Open
[WIP, FS-1043] Extension members visible to trait constraints #3582
0 of 8 tasks complete

rmunn referenced this issue Nov 17, 2017
Open
infer module kind from its input #621

fsharp/fslang-suggestions

Join GitHub today

Support type classes or implicits #243

Comments

baronfel commented Oct 20, 2016 • edited by dsyme Edited 1 time dsyme edited Oct 29, 2016 (most recent)

baronfel added open old votes:300+ labels Oct 20, 2016

dsyme removed the open label Oct 29, 2016

dsyme referenced this issue Oct 29, 2016

dsyme added area: type constraints and removed area: type constraints labels Oct 29, 2016

dsyme changed the title from Support for type classes or implicits to Support type classes or implicits Oct 29, 2016

This comment has been minimized.

cloudRoutine commented Oct 30, 2016

This comment has been minimized.

dsyme commented Oct 31, 2016 • edited Edited 1 time dsyme edited Oct 31, 2016 (most recent)

This comment has been minimized.

cloudRoutine commented Nov 3, 2016

This comment has been minimized.

dsyme commented Nov 3, 2016 • edited Edited 1 time dsyme edited Nov 3, 2016 (most recent)

This comment has been minimized.

kurtschelfthout commented Nov 10, 2016

This comment has been minimized.

Rickasaurus commented Nov 10, 2016

This comment has been minimized.

Alxandr commented Nov 13, 2016

This comment has been minimized.

cloudRoutine commented Nov 13, 2016

This comment has been minimized.

dsyme commented Nov 14, 2016 • edited Edited 1 time dsyme edited Nov 14, 2016 (most recent)

This comment has been minimized.

Alxandr commented Nov 15, 2016

This comment has been minimized.

kurtschelfthout commented Nov 15, 2016 • edited Edited 1 time kurtschelfthout edited Nov 15, 2016 (most recent)

This comment has been minimized.

dsyme commented Nov 15, 2016

This comment has been minimized.

drvink commented Nov 15, 2016 • edited Edited 1 time drvink edited Jun 28, 2017 (most recent)

This comment has been minimized.

dsyme commented Nov 15, 2016 • edited Edited 1 time dsyme edited Nov 15, 2016 (most recent)

This comment has been minimized.

Rickasaurus commented Nov 16, 2016

cloudRoutine referenced this issue Nov 16, 2016

This comment has been minimized.

kurtschelfthout commented Nov 16, 2016

This comment has been minimized.

Alxandr commented Nov 16, 2016

This comment has been minimized.

Savelenko commented Nov 18, 2016 • edited Edited 1 time Savelenko edited Nov 18, 2016 (most recent)

This comment has been minimized.

yawaramin commented Nov 20, 2016

This comment has been minimized.

kurtschelfthout commented Nov 24, 2016 • edited Edited 1 time kurtschelfthout edited Nov 25, 2016 (most recent)

This comment has been minimized.

dsyme commented Nov 25, 2016

This comment has been minimized.

kurtschelfthout commented Nov 25, 2016

This comment has been minimized.

Alxandr commented Nov 25, 2016

This comment has been minimized.

Rickasaurus commented Nov 30, 2016 • edited Edited 1 time Rickasaurus edited Nov 30, 2016 (most recent)

This comment has been minimized.

Alxandr commented Nov 30, 2016

This comment has been minimized.

cloudRoutine commented Nov 30, 2016

This comment has been minimized.

gusty commented Dec 1, 2016 • edited Edited 1 time gusty edited Dec 22, 2016 (most recent)

This comment has been minimized.

radekm commented Dec 1, 2016

gusty referenced this issue Dec 22, 2016

This comment has been minimized.

tldrlol commented Jan 4, 2017

This comment has been minimized.

cloudRoutine commented Feb 24, 2017 • edited Edited 1 time cloudRoutine edited Feb 24, 2017 (most recent)

This comment has been minimized.

yawaramin commented Feb 25, 2017

This comment has been minimized.

kurtschelfthout commented May 28, 2017

This comment has been minimized.

robkuz commented May 29, 2017

This comment has been minimized.

Alxandr commented May 29, 2017

baronfel commented Oct 20, 2016 •

edited by dsyme

Edited 1 time

dsyme edited Oct 29, 2016 (most recent)

dsyme commented Oct 31, 2016 •

edited

Edited 1 time

dsyme edited Oct 31, 2016 (most recent)

dsyme commented Nov 3, 2016 •

edited

Edited 1 time

dsyme edited Nov 3, 2016 (most recent)

dsyme commented Nov 14, 2016 •

edited

Edited 1 time

dsyme edited Nov 14, 2016 (most recent)

kurtschelfthout commented Nov 15, 2016 •

edited

Edited 1 time

kurtschelfthout edited Nov 15, 2016 (most recent)

drvink commented Nov 15, 2016 •

edited

Edited 1 time

drvink edited Jun 28, 2017 (most recent)

dsyme commented Nov 15, 2016 •

edited

Edited 1 time

dsyme edited Nov 15, 2016 (most recent)

Savelenko commented Nov 18, 2016 •

edited

Edited 1 time

Savelenko edited Nov 18, 2016 (most recent)

kurtschelfthout commented Nov 24, 2016 •

edited

Edited 1 time

kurtschelfthout edited Nov 25, 2016 (most recent)

Rickasaurus commented Nov 30, 2016 •

edited

Edited 1 time

Rickasaurus edited Nov 30, 2016 (most recent)

gusty commented Dec 1, 2016 •

edited

Edited 1 time

gusty edited Dec 22, 2016 (most recent)

cloudRoutine commented Feb 24, 2017 •

edited

Edited 1 time

cloudRoutine edited Feb 24, 2017 (most recent)

MattWindsor91 commented Aug 7, 2017 •

edited

Edited 1 time

MattWindsor91 edited Aug 8, 2017 (most recent)

dsyme commented Aug 17, 2017 •

edited

Edited 1 time

dsyme edited Aug 17, 2017 (most recent)