Scala: Higher-kinded type as a type parameter

Question

Please consider the following code snippet (it demonstrates a simplified version of my actual problem):

trait Id[Type[_]] {
  def id[S]: S => Type[S]
}

trait IdTransformer[Type[_]] {
  type Result[_]  // depends of Type
  def idTransform[P]: P => Result[P]
  def composeWith[Other[_]](other: Id[Other]) = new Id[Result[Other]] { def id[S] = x => idTransform(other.id(x)) }
}

// instance example
class OptionIdTransformer extends IdTransformer[Option] {
  type Result = Option[_]
  def idTransform[S] = x => Some(x)
}

There I have Id trait defines a function that wraps a value into a type and IdTransformer trait defines a way to add new logic to id operations. I want to use them in way like

Transformer1.composeWith(Transformer2.composeWith(...(idInstance)))

But when I compile the code, I get error messages

type Other takes type parameters

and

IdTransformer.this.Result[<error>] takes no type parameters, expected: one 

in method composeWith, although Result[Other] should be a higher-kinded type and should take a single type parameter.

Please explain what is the reason of the errors and whether is there a workaround.

Answer 1

You are trying to compose a higher-kinded type with two other hihgher-kinded types. What is needed for that a trick called type lambda.

trait IdTransformer[Type[_]] {
  type Result[_]  // depends of Type
  def idTransform[P]: P => Result[P]
  def composeWith[Other[_]](other: Id[Other]) = new Id[({type λ[α] = Result[Other[α]]})#λ] { def id[S] = x => idTransform(other.id(x)) }
}