CODEWITHSUNDEEP
scalatypes
alf
alf

Reputation: 8513

Recursive type definition in Scala

Suppose I have this code in Haskell and I want to try to come up with something like it in Scala:

data CatList q a = E | C a (q (CatList q a))

instance Queue q => CatenableList (CatList q) where
   -- methods

Note that CatList is either empty, or is an element plus a queue (as defined by a typeclass q) of CatLists. In Scala, I'm trying to do something like 

sealed trait CatList[+Q, +E]

object Empty extends CatList[Nothing, Nothing]

case class C[Q[_], E](x: E, q: Q[CatList[Q, E]]) extends CatList[Q[???], E]

but the problem is, Q[_] takes parameters, so I need to provide something in the extends clause, which leads to CatList[Q[CatList[Q[???], E], E] which is confusing.

I can try a Haskell approach, saying that Q[_] is nothing but a type, and go with 

sealed trait CatList[+Q[_], +E]

object Empty extends CatList[Nothing, Nothing]

case class C[Q[_], E](x: E, q: Q[_]) extends CatList[Q[_], E]

but that fails with

Error:(16, 56) Q[_] takes no type parameters, expected: one
  case class C[Q[_], E](x: E, q: Q[_]) extends CatList[Q[_], E]
                                                       ^

So the question is, is there a way to get around that?

Upvotes: 2

Views: 736

Answers (1)

Alexey Romanov
Alexey Romanov

Reputation: 170735

You need

sealed trait CatList[+Q[_], +E]

object Empty extends CatList[Nothing, Nothing]

case class C[+Q[_], +E](x: E, q: Q[CatList[Q, E]]) extends CatList[Q, E]

[_] has different meanings in type parameter declaration like trait CatList[+Q[_], +E] ("Q is a type constructor") and in use like extends CatList[Q[_], E] ("Q with some unknown parameter").

Upvotes: 3

Related Questions