Simulate higher-kinded polymorphism

[baronfel]

Submitted by Daniel Fabian on 3/21/2014 12:00:00 AM
492 votes on UserVoice prior to migration

F# already has to make trade-offs when doing interop, e.g. it is possible to create a null value for a DU from C#, erased type providers don't work from anywhere but F# etc. Maybe F# could allow for higher-kinded polymorphism within F# code and use dynamic casts at runtime or maybe statically resolved inlining to simulate higher-kinded polymorphism.

Original UserVoice Submission
Archived Uservoice Comments

[robkuz]

Problem Statement
As I have been asked repeatedly to provide some information on why HKTs would be so beneficial
please have a look at these blog posts

https://robkuz.github.io/Higher-kinded-types-in-fsharp-Intro-Part-I/
https://robkuz.github.io/HKTS-in-fsharp-part-III-Concept-Emulation/

and if you are interested also have a look to see Part II describing the solution in Haskell

https://robkuz.github.io/HKTS-in-fsharp-Part-II-A-Short-Visit-To-Haskell-Land/

Please read the blog post before you proceed

Now after reading you might conclude that

Discussion

• this can be done differently!
  and of course it can (it always can)
• this seems a bit heavy for just one type!
  Obviously this is just an example created out of a larger code base.
  In reality this is like some 5-10 types that need these workflow steps
  and these types for a tree of similar structure and by being that the
  whole lends itself very much to be processed generically.
  Having 5-10 types and 4 workflow steps would at the moment require me to
  recreate the 15-30 type definitions over and over again with little additional information.
  Plus there is the business concept of "workflow area" which the description above is just one (of 3 sofar).

So what could I do (except introducing some defunctionalized HKTs)? The only way I see
is to go full scale class based OO. Polymorphic methods and overloading all around.
The problem thou is that I loose immutablity and most likely partial application and easy composibilty.

What was the reason to go F#? For me most certainly NOT. Having a slightly nicer syntax around OO constructs and some better type inference than C# doesn't cut the mustard.

Now what can be done to improve my example? Assuming that HKTs will not come and assuming that nothing I have written will convince anybody who has not been convinced long time ago as there are much better papers about the ins and outs of HKTs (and I think that both assumptions are sensible).

Partial Solution
I think F# should include a feature like Haskells {-# LANGUAGE RankNTypes #-}.
Which means: “allow polymorphic functions as first class paramters”.
Haskell expresses this via function signatures similar to this one map :: forall f g. (forall a. f a -> g a) -> R f -> R g.

I think this addition/extension/change should be unproblematic as this is from my experience (and some SO question I have seen)
the assumed default anyways and people (me included) are often surprised that the type inferrer is already inferring types at
points where it should not yet-

The the following code

