scala

test.scala

package week5

object higherOrderListFunctions {
  val l: List[Int] = new Cons[Int](5, Nil)        //> l  : week5.List[Int] = 5,.
  l.head                                          //> res0: Int = 5
  l.tail                                          //> res1: week5.List[Int] = .
  l.map(x => x * 2).head                          //> res2: Int = 10

  def squareList1(xs: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case Cons(h, t) => new Cons(h * h, squareList1(t))
  }                                               //> squareList1: (xs: week5.List[Int])week5.List[Int]
  def squareList2(xs: List[Int]): List[Int] =
    xs map (x => x * x)                           //> squareList2: (xs: week5.List[Int])week5.List[Int]

  var l1 = squareList1(new Cons(1, new Cons(2, new Cons(3, Nil))))
                                                  //> l1  : week5.List[Int] = 1,4,9,.
  var l2 = squareList2(new Cons(1, new Cons(2, new Cons(3, Nil))))
                                                  //> l2  : week5.List[Int] = 1,4,9,.
  var l3 = l1.filter(x => x < 5)                  //> l3  : week5.List[Int] = 1,4,.
  var l4 = l1.filterNot(x => x < 5)               //> l4  : week5.List[Int] = 9,.
  def p: Function1[Int, Boolean] = x => x < 5     //> p: => Int => Boolean
  var p1 = (l2.filter(p), l2.filterNot(p))        //> p1  : (week5.List[Int], week5.List[Int]) = (1,4,.,9,.)
  val (p2, p3) = l2 partition p                   //> p2  : week5.List[Int] = 1,4,.
                                                  //| p3  : week5.List[Int] = 9,.

  val c1 = new Cons(1, Nil)                       //> c1  : week5.Cons[Int] = 1,.
  val c2 = new Cons(2, Nil)                       //> c2  : week5.Cons[Int] = 2,.
  val cc = c1 concat 6 concat 8                   //> cc  : week5.List[Int] = 1,6,8,.
  var cc1 = cc concat c1 concat c2                //> cc1  : week5.List[Int] = 1,6,8,1,2,.
  cc1 partition p                                 //> res3: (week5.List[Int], week5.List[Int]) = (1,1,2,.,6,8,.)
  cc1 takeWhile (x => x == 1 || x == 6)           //> res4: week5.List[Int] = 1,6,.
  cc1 dropWhile (x => x == 1 || x == 6)           //> res5: week5.List[Int] = 8,1,2,.
  (cc1 takeWhile p, cc1 dropWhile p)              //> res6: (week5.List[Int], week5.List[Int]) = (1,.,6,8,1,2,.)
  cc1 span p                                      //> res7: (week5.List[Int], week5.List[Int]) = (1,.,6,8,1,2,.)

  val nums = new Cons(2, new Cons(-4, new Cons(5, new Cons(7, new Cons(1, Nil)))))
                                                  //> nums  : week5.Cons[Int] = 2,-4,5,7,1,.
  val fruit = new Cons("apple", new Cons("pear", new Cons("orange", new Cons("pineapple", Nil))))
                                                  //> fruit  : week5.Cons[String] = apple,pear,orange,pineapple,.

  nums filter (x => x > 0)                        //> res8: week5.List[Int] = 2,5,7,1,.
  nums filterNot (x => x > 0)                     //> res9: week5.List[Int] = -4,.
  nums partition (x => x > 0)                     //> res10: (week5.List[Int], week5.List[Int]) = (2,5,7,1,.,-4,.)
  nums takeWhile (x => x > 0)                     //> res11: week5.List[Int] = 2,.
  nums dropWhile (x => x > 0)                     //> res12: week5.List[Int] = -4,5,7,1,.
  nums span (x => x > 0)                          //> res13: (week5.List[Int], week5.List[Int]) = (2,.,-4,5,7,1,.)
  val packList = new Cons("a", new Cons("a", new Cons("a", new Cons("b", new Cons("c", new Cons("c", new Cons("a", Nil)))))))
                                                  //> packList  : week5.Cons[String] = a,a,a,b,c,c,a,.
 val pl = packList.pack                           //> pl  : week5.List[week5.List[String]] = a,a,a,.,b,.,c,c,.,a,.,.
 pl.first                                         //> res14: week5.List[String] = a,a,a,.
 pl.tail.tail.tail.head                           //> res15: week5.List[String] = a,.
 pl.length                                        //> res16: Int = 4
 pl.tail.length                                   //> res17: Int = 3
 pl.encode                                        //> res18: week5.List[(week5.List[String], Int)] = (a,a,a,.,1),(b,.,1),(c,c,.,1
                                                  //| ),(a,.,1),.
}

