How to abstract over type kind?

Question

I implemented an TList that could collect any type H. But I've discovered that it could not contain higher order types H[_]. So I copypasted the entire thing and added [_] to respected places.

The though came to my mind. What if I would need to store H[_[_]], H[_[_,_]] or even H[_[_[_]]]. Should I just copy the code any time? Is there any way to abstract over type kindness?

think you're looking for this: https://underscore.io/blog/posts/2016/12/05/type-lambdas.html . Also could you show what you got so far? — pedromss, Sep 01 '17 at 19:08
Nothing special, like normal shapeless exercises. Type lambdas are bound to type kinds nevertheless. It allows to get kind of `*,* -> *` to `* -> *`¸ but it could not help to write code that accepts easily both `*`, `* -> *`, `* -> * -> *` — ayvango, Sep 01 '17 at 19:40
No but it would help writing the could that uses the types that take a certain number of types. What I'm saying is instead of duplicating the implementation change the way you use it. A snippet of you `TList` and a few examples of what you would like to achieve would help. — pedromss, Sep 01 '17 at 19:44
The code is highly cumbersome and indescriptive since I could not express it on type level due to: https://stackoverflow.com/questions/45767714/why-certain-type-projections-are-rejected-and-slightly-different-not is still unsolved. So I had about 400 LoC and I doubt that anyone would like to dig in it — ayvango, Sep 01 '17 at 19:58

score 1 · Accepted Answer · answered Sep 02 '17 at 15:13

In Scala there is no rank-2 polymorphism. It means methods (and moreover functions which are not even polymorphic at all) can't except arguments with universal quantifiers (all universal quantifications should be done on method level). So we can have methods like

def f[A, B[_], C[_[_]]](x: A, y: B[A], z: C[B]) = ???

but not like (pseudocode)

def f(x: [A] A, y: [A1, B[_]] B[A1], z: [B1[_], C[_[_]]] C[B1]) = ???

Also this means we can't substitute type constructor to the place where a specific type is expected (really, a type constructor B[_] can be considered as [A] B[A], C[_[_]]] as [B[_]] C[B] or [[A] B[A]] C[B]).

But to make types and type constructors look more uniformly you can wrap a type constructor with a trait type. For example you can look at the following encoding (it's surely wordy, you have to wrap-unwrap types all the time):

  trait Type

  trait ConcreteType extends Type {
    type T
  }

  trait TypeConstructor[U] extends Type {
    type l[X <: U] <: ConcreteType
  }

  type Type0 = ConcreteType
  type Type1 = TypeConstructor[Type0]
  type Type2 = TypeConstructor[Type1]
  type Type3 = TypeConstructor[Type2]

//  type A = Int

  type A = Type0 {type T = Int}

//  type B[X] = List[X]

  type B = Type1 {
    type l[X <: Type0] = Type0 {type T = List[X#T]}
  }

  trait Functor[F[_]]

//  type C[F[_]] = Functor[F]

  type C = Type2 {
    type l[F <: Type1] = Type0 {
      type T = Functor[
        ({
          type ll[X] = (F#l[Type0 {type T = X}])#T
        })#ll
        ]
    }
  }


  trait Generic[FF[_[_]]]   // like shapeless.Generic1, shapeless.IsHCons1, shapeless.IsCCons1
  // Generic1[F[_], FR[_[_]]], IsHCons1[L[_], FH[_[_]], FT[_[_]]], IsCCons1[L[_], FH[_[_]], FT[_[_]]]
  // Generic1[F, Functor], IsHCons1[L, Monad, Monad], IsCCons1[L, Applicative, Applicative]

//  type D[FF[_[_]]] = Generic[FF]

  type D = Type3 {
    type l[FF <: Type2] = Type0 {
      type T = Generic[
        ({
          type ll[F[_]] = (
            FF#l[Type1 {
              type l[X <: Type0] = Type0 {type T = F[X#T]}
            }]
            )#T
        })#ll
        ]
    }
  }

  import shapeless.{::, HNil}

  type lst = A :: B :: C :: D :: HNil

Some links:

https://wiki.haskell.org/Rank-N_types

https://en.wikibooks.org/wiki/Haskell/Polymorphism#Higher_rank_types

https://apocalisp.wordpress.com/2010/07/02/higher-rank-polymorphism-in-scala/

I become used to constructions like that: `[X, U[_ <: X], H[Y <: X] <: U[Y]]`. It looks really ugly, especially when it occurs twice in a row — ayvango, Sep 02 '17 at 15:34

How to abstract over type kind?

1 Answers1

Linked