let createSafe (parent:obj) (prop:Lazy<'t>): 't = 
     if not <| isNull parent then prop.Force() else Unchecked.defaultof<'t>

type LineItem<'a> = 
with        
    member inline self.Imap(invoker, s:LineItem<'a>): LineItem<'b> =
        {
            articleID = invoker $ (createSafe s (lazy(s.articleID)))
            units =     invoker $ (createSafe s (lazy(s.units))) 
            amount =    invoker $ (createSafe s (lazy(s.amount))) 
        }

type ToFinish = ToFinish with 
    static member inline ($) (ToFinish, b) = toFinishedBrand b

let inline imap (invoker: ^I) (s:^S) : ^R = (^S: (member Imap: ^I -> ^S -> ^R) (s, invoker, s))

let inline toFinished li = imap ToFinish li

Is really really hard to understand.

• You have to attach a member function to your type
• you have to create an additional type and an associated member functions than somehow act as the wrapper around the function you want to execute
• you need to create a wrapper function using some scary generic type constraints

Whenever I do this I feel a bit like Dr. Strange mumbling some arcane magic spells. If there was a RankNTypes-feature the whole thing could
be condensed to this much cleaner functional design

let mapLineItem f li = {
        articleID = f (createSafe s (lazy(s.articleID)))
        units =     f (createSafe s (lazy(s.units))) 
        amount =    f (createSafe s (lazy(s.amount))) 
    }

mapLineItem toFinishedBrand someLineItemProgress

Expressing HKTs via type constraints(?)
Another additional feature could be to allow for some kind of lightweight HKTs by using generic type constraints.
At the moment I have I need to define multiple inj and prj function. for each process step I have

module INP =
    let inline inj (value: InProgress<'A>) : Brand<InProgress, 'A> = new Brand<_,_>(value)
    let inline prj (value: Brand<InProgress, 'A>) : InProgress<'A> = value.Apply() :?> _

module FIN =
    let inline inj (value: Finished<'A>) : Brand<Finished, 'A> = new Brand<_,_>(value)
    let inline prj (value: Brand<Finished, 'A>) : Finished<'A> = value.Apply() :?> _

It would be cool if this could be somehow expressed as

let inline inj<'A, 'T when 'T : HasGenericParamOf<'A>> (value: 'T) : Brand<Finished, 'A> = new Brand<_,_>(value)
let inline prj<'A, 'T when 'T : HasGenericParamOf<'A>> (value: Brand<Finished, 'A>) : 'T = value.Apply() :?> _

So enough of hopefully constructive input for today.
I guess it is time for another long twitter rant about HKTs ;-)

[jindraivanek]

Somehow I got preoccupied with idea of solving this with Traits (using experimental implementation from #243, so no HKT). Here is the result: https://gist.github.com/jindraivanek/ca09752df052d4f82b405f181f93f8b1.

Few notes:

• Traits allow us to avoid need for HKT function in mapLineItem
• Without HKT, I think it is impossible to do this without some variant of marker types and without some type unsafety (upcast from IBrand in my code).

[robkuz]

@jindraivanek looks interestingly!
I don't mind the type cast as long as it is confined. In my case it is in the inj and prj functions.
Have a look at my latest blog for how to type classify those.
I suspect if you type classify the Tag or the Kind types you should be able to write your transition Witnesses without any type casts

[jindraivanek]

@robkuz good writeup!
Inspired by your blog post, I was able define generic inj and prj functions. So, now type cast is not part of transition methods, and upcast is type safe, thanks to type constraints in prj.

You can see new version here: https://gist.github.com/jindraivanek/ca09752df052d4f82b405f181f93f8b1

I quite like this solution, I think it is a good example of power of traits even without HKT :)

[robkuz]

@jindraivanek
This is nice - I like te trick with the interface. Btw. would it be possible to do this also with a Tagging interface? Then you wouldn't need to implement member __.brand.

One drawback of your particular approach is however that you need to implement that interface which will not work if you dont have access to those types.

Here is another approach (also typeclassifying the Brands). It's partly back to the very original problem stated in my blog. However that problem arose more to the fact that you manually have to dispatch the inj/prj functions and not so much of writing them

type Brand<'tag, 'b>(value: obj) = 
    member this.Apply() : 'c = value :?> _

[<Trait>]
type IBrand<'Kind, 'Tag, 'a> =
    abstract inj: 'Kind -> Brand<'Tag, 'a> 
    abstract prj: Brand<'Tag, 'a> -> 'Kind

type Decision<'a> = Decision of 'a

type InProgress = class end
type Finished = class end
type Cancelled = class end

type InProgress<'a> = {value: 'a; decision: Decision<'a>}
type Finished<'a> = {value: 'a; initial: 'a; timestamp: DateTime}
type Cancelled<'a> = {value: 'a; decisions: list<Decision<'a>>; timestamp: DateTime; reason: string}

[<Witness>] 
type InProgressBrand<'a> =
    interface IBrand<InProgress<'a>, InProgress,'a> with
        member this.inj v = new Brand<_,_>(v)
        member this.prj v = v.Apply() 

[<Witness>] 
type FinishedBrand<'a> =
    interface IBrand<Finished<'a>,Finished, 'a> with
        member this.inj v = new Brand<_,_>(v)
        member this.prj v = v.Apply() 

[<Witness>] 
type CancelledBrand<'a> =
    interface IBrand<Cancelled<'a>, Cancelled,'a> with
        member this.inj v = new Brand<_,_>(v)
        member this.prj v = v.Apply() 

let inj x = x |> IBrand.inj
let prj x = x |> IBrand.prj

Could you try this one out (I cant get that branch running on my machine)?

It is slightly longer than yours yet still generic at the call site (or so I would expect)

[jindraivanek]

@robkuz Thanks :) Tagging interface works, I updated my code: https://gist.github.com/jindraivanek/ca09752df052d4f82b405f181f93f8b1 Thanks for pointing this out, I wasn't aware that write interface without member is possible. :)

Yes, this compile.
I was trying to combine it with Transition trait to have working example, but hits some errors. But maybe this error is bug in trait implementation (looks like compiler don't consider type annotation to find fitting solution in case of function that combine multiple traits). See comments near end of my code: https://gist.github.com/jindraivanek/e217d9352fa67f1adf9dedd441c45154

Btw. what's your problem with trait branch? I need to compile code using traits like this fsharp-traits/release/net40/bin/fsc.exe --noframework -r:fsharp-traits/release/net40/bin/FSharp.Core.dll TraitCode.fs.

[robkuz]

@jindraivanek cool. That looks nice.
I want to move your second example into the discussion about TCs if you dont mind

[sighoya]

If at some day higher kinded types will be supported in C# (Source: HKT), then F# should support higher kinded types due to interoperability, too

[Heimdell]

Why does it need CLR change, though?

[kspeakman]

So I finally came across a scenario where I think HKTs would be useful -- in MVU apps. Here is the comment I posted in the F# Slack.

I end up defining separate type trees for page models, page msgs, and page init args (aka routes). They are all the same basic structure with different data carried on the DU case, but I have to name the cases differently to avoid ambiguity. HomeModel of Home.Model vs HomeMsg of Home.Msg vs HomeInit of Home.InitArgs They rendevous in the main update function to call the appropriate page function. I think if there were HKTs, I could just call it Home of _ and plug in the type of the case later. I suppose this can be emulated somewhat by using type Scope<'t1, 't2, ...> | Home of 't1 | Page2 of 't2 | ... but this seems like a lot of pain that I am not willing to deal with.

Just for further detail, the main update statement ends up looking like this:

match model.Page, msg with
// top level messages
| _, Logout ->
    ...
| _, SwitchPage pageInit ->
    ...
// page specific
| HomeModel pageModel, HomeMsg pageMsg ->
    let pageModel, effects = Home.update pageMsg pageModel
    { model with Page = HomeModel pageModel }, effects

The main thing that HKTs would buy is not having to maintain 3 copies of the same structure, assuming they would work like I am thinking.

| Home pageModel, Home pageMsg ->
    ...

Maybe even opportunity to improve expressiveness.

match Scope.merge model.Page msg with
| Home (pageModel, pageMsg) ->
    ...

But I also wonder what tradeoffs this would imply. For example, to type inference.

[gusty]

Here's another real world situation that would require Higher Kinds #892 these are frequently asked questions. Some hacks are available but no clean way to do it without HKs.

[vzarytovskii]

Closing all probably not issues. This one is a bit more sensitive for many, so we shall wait and see where does CLR go with the extensions and unions.