## Functional programming in Scala, Chapter 3, List implementation

Doing the exercise in chapter 3. Finished implementing the List class.

object Example {
sealed trait List[+A] {
def head: A = this match {
case Nil => throw new NoSuchElementException
case Cons(x, _) => x
}
def tail: List[A] = this match {
case Nil => throw new NoSuchElementException
case Cons(_, x) => x
}
def setHead[B >: A](x: B): List[B] = this match {
case Nil => Nil
case Cons(y1, ys) => Cons(x, ys)
}
@annotation.tailrec
final def drop(n: Int): List[A] = {
require(n >= 0)
this match {
case Nil => Nil
case ys@Cons(x, xs) => n match {
case 0 => ys
case _ => xs.drop(n - 1)
}
}
}
@annotation.tailrec
private final def takeHelper[B >: A](n: Int, list: List[B], acc: List[B]): (List[B], List[B]) = list match {
case Nil => (list, acc)
case Cons(x, xs) => n match {
case 0 => (list, acc)
case _ => takeHelper(n - 1, xs, acc ++ List(x))
}
}
@annotation.tailrec
private final def takeWhileHelper[B >: A](f: B => Boolean, list: List[B], acc: List[B]): (List[B], List[B]) = list match {
case Nil => (list, acc)
case Cons(x, xs) => f(x) match {
case false => (list, acc)
case true => takeWhileHelper(f, xs, acc ++ List(x))
}
}
def take(n: Int): List[A] = {
require(n >= 0)
val (_, acc) = takeHelper(n, this, Nil: List[A])
acc
}
def takeWhile(f: A => Boolean): List[A] = {
val (_, acc) = takeWhileHelper(f, this, Nil)
acc
}
@annotation.tailrec
final def dropWhile(f: A => Boolean): List[A] = this match {
case Nil => Nil
case ys@Cons(x, xs) => if(f(x)) xs.dropWhile(f) else ys
}
// naive implementation of foldRight
//    def foldRight[B](z: B)(f: (A, B) => B): B = this match {
//      case Nil => z
//      case Cons(x, xs) => f(x, xs.foldRight(z)(f))
//    }
@annotation.tailrec
final def foldLeft[B](z: B)(f: (B, A) => B): B = this match {
case Nil => z
case Cons(x, xs) => xs.foldLeft(f(z, x))(f)
}
// foldRight via foldLeft
def foldRight[B](z: B)(f: (A, B) => B): B = {
foldLeft((x: B) => x)((g, a) => {b => g(f(a, b))})(z)
}
def reduceLeft[B >: A](f: (B, B) => B): B = {
}
def reduceRight[B >: A](f: (B, B) => B): B = {
}
def map[B](f: A => B): List[B] = foldRight(Nil: List[B])((x, xs) => Cons(f(x), xs))
def filter[B >: A](f: B => Boolean) = foldRight(Nil: List[B])((x, xs) => {
if(f(x)) Cons(x, xs)
else xs
})
def filter1[B >: A](f: B => Boolean) = {
flatMap(x => {
if(f(x)) List(x)
else Nil
})
}
// potential stackoverflow error
def zip[B](other: List[B]): List[(A, B)] = {
(this, other) match {
case (Nil, _) => Nil
case (_, Nil) => Nil
case (Cons(x, xs), Cons(y, ys)) => Cons((x, y), xs.zip(ys))
}
}
def zipWith[B, C](other: List[B], f: (A, B) => C): List[C] = {
this.zip(other).map(x => f(x._1, x._2))
}
def forall(f: A => Boolean): Boolean = {
val satisfied = takeWhile(f)
if(satisfied.length == length) true else false
}
def exists(f: A => Boolean): Boolean = {
val dropped = dropWhile(f)
if(dropped.length == length) false else true
}
def hasSubsequence[B >: A](list: List[B]): Boolean = (this, list) match {
case (Nil, Nil) => true
case (Nil, _) => false
case (_, Nil) => true
case (list1@Cons(x, xs), list2@Cons(y, ys)) => {
if(x == y) xs.hasSubsequence(ys)
else xs.hasSubsequence(list2)
}
}
def flatMap[B](f: A => List[B]): List[B] = List.concatenate(this.map(f))
def length: Int = foldLeft(0)((x, _) => x + 1)
def reverse: List[A] = foldLeft(Nil: List[A])((xs, x) => Cons(x, xs))
def append[B >: A](a: B): List[B] = foldRight(List(a))(Cons(_, _))
def ++[B >: A](other: List[B]): List[B] = {
foldRight(other)((x, xs) => Cons(x, xs))
}
def mkString(sep: String, start: String, end: String) = {
val middle = foldLeft("")((string, x) => {
string match {
case "" => x.toString
case _ => string + sep + x.toString
}
})
start + middle + end
}
override def toString = mkString(", ", "List(", ")")
}
case object Nil extends List[Nothing]
case class Cons[+A](h: A, t: List[A]) extends List[A]
object List {
implicit val init = Nil
def apply[A](as: A*): List[A] = {
if(as.isEmpty) Nil
else Cons(as.head, apply(as.tail: _*)) // the _* type annotation allows us to pass a Seq to a variadic method
}
def concatenate[A](as: List[A]*): List[A] = {
as.reduceLeft(_ ++ _)
}
def concatenate[A](as: List[List[A]]): List[A] = {
as.reduceLeft(_ ++ _)
}
}
}

object Test {
import Example._
val l1 = List[Int](1, 2, 3, 4)
//  l1.tail
//  l1.drop(2)
//  l1.dropWhile(_ < 3)
//  l1.foldLeft[Int](0)(_ + _) // compute sum
//  l1.foldRight(0)(_ + _) // compute sum
//  l1.foldRight[List[Int]](MNil)(Cons[Int](_, _)) // returns the same list
//  l1.foldLeft[List[Int]](MNil)((xs, x) => Cons[Int](x, xs)) // reverses the list
//  l1.length
//  l1.reduceLeft(_ + _)
//  l1.reduceRight(_ + _)
//  List.concatenate(List(1, 2), List(3, 4), List(5, 6))
//
//  def add1(xs: List[Int]): List[Int] = {
//    xs.foldRight(MNil: List[Int])((x, xs) => Cons(x + 1, xs))
//  }
//  add1(List(2, 4, 6))

//  l1.toString
//  l1.map(_ + 1)
//  l1.flatMap(x => List(x, math.pow(x, 2)))
//  l1.filter(_ > 2)
//  l1.filter1(_ > 2)
//  List(1, 2, 3).zipWith(List(4, 5, 6), (x: Int, y: Int) => x + y)
//  l1.take(2)
//  l1.takeWhile(_ < 3)

l1.forall(_ > 0)
l1.exists(_ < 0)
l1.dropWhile(_ < 3)
l1.hasSubsequence(List(1, 2))
l1.hasSubsequence(List(2, 3))
l1.hasSubsequence(List(3, 4))
}