Add support for higher-rank types #567
Comments
|
If this were to be implemented, it would be great to see support for existential types in addition to universal ones, since faithfully representing them using the encoding |
I'm not sure that the workaround is that much harder to read than the type-annotated version. And it requires no extra knowledge on the part of the programmer
We'll need more substantial examples than this. Also note the code may be much slower than passing in two functions. That's a major reason for not adding this feature. |
I think the type annotated version would look something like this: I haven't thought this through much but allowing type arguments on an argument expresses that the Compared to: Note the call site (the thing you write over and over again) is the most verbose. I claim it's pretty hard to see here that this is just the
For sure, this is the simplest possible example where it comes up.
Can you explain why? Seems like it's very comparable to passing in a closure and invoking it: one instantiation of the closure type vs one instantiation of the interface implementation + one method call for Invoke vs one method call for Invoke. |
Dispatch to a generic virtual method is generally slower - the original implementation used a hash table lookup - but the implementation details are subtle and it is possible that CLR "fast path" optimizations are good enough. Measure and see though (using the class encoding...) |
|
@dsyme I'm not sure I understand why the performance matters - if someone needs higher rank types then they're going to pay that penalty whether they implement them by hand or if the compiler uses some more pleasant sugar to do it for them. And while it's not a constant occurrence, people do need higher rank types at times, the .NET platform already supports them (in the form of types with generic methods), and implementing them by hand is as awkward as explicitly implementing |
|
@kbattocchi Two examples. For this:
we have an alternative today, which is to pass in "f" twice, e.g. and then duplicate "f" at the callsite. That doesn't work in general of course. But I do know its performance doesn't use any generic virtual dispatch. Likewise it matters because people will inevitably use the feature when not needed, e.g. where "f" is only instantiated at one type. So they pay a performance cost for nothing. |
|
@dsyme I doubt that there would be too many people using the feature unnecessarily because type inference still wouldn't infer higher rank types (since there's no single most general type to infer), so it would require the user to opt-in by writing an annotation. Also, your alternative allows users to pass in any two functions, even if they are not actually different instantiations of a single higher-rank function, which makes it easier for a caller to use the function incorrectly. (Technically since .NET allows runtime type tests of the generic parameter it's always possible to build a higher-rank function with the same behavior, but it would be very unnatural). Finally, there is some overhead to using a generic interface, but I can still make a tens of millions of calls a second. |
|
Few more substantial examples: And here's a post about encoding existential types, tangentially related: https://stackoverflow.com/questions/16284680/expressing-existential-types-in-f |
|
I wonder if it would be a better idea if instead of allowing rank-n types, it would instead be allowed to convert functions to single-method interface types, a bit reminiscent of function to delegate conversion. The simple example would then become: Pros:
Cons:
|
|
Hey @kurtschelfthout, great writeup. I'd like to add my perspective to that On Readability and Comprehension
I would be pretty surprised if any developer would think that a definition like As for the knowledge part: It took me almost a year before I really grokked that I can (or rather must) express such a function as a wrapped invokable type. For me this was totally counter-intuitive. Somehow like Java before Java 8 and Lambdas. Even in Haskell I was totally stunned that I have to enable a language extension to make this happen. I think most novices would simply expect that this works. At least that was my expectation. Performance
I'd like to add: Why nor let the developer decide if there is any performance issue at all? Whoever uses it should first measure if the code under review has any performance issues and
I must admit I use it relatively often - probably one of the aspects that I try to write my code pretty generic and then polymorphic function params come pretty handy. Alternative [<CallableAsFunction>] //not sure this is necessary, strictly speaking
type PassThrough =
abstract Invoke<'a> : 'a -> 'a
let g (f:PassThrough) (x:'b,y:'c) : 'b * 'c = (f x, f y) //under the hood: f.Invoke x
let pair = g id (1, '2') // under the hood: anonymous interface implementationConcerning the alternative to the first proposal [<CallableAsFunction>]
type PassThrough<'a> = 'a -> 'a
let g (f:PassThrough) (x:'b,y:'c) : 'b * 'c = (f x, f y) //under the hood: f.Invoke x
let pair = g id (1, '2') // under the hood: anonymous interface implementationor why not adorn a function itself let g ([<PolymorphicFnParam>] f:'a -> 'a) (x:'b,y:'c) : 'b * 'c = (f x, f y)
let pair = g id (1, '2') // under the hood: anonymous interface implementationor we could extend this feature request ("Allow for Structural Checking of Generic Parameters within Type Constraints")[https://github.com//issues/566] and express it like this let g<'f, 'a where 'f: isPolymorphicFun<'a -> 'a> (f:'f) (x:'b,y:'c) : 'b * 'c = (f x, f y)
let pair = g id (1, '2') // under the hood: anonymous interface implementationI don't know if this last is a good idea thou. Btw. I'd be willing to help testing or to fund this request |
Because you really need two places to put parameters (and maybe constraints on): the interface and the interface method. Take the other possibility mentioned in the very simple example: type ConvertAll<'b> =
abstract Invoke<'a> : 'a -> 'b
let g (f:ConvertAll<_>) (x,y) = (f x, f y)
let pair = g (fun _ -> 1) ("test", true)Also I'd expect in quite a few cases that the interface type MyAbbrev<'b> = (f<'a>:'a -> 'a) -> 'bGenerally you should be able to write a type like this (in pseudo notation): forall a. a -> (forall b when b :> IMyInterface. b -> (forall c when c : equality. c -> a)))everywhere you can currently write types (signature files, type annotations, type abbreviations). Naming the interface type neatly removes that problem without introducing any additional syntax. The |
|
Thanks for the explanation. What would happen if we'd assume that alle parameters of the given function are polymorphic and have a universal quantification so that your could be expressed like this would that be a problem? |
Yes. You need to allow the programmer to be in control of how each type parameter is quantified. It's not either all on the outermost level (the current behaviour) or each subsequent parameter in a new scope (your suggestion). For example, how would you write the |
|
@kurtschelfthout I am not sure I agree (or understand for that matter ;-)) Let' say we have your converter function (and for a moment disregard any other constraints) which in then should expand to something like this and lets assume that we had a call site like this and lets further assume that the implementation of |
|
Just to add another use case in TypeShape - the slides on it have a lengthy interlude on rank-2 and existential types: https://eiriktsarpalis.github.io/typeshape/#/18. This plays an important role in how the library works. For example, instead of writing: | Shape.FSharpList s ->
s.Accept {
new IFSharpListVisitor<'T -> string> with
member __.Visit<'a> () =
let tp = mkPrinter<'a>()
wrap(fun ts -> ts |> List.map tp |> String.concat "; " |> sprintf "[%s]")
}Users could write perhaps: | Shape.FSharpList s ->
s.Accept (fun<'a> () ->
let tp = mkPrinter<'a>()
wrap(fun ts -> ts |> List.map tp |> String.concat "; " |> sprintf "[%s]")If you know about existential "packs" they are relatively common. E.g. here is an |
|
@kurtschelfthout Thanks. I'm still not entirely convinced that the explicit encoding is a bad thing though - at least it shouts out to me "here's an existential pack/unpack!" (though you have to know the encoding to be able to read it in those terms) |
Therein lies the rub, I think. I for one can't understand how the existential encoding works without writing it in a shorter, typed form and then deriving the interface-based encoding from that. I would have trouble recognising what it is when encoded via multiple generic interfaces. Half the slides of TypeShape talk about how/why this encoding is useful and necessary, so I don't think I'm an outlier. The simple rank 2 encoding with anonymous interface implementation is more easily understandable of course. But then not many language features have acceptable cost/benefit when applied to the simplest possible example. The main benefit I see with a feature like this is that intent of the code and documentation (of say, a library like TypeShape) is significantly improved. I do agree the feature is kind of niche - expected in F# at this point, most of the "obvious" features are there. On the other hand it doesn't get particularly in the way either, you can practically ignore it until you encounter it in a library signature somewhere. |
|
This might be relavant for the discussion. Polymorphism in OCaml 4.0.6 |
|
If you have a GADT query or request/response DSL, rank-2 types can be very helpful in reducing meaningless code duplication and boilerplate. As a follow-on to the Haskell GADT example I gave on issue #179, here is an example of how you would use that in another part of your DSL: Again, this is in Haskell, rather than inventing a syntax for F#. This particular thing I have not figured out an encoding for in F# that would work for me, but since the ways that I've been able to encode GADTs have been unsatisfying anyway, I use the workaround I describe in my comment on that issue. Here is, then, how you would use this in your interpreter or runtime for your DSL: As you can see, your overall type signature is generic, but each particular case you match on has the type refined to something more specific. |
|
A use-case for higher rank types I just stumbled across. I have the following: open System
type ValidationResult<'r> = Result<'r, string list>
type SinglePropValidationResult<'property> = Result<'property, string>
type PropValidatorFns<'property> = ('property -> SinglePropValidationResult<'property>) list
type PropMap<'object, 'property> = 'object -> 'property
type ObjValidator<'object, 'property> = (PropMap<'object, 'property> * PropValidatorFns<'property>) list
module Validation =
let stateIsValid (state: State) =
match Constants.StatesOfAustralia.Contains(state.Value) with
| true -> Ok state
| false -> Error "Given state is not a known US state."
let pipeObjectThroughValidation
(validators: ObjValidator<'object, forall. 'property>)
(input: 'object): ValidationResult<'object> =
let errorList =
validators
|> List.collect
(fun (mapper, validatorList) ->
let property = mapper input
validatorList |> List.map (fun v -> v property))
|> List.choose (function
| Error msg -> Some msg
| Ok _ -> None)
if not errorList.IsEmpty then
Error errorList
else
Ok inputThe Here, the property could be of different type in an object (records, tuples, or anything). And would like to use it as let person = { firstname = "jake"; age = 1000 }
pipeObjectThroughValidation [ (_.firstname, [validateName; validateSthElse]); (_.age, validateAgeRequireMents)] |
|
Using the interface trick prevents our function to use F# constraints. Take the following example: this works if we pass a function like but if we pass something like And we can't add the static constraint required for Now and the constraint disappears as it is resolved at compile time. If we use the trick of the static Invoker we don't have that limitation but it generates lot of constraints because it delays overload resolution, forcing our So, none of the 2 existing workarounds are good enough. We do need to add this functionality, there's no other way. |
|
Higher-rank types of this kind won't be added to F#. The encoding using a generic interface method is adequate for nearly all use-cases, and superior from some perspectives (e.g. can be more explicit and readable). |
|
If the decision is to keep the existing encodings at least if we had #1085 we could turn this: into this And also into If the invokable as static member is also implemented. |
Add support for higher-rank types
We propose to add support for higher-rank types, originally suggested by @polytypic, see https://twitter.com/VesaKarvonen/status/846239603627569152. This suggestion draws heavily on comments made in that thread by Vesa and @kbattocchi .
The existing way of approaching this problem in F# is to manually create an interface type with a single method to represent an argument with a type like (forall 'a. 'a -> 'a) and anonymously implement the interface on usage, for example http://stackoverflow.com/questions/7213599/generic-higher-order-function/7221589#7221589
Alternatively, that SO question also shows some SRTP/operator overloading magic that can be used to address the problem.
Pros and Cons
The advantages of making this adjustment to F# are that
let g f (x,y) = (f x, f y)is unlikely to work as intended; also, the problem only shows up at the call site:g id ( 1, '2')The disadvantages of making this adjustment to F# are that
Extra information
Estimated cost (XS, S, M, L, XL, XXL): Err. L?
Related suggestions: NOT to be confused with #175 this is not about higher kind but higher rank (non-prenex) polymorphism.
Affadavit (must be submitted)
Please tick this by placing a cross in the box:
Please tick all that apply:
The text was updated successfully, but these errors were encountered: