Scala List object methods implementation

Question

I need to implement my own List class in Scala. I've implemented:

trait List[+A] {
  /** The first element */
  def head: A
  /** The rest of the elements */
  def tail: List[A]

  def map[B](f: A => B): List[B]
  def flatMap[B](f: A => List[B]): List[B]
  def filter(f: A => Boolean): List[A]

  // Concatenate two lists
  def concat[B >: A](that: List[B]): List[B] = this match {
    case Empty => that
    case NonEmpty(head, tail) => NonEmpty(head, tail concat that)
  }
}

/** The empty list, also known as Nil */
case object Empty extends List[Nothing] {
  def head = throw new UnsupportedOperationException("Empty.head")
  def tail = throw new UnsupportedOperationException("Empty.tail")

  def map[B](f: Nothing => B): List[B] = Empty
  def flatMap[B](f: Nothing => List[B]): List[B] = Empty
  def filter(f: Nothing => Boolean): List[Nothing] = Empty

  override def toString = "Empty"
}

And now I need to implement filter, flatMap and Map methods:

case class NonEmpty[A](head: A, tail: List[A]) extends List[A] {


    //def map[B](f: A => B): List[B] = ???
      //def flatMap[B](f: A => List[B]): List[B] = ???
      def filter(predicate: A => Boolean): List[A] = {        
      }

For instance method filter(predicate: A => Boolean): List[A] how can I iterate through every element in this list? How can I check if given predicate is true or false? (tried if(predicate(head)) - doesn't work for some reason.) Thank you for help.

It looks like an homework, maybe you could tell us what you've tried and whre your stuck more precisely. — Nicolas
– Nicolas, Commented Nov 9, 2012 at 14:30

kiritsuku · Accepted Answer · 2012-11-09 14:37:16Z

3

You need to traverse the elements with head and tail:

def filter(f: A => Boolean): List[A] = {
  def loop(xs: List[A], ys: List[A]): List[A] =
    if (xs == Empty) ys else loop(xs.tail, if (f(xs.head)) NonEmpty(xs.head, ys) else ys)
  loop(this, Empty).reverse
}

This implementation can be defined in List. The last thing you need for this is the reverse method. You can implement it the same way as filter - use an inner method to traverse all elements.

Instead of reverse you can use a non-tail-recursive implementation, which must not reversed and can be implemented in the subclasses:

def filter(f: A => Boolean): List[A] =
  if (f(head)) NonEmpty(head, tail filter f)
  else tail filter f

The other methods can be defined in a similar way.

edited Nov 9, 2012 at 14:37

answered Nov 9, 2012 at 14:24

kiritsuku

53.4k19 gold badges118 silver badges136 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ricardo Simmus Over a year ago

thanx for your help, I didn't know about NonEmpty(head, tail filter f)

phant0m Over a year ago

@RicardoSimmus How do you mean, you "didn't know"?

phant0m · Accepted Answer · 2012-11-09 14:32:24Z

1

Often, recursion gets easier when you just live in Fairyland and pretend (almost) everything already works.

Suppose filter already did what you asked, how would you use filter to make it work for yet another element?

Well, you can decide whether you want to to include the first element of your list (depending on f), and let filter, "which already works", handle the rest. Then just concatenate the list.

def filter(f: A => Boolean) : List[A] = {
  if (f(head)) NonEmpty(head, tail.filter(f))
  else tail.filter(f)
}

answered Nov 9, 2012 at 14:32

phant0m

17k6 gold badges52 silver badges84 bronze badges

Collectives™ on Stack Overflow

Scala List object methods implementation

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related