Is there such thing like "rigid type" in F#?

Question

In Haskell type class can introduce "interface" where you have some "free" type parameters, something like "for all a: instances support this set of functions". And if you instantiate such type-class, you can not narrow this a type, otherwise you get error about rigid type a (like "for all, but now become more narrow, which breaks original type promise to be for all"). OK, I implemented IEnumerable interface in my F# type (class):

    interface System.Collections.Generic.IEnumerable<byte> with
        member __.GetEnumerator () = (__.GetBytes ()).GetEnumerator ()

and this is compiling, works as I expected, all is fine. But here I made more narrow interface: IEnumerable<byte> instead of IEnumerable<'Any>. So, what is type parameter in IEnumerable? You can implement more specific, narrow interface, right? It's not like "forall" in Haskell, or?

Are you asking whether this is possible in F# in general, or specifically in case where your implementation calls `GetBytes()`, which presumably returns a collection of bytes? If it's the former case, I can write an answer with some details, but in case of the latter nothing other than fixing the type parameter to `byte` would type check, even in Haskell I believe — Honza Brestan, Jan 20 '18 at 10:09
I will be grateful for the answer for both cases: my learning of F# is in progress, so my question is wide and theoretical — RandomB, Jan 20 '18 at 10:13

score 4 · Answer 1 · answered Jan 20 '18 at 11:00

In your example, the outer GetEnumerator() implementation calls __.GetBytes(), which I would expect to have a type unit -> IEnumerable<byte> and that fixes the generic type parameter to be a byte as well. If you were able to say your type implements IEnumerable<'Any>, what should be the program behavior if I wanted 'Any to be let's say a bool, but it still gave me a collection of bytes? Programs like that don't type check in F#, because the language specification wants the programmer to make all such conversions explicitly to make sure it is meaningful for their program.

If you want to specify an open generic interface implementation, it's definitely possible (and common). You can have your type implement a generic interface like IEnumerable<'Any>, but the type parameter 'Any has to be specified on the type level. So you cannot write this

type MyEnumerable () =
    interface IEnumerable<'Any> with ...

but you can do it if you declare the type parameter on the type itself in addition to the interface:

type MyEnumerable<'Any> () =
    interface IEnumerable<'Any> with ...

This is mainly due to F#'s origin in .NET where interfaces existed before generics and are closely tied to how the runtime works with types, but having the type disconnected from type parameters in its interface implementation would often not make sense anyway as such interface could only have very limited capability, or would do things not related to the type itself, which would most likely be a bad design anyway.

Now if I get back to your example, you can try adding the 'Any type parameter to the interface and the type it's implementing it, but the compiler will give you errors due to the reasons in the first paragraph. So you have to decide whether the type itself really is generic, an in that case the GetEnumerator implementation should change, or whether it really only implements an "enumerable of bytes", in which case your original code is correct and cannot be more generalized.

Your example with `'Any` in type declaration and then in interface, looks like introducing of type parameter and "propagating" it with `ScopedTypeVariables` extension in Haskell. Possibility to make more specific implementation (more narrow) in this case looks different from Haskell, but may be I don't see right analogue. — RandomB, Jan 20 '18 at 11:11

Fyodor Soikin · Accepted Answer · 2018-01-20T15:31:11.213

Your code snippet is analogous to Haskell instance, not Haskell class. This code snippet says that the surrounding type is an instance of IEnumerable<byte> which would be analogous to something like instance IEnumerable T Byte in Haskell (where T is the type in which you implemented IEnumerable).

I guess the key insight here is that IEnumerable must be seen as a multiparam type class, with one parameter denoting the type that is the sequence, and the other parameter denoting the element of the sequence.

In F# the first parameter is implicit - it's not mentioned directly on the interface declaration, but every interface has it - it's the type on which the interface is implemented.

// F#
type MyType = MyType with
    interface IEnumerable<byte> with
        member this.GetEnumerator() = xyz


-- Haskell
class IEnumerable t e where
    getEnumerator :: t -> [e]

data MyType = MyType

instance IEnumerable MyType Byte where
    getEnumerator t = xyz

Here, it's easy to see that both t and e would in fact be "rigid" types. The multiparam-ness reflects the fact that the same type t may have multiple IEnumerable implementations for different e, same way you can implement multiple concrete IEnumerable<e> on a type in F#.

The one thing that F# cannot do (as such) is provide an implementation for any e, like this:

instance IEnumerable MyType e where
    getEnumerator t = ...

To achieve a similar (though not identical) effect in F#, one would create another interface and implement it:

type AnyEnumerable =
    abstract member AnyEnumerate<'a>() : IEnumerable<'a>

type MyType = MyType with
    interface AnyEnumerable with
        member this.AnyEnumerate<'a>() = 
            { new IEnumerable<'a> with
                  member this.GetEnumerator() = ... }

let x = MyType.AnyEnumerate<int>()
let y = MyType.AnyEnumerate<string>()

Exactly: multiparam typeclass! This is the closest analogue. — RandomB, Jan 20 '18 at 16:06

Is there such thing like "rigid type" in F#?

2 Answers2