abstract class List[+T] {
  def head: T
  def tail: List[T]
  override def toString: String
  def map[U](f: T => U): List[U] = this match {
    case Nil => Nil
    case Cons(x, xs) => new Cons[U](f(x), xs map (f))
  }
  def filter(p: T => Boolean): List[T] = this match {
    case Nil => this
    case Cons(x, xs) => if (p(x)) new Cons(x, xs.filter(p)) else xs.filter(p)
  }
  def filterNot(p: T => Boolean): List[T] = this match {
    case Nil => this
    case Cons(x, xs) => if (!p(x)) new Cons(x, xs.filterNot(p)) else xs.filterNot(p)
  }
  def partition(p: T => Boolean): (List[T], List[T]) = {
    def partitionAcc(xs: List[T], l1: List[T], l2: List[T]): (List[T], List[T]) = xs match {
      case Nil => (l1, l2)
      case Cons(y, ys) => if (p(y)) partitionAcc(ys, l1 concat y, l2) else partitionAcc(ys, l1, l2 concat y)
    }
    partitionAcc(this, Nil, Nil)
  }
  def takeWhile(p: T => Boolean): List[T] = this match {
    case Nil => this
    case Cons(x, xs) => if (p(x)) new Cons(x, xs takeWhile p) else Nil
  }
  def dropWhile(p: T => Boolean): List[T] = this match {
    case Nil => this
    case Cons(x, xs) => if (p(x)) xs dropWhile p else this
  }
  def span(p: T => Boolean): (List[T], List[T]) = {
    def spanAcc(xs: List[T], ys: List[T]): (List[T], List[T]) = xs match {
      case Nil => (ys, Nil)
      case Cons(r, rs) => if (p(r)) spanAcc(rs, ys concat r) else (ys, xs)
    }
    spanAcc(this, Nil)
  }
  def pack: List[List[T]] = this match {
    case Nil => Nil
    case Cons(x, xs) => new Cons(this takeWhile (y => y == x), (this dropWhile (y => y == x)).pack)
  }
  def encode: List[(T, Int)] = this match {
    case Nil => Nil
    case Cons(x, xs) => this.pack.map(z => (z.first, z.length))
  }
  def concat[U >: T](x: U): List[U] = this match {
    case Nil => new Cons[U](x, Nil)
    case Cons(y, ys) => new Cons[U](y, ys concat x)
  }
  def concat[U >: T](xs: List[U]): List[U] = xs match {
    case Nil => this
    case Cons(y, ys) => this concat y concat ys
  }
  def first: T = this match {
  	case Nil => throw new NoSuchElementException("Nil.first")
  	case Cons(x, xs) => x
  }
  def length: Int = {
  	def lengthAcc(xs: List[T], i: Int): Int = xs match {
  		case Nil => i
  		case Cons(y, ys) => lengthAcc (ys, i + 1)
  	}
  	lengthAcc(this, 0)
  }
}
case class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  override def toString: String = head.toString + "," + tail.toString
}
object Nil extends List[Nothing] {
  def head: Nothing = throw new NoSuchElementException("Nil.head")
  def tail: List[Nothing] = throw new NoSuchElementException("Nil.tail")
  override def toString: String = "."
}