Basic implementation of a List data structure in Scala

Question

I'm learning Scala and in a book that I'm reading (Functional Programming in Scala) I came across an example of a custom List implementation in Scala which goes like this:

sealed trait MyList[+A]
case object MyNil extends MyList[Nothing]
case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A]
object MyList {
  def apply[A](as: A*): MyList[A] =
    if (as.isEmpty) MyNil
    else Cons(as.head, apply(as. tail: _*))
}

I would like to extend MyList to add the following functionality:

add a tail method that returns all elements of a MyList instance without the first one, e.g. val x = MyList(1,2,3); x.tail == MyList(2,3).
Add a sum method that is only applicable when MyList contains Ints (or even better for all numeric types). So e.g. val x = MyList(1,2,3); x.sum == 6

The idea above 2 questions is to understand: (1) how to interact with the instance of my class and (2) how to use polymorphism in a situation like this. After some searching around, I'm not even sure how to begin with these problems, which is why I'm asking this question.

Any tips would be appreciated. Many thanks!

UPDATE:

A few updates:

First, I'd like to point out that the solution to the programming challenges in the Functional Programming course that I mentioned earlier can be found here, however, I'm looking for something a little different than what the author is asking for.

I've managed to find an answer to my first question "how can I use tail on my instance itself, e.g. MyList(1,2,3).tail?". To solve this, I had to modify the original trait in the following manner:

sealed trait MyList[+A] {
  def tail: MyList[A] = MyList.tail(this)
}

I'm not sure if this is the best way of doing what I want to do, but it works. If anyone has better suggestions, please let me know.

The second part is harder. I wanted to add the following inside the same trait:

def sum[Int]: MyList[Int] = MyList.sum(this)

But IntelliJ is complaining about the type of this which is A and I need to apply this conditionally on this being of type Int.

Another alternative is to do the following:

def sum: Int = this match {
    case x: MyList[Int] => MyList.sum(x)
 }

But what if we want to create another implementation for String that will also return a String? This cannot be the right solution and I haven't found one yet. Please help :)

Here is the solution. It would possibly benefit you more if you tried something and asked your question based on a specific problem in your implementation. A tip would be to try and do it using pattern matching. — jrook
– jrook, Commented Jan 31, 2020 at 21:02
Hey, thanks for the suggestion. Sorry, I know the question was a bit lazy. I'm travelling right now and I just didn't have the right amount of time to formulate it correctly. I've seen the file in the link you provided but it doesn't quite seem to work as I wished. The solutions are defined inside the companion object and when I import MyList elsewhere I cannot do something like val x = MyList(1,2); x.sum, I can only do that inside the companion object itself. — IVR
– IVR, Commented Feb 1, 2020 at 6:23

jwvh · Accepted Answer · 2020-02-10 08:26:48Z

.tail

I note that your Cons class already has a public tail member. I'd be tempted to start there and just make it universal...

sealed trait MyList[+A] {
  def tail: MyList[A]
}

...and add the MyNil implementation.

case object MyNil extends MyList[Nothing] {
  def tail: MyList[Nothing] = 
    throw new java.lang.UnsupportedOperationException("tail of empty list")
}

This is how the standard library List handles the tail of an empty list. Another, perhaps gentler, option would be to return this so that the tail of an empty MyList is just the empty MyList.

Leaving class Cons and object MyList unchanged, we get the expected results.

MyList('s','h','o','w').tail  //res0: MyList[Char] = Cons(h,Cons(o,Cons(w,MyNil)))
MyList(9).tail.tail           //java.lang.Unsupported...

.sum

This is a bit trickier. We want each .sum invocation to compile only if the elements are of a sum-able type, such as Int. The Scala way to achieve this to require that the call site provide implicit "evidence" that the element type is acceptable.

sealed trait MyList[+A] {
  def sum(implicit ev : A =:= Int) : Int  //can sum only if A is Int
}

Alas, this won't compile because MyList is covariant on A, but being the type of a passed parameter puts A in a contra-variant position.

Error: covariant type A occurs in invariant position in type A =:= Int of value ev

Fortunately there's a fix for that: use a different type parameter, related to A but not restricted to its covariant relationship.

sealed trait MyList[+A] {
  def sum[B >: A](implicit ev : B =:= Int) : Int = 0  //default behavior
}

case object MyNil extends MyList[Nothing] { ... //unchanged

case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
  override def sum[B >: A](implicit ev :B =:= Int) : Int = head + tail.sum[B]
}

object MyList { ... //unchanged

MyList(23,31,12).sum   //res0: Int = 66
MyList("as","is").sum  //won't compile

Numeric[A]

Well that works for Int, but it would be a pain to have to do the same for every sum-able type. Fortunately the standard library offers the Numeric typeclass which provides some basic values (zero and one) and operations (plus(), minus(), times(), etc.) for all the numeric types under its umbrella (Short, Long, Float, etc.).

So, putting it all together:

sealed trait MyList[+A] {
  val tail: MyList[A]
  def sum[B >: A](implicit ev : Numeric[B]): B = ev.zero
}

case object MyNil extends MyList[Nothing] {
  val tail: MyList[Nothing] = this
}

case class Cons[+A](head: A, tail: MyList[A]) extends MyList[A] {
  override def sum[B >: A](implicit ev : Numeric[B]): B = ev.plus(head, tail.sum[B])
}

object MyList {
  def apply[A](as: A*): MyList[A] =
    if (as.isEmpty) MyNil else Cons(as.head, apply(as.tail: _*))
}

This is an excellent post, thank you for such a detailed answer!

Collectives™ on Stack Overflow

Basic implementation of a List data structure in Scala

1 Answer 1

.tail

.sum

Numeric[A]

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

.tail

.sum

Numeric[A]

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related