CODEWITHSUNDEEP
scalarecursiontypes
Mika Prouk
Mika Prouk

Reputation: 515

How to define a certain recursive type in scala

Suppose I have a type A. How can I define a type B in scala which is either Unit or the tuple (A, B)?

I want to model a type B[A] which can be 

(), (A, ()), (A, (A, ())), (A, (A, (A, ()))), (..., (A, (A, (A, ())))).

I have seen things like 

trait B[A] extends (A, B) {}

or examples in

What does the `#` operator mean in Scala?

but was not able to work with what I found since the terminating Unit possibility is missing.

Thank you.

Upvotes: 0

Views: 1291

Answers (3)

Stephen
Stephen

Reputation: 4296

You need to use a sealed trait (alegbraic data type) to encode the possibility with type safety.

See how the HList from shapeless[1] does this..

sealed trait HList
sealed trait HNil extends HList
case object HNil extends HNil
case class ::[+H, +T <: HList](head: H, tail: T) extends HList

@ val xs = 1 :: 2.0 :: "three" :: HNil 
xs: Int :: Double :: String :: HNil = 1 :: 2.0 :: three :: HNil

When you say you need it to be either a tuple or a Unit, those are the cases that extend the sealed trait. Then you can use exhaustive pattern matching on them.

[1] https://github.com/milessabin/shapeless

Upvotes: 2

Dani
Dani

Reputation: 1022

How about the following (similar to how List is defined): 

trait NestedTuple[+A]

case class Tup[A](a: A, tail: NestedTuple[A]) extends NestedTuple[A]
case object End extends NestedTuple[Nothing]

val t1: NestedTuple[Int] = End      
t1: NestedTuple[Int] = End

val t2: NestedTuple[Int] = Tup(1, Tup(2, End)) 
t2: NestedTuple[Int] = Tup(1,Tup(2,End))

Upvotes: 6

simpadjo
simpadjo

Reputation: 4017

It looks like a Free Monad. You can take an implementation from scalaz library or cats.

Upvotes: -1

Related Questions