functional-scala-exercises-ch-2-3.scala

// 2.1

def fib(n: Int): Int = {

  @annotation.tailrec
  def go(a: Int, b: Int, n: Int): Int =
    if (n > 0) go(b, a+b, n-1) else a

  go(0, 1, n)
}

// 2.2

def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = {

  @annotation.tailrec
  def loop(n: Int): Boolean = {
    if (n >= as.length-1) true
    else if (!ordered(as(n), as(n + 1))) false
    else loop(n + 1)
  }

  loop(0)
}

// 2.3

def curry[A,B,C](f: (A,B) => C): A => (B => C) =
  (a: A) => (b: B) => f(a,b)

// 2.4

def uncurry[A,B,C](f: A => B => C): (A, B) => C =
  (a: A, b: B) => f(a)(b)

// 2.5

def compose[A,B,C](f: B => C, g: A => B): A => C =
  a => f(g(a))

//

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def sum(ints: List[Int]): Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x + sum(xs)
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)
  }

  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))
}

// 3.1

val x = List(1,2,3,4,5) match {
  case Cons(x, Cons(2, Cons(4, _))) => x
  case Nil => 42
  case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
  case Cons(h, t) => h + List.sum(t)
  case _ => 101
}

// 3.2

def tail[A](as: List[A]): List[A] = as match {
  case Cons(_, t) => t
  case Nil => Nil
}

// 3.3

def setHead[A](a: A, as: List[A]): List[A] = as match {
  case Cons(_, t) => Cons(a, t)
  case Nil => Nil
}

// 3.4

def drop[A](l: List[A], n: Int): List[A] = l match {
  case Cons(_, t) if n > 0 => drop(t, n - 1)
  case x => x
}

// 3.5

def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
  case Cons(x, t) if f(x) => dropWhile(t, f)
  case Cons(x, t) if !f(x) => Cons(x, t)
  case x => x
}

// 3.6

def init[A](l: List[A]): List[A] = {
  def build(from: List[A]): List[A] = from match {
    case Nil => Nil
    case Cons(_, Nil) => Nil
    case Cons(h, t) => Cons(h, build(t))
  }

  build(l)
}

//

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
  as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

def sum2(ns: List[Int]) =
  foldRight(ns, 0)((x,y) => x + y)

def product2(ns: List[Double]) =
  foldRight(ns, 1.0)(_ * _)

// 3.7

// Not unless you use an extra effect over List specifying whether to continue folding

// 3.8

foldRight(List(1,2,3), Nil:List[Int])(Cons(_,_))

// 3.9

def length[A](as: List[A]): Int =
  foldRight(as, 0)((_, acc) => acc + 1)

// 3.10

@annotation.tailrec
def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B =
  as match {
    case Nil => z
    case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
  }

// 3.11

def sum3(ns: List[Int]) =
  foldLeft(ns, 0)(_+_)

def product3(ns: List[Double]) =
  foldLeft(ns, 1.0)(_*_)

def length3[A](as: List[A]): Int =
  foldLeft(as, 0)((acc, _) => acc + 1)

// 3.12

def reverse[A](as: List[A]): List[A] =
  foldLeft(as, Nil:List[A])((acc,x) => Cons(x, acc))

// 3.13

def foldRightViaFoldLeft[A,B](as: List[A], z: B)(f: (A, B) => B): B =
  foldLeft(reverse(as), z)((acc, x) => f(x, acc))

// 3.14

def appendViaFoldRight[A](a1: List[A], a2: List[A]): List[A] =
  foldRight(a1, a2)((x, acc) => Cons(x, acc))

def appendViaFoldLeft[A](a1: List[A], a2: List[A]): List[A] =
  foldLeft(reverse(a1), a2)((acc, x) => Cons(x, acc))

// 3.15

def concat[A](ass: List[List[A]]): List[A] =
  foldRight(ass, Nil:List[A])(appendViaFoldRight)

// 3.16

def add1(ints: List[Int]): List[Int] =
  foldRight(ints, Nil:List[Int])((x, acc) => Cons(x+1, acc))

// 3.17

def toString(doubles: List[Double]): List[String] =
  foldRight(doubles, Nil:List[String])((x, acc) => Cons(x.toString, acc))

// 3.18

def map[A,B](as: List[A])(f: A => B): List[B] =
  foldRight(as, Nil:List[B])((x, acc) => Cons(f(x), acc))

// 3.19

def filter[A](as: List[A])(f: A => Boolean): List[A] =
  foldRight(as, Nil:List[A])((x, acc) => if (f(x)) Cons(x, acc) else acc)

filter(List(1,2,3,4,5))(x => x % 2 == 0)

// 3.20

def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] =
  concat(map(as)(f))

flatMap(List(1,2,3))(i => List(i,i))

// 3.21

def filterViaFlatMap[A](as: List[A])(f: A => Boolean): List[A] =
  flatMap(as)(x => if (f(x)) List(x) else Nil)

// 3.22

def addWith(a1: List[Int], a2: List[Int]): List[Int] = (a1, a2) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1, t1), Cons(h2, t2)) => Cons(h1 + h2, addWith(t1, t2))
}

// 3.23

def zipWith[A,B,C](a1: List[A], a2: List[B])(f: (A,B) => C): List[C] = (a1, a2) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1, t1), Cons(h2, t2)) => Cons(f(h1,h2), zipWith(t1, t2)(f))
}

// 3.24

def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {

  def running[A](sup1: List[A], sub1: List[A], started: Boolean): Boolean = (sup1, sub1) match {
    case (Nil, Nil) => true
    case (_, Nil) => true
    case (Nil, _) => false
    case (Cons(h1,t1), Cons(h2,t2)) =>
      if (started && h1 != h2)
        false
      else if (!started && h1 != h2)
        running(t1, sub, false)
      else
        running(t1, t2, true)
  }


  running(sup, sub, false)
}

//

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

// 3.25

def size[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 1
  case Branch(l, r) => size(l) + size(r)
}

// 3.26

def maximum(t: Tree[Int]): Int = t match {
  case Leaf(x) => x
  case Branch(l, r) => maximum(l) max maximum(r)
}

// 3.26

def depth[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 0
  case Branch(l,r) => 1 + (depth(l) max depth(r))
}

// 3.27

def map[A, B](t: Tree[A])(f: A => B): Tree[B] = t match {
  case Leaf(x) => Leaf(f(x))
  case Branch(l, r) => Branch(map(l)(f), map(r)(f))
}

// 3.28

def fold[A, B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
  case Leaf(x) => f(x)
  case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
}

def sizeViaFold[A](t: Tree[A]): Int =
  fold(t)(x => 1)(1 + _ + _)

def maximumViaFold[A](t: Tree[Int]): Int =
  fold(t)(x => x)(_ max _)

def depthViaFold[A](t: Tree[A]): Int =
  fold(t)(x => 0)((y, z) => 1 + (y max z))

def mapViaFold[A, B](t: Tree[A])(f: A => B): Tree[B] =
  fold(t)(x => Leaf(f(x)): Tree[B])(Branch(_,_))