exercises from the amazing fpiscala

fpis.sc

import scala.annotation.tailrec

/**
  * EXERCISE 2.1
  * Write a recursive function to get the nth Fibonacci number (http://mng.bz/C29s).
  * The first two Fibonacci numbers are 0 and 1 . The nth number is always the sum of the
  * previous two—the sequence begins 0, 1, 1, 2, 3, 5 . Your definition should use a
  * local tail-recursive function.
  */
def fib(n: Int): Int = {
  @tailrec
  def go(n: Int, prev: Int, curr: Int): Int =
    if (n == 0) prev
    else go(n - 1, curr, prev + curr)
  go(n, 0, 1)
}
fib(1)
fib(5)
/**
  * EXERCISE 2.2
  * Implement isSorted , which checks whether an Array[A] is sorted according to a
  * given comparison function
  */
def isSorted[A](as: Array[A], ordered: (A, A) => Boolean): Boolean = {
  @tailrec
  def go(len: Int): Boolean = {
    if (len >= as.length - 1) true
    else if (ordered(as(len), as(len + 1))) false
    else go(len + 1)
  }
  go(as.length)
}
val x: (Int, Int) => Boolean = _ > _
x(2, 3)
x(3, 2)
isSorted(Array(1, 2, 3), x)

/**
  * EXERCISE 2.3
  * Let’s look at another example, currying, 9 which converts a function f of two arguments
  * into a function of one argument that partially applies f . Here again there’s only one
  * implementation that compiles. Write this implementation.
  */
def curry[A, B, C](f: (A, B) => C): A => (B => C) = a => b => f(a, b)

/**
  * EXERCISE 2.4
  * Implement uncurry , which reverses the transformation of curry . Note that since =>
  * associates to the right, A => (B => C) can be written as A => B => C .
  */
def uncurry[A, B, C](f: A => B => C): (A, B) => C = (a, b) => f(a)(b)

/**
  * EXERCISE 2.5
  * Implement the higher-order function that composes two functions.
  */
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 apply[A](ls: A*): List[A] =
    if (ls.isEmpty) Nil
    else Cons(ls.head, apply(ls.tail: _*))

  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 => 0.0
    case Cons(x, xs) => x * product(xs)
  }

  /**
    * EXERCISE 3.2
    * Implement the function tail for removing the first element of a List . Note that the
    * function takes constant time. What are different choices you could make in your
    * implementation if the List is Nil ? We’ll return to this question in the next chapter.
    */
  def tail[A](ls: List[A]): List[A] = ls match {
    case Nil => Nil
    case Cons(x, xs) => xs
  }

  /**
    * EXERCISE 3.3
    * Using the same idea, implement the function setHead for replacing the first element
    * of a List with a different value.
    */
  def setHead[A](h: A, ls: List[A]): List[A] = ls match {
    case Nil => Nil
    case Cons(_, xs) => Cons(h, xs)
  }

  /**
    * EXERCISE 3.4
    * Generalize tail to the function drop , which removes the first n elements from a list.
    * Note that this function takes time proportional only to the number of elements being
    * dropped—we don’t need to make a copy of the entire List .
    */
  @tailrec
  def drop[A](ls: List[A], n: Int): List[A] = ls match {
    case Nil => Nil
    case Cons(x, xs) => if (n > 1) drop(xs, n -1) else xs
  }

  /**
    * EXERCISE 3.5
    * Implement dropWhile , which removes elements from the List prefix as long as they
    * match a predicate.
    */
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
    case Cons(x, xs) if f(x) =>  dropWhile(xs, f)
    case _ => l
  }

  /**
    * EXERCISE 3.6
    * Not everything works out so nicely. Implement a function, init , that returns a List
    * consisting of all but the last element of a List . So, given List(1,2,3,4) , init will
    * return List(1,2,3) . Why can’t this function be implemented in constant time like
    * tail ?
    */
  def init[A](l: List[A]): List[A] = l match {
    case Nil => sys.error("init of empty list")
    case Cons(_, Nil) => Nil
    case Cons(h, t) => Cons(h, init(t))
  }

  /**
    * EXERCISE 3.7
    * Can product , implemented using foldRight , immediately halt the recursion and
    * return 0.0 if it encounters a 0.0 ? Why or why not? Consider how any short-circuiting
    * might work if you call foldRight with a large list. This is a deeper question that we’ll
    * return to in chapter 5.
    */
  def foldRight[A, B](as: List[A], b: B)(f: (A, B) => B): B = as match {
    case Nil => b
    case Cons(x, xs) => f(x, foldRight(xs, b)(f))
  }

  def sum1(ints: List[Int]): Int = foldRight(ints, 0)((x, y) => x + y)
  def product1(ds: List[Double]): Double = foldRight(ds, 0.0)((x, y) => x * y)

  /**
    * EXERCISE 3.8
    * See what happens when you pass Nil and Cons themselves to foldRight , like this:
    * foldRight(List(1,2,3), Nil:List[Int])(Cons(_,_)) .  What do you think this
    * says about the relationship between foldRight and the data constructors of List ?
    */
  val q = foldRight(List(1, 2, 3), Nil: List[Int])(Cons(_, _))

  /**
    * EXERCISE 3.9
    * Compute the length of a list using foldRight .
    */
  def length[A](as: List[A]): Int = foldRight(as, 0)((_, y) => 1 + y)

  /**
    * EXERCISE 3.10
    * Our implementation of foldRight is not tail-recursive and will result in a StackOver-
    * flowError for large lists (we say it’s not stack-safe). Convince yourself that this is the
    * case, and then write another general list-recursion function, foldLeft , that is
    * tail-recursive, using the techniques we discussed in the previous chapter. Here is its
    * signature: 11
    */
  @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)
  }

  /**
    * EXERCISE 3.11
    * Write sum , product , and a function to compute the length of a list using foldLeft .
    */
  def sum2(ints: List[Int]): Int = foldLeft(ints, 0)(_ + _)
  def product2(ds: List[Double]): Double = foldLeft(ds, 0.0)(_ * _)
  def length2[A](as: List[A]): Int = foldLeft(as, 0)((x, y) => x + 1)

  /**
    * EXERCISE 3.12
    * Write a function that returns the reverse of a list (given List(1,2,3) it returns
    * List(3,2,1) ). See if you can write it using a fold.
    */
  def reverse[A](ls: List[A]) = foldLeft(ls, List[A]())((xs, x) => Cons(x, xs))

  /**
    * EXERCISE 3.13
    * Hard: Can you write foldLeft in terms of foldRight ? How about the other way
    * around? Implementing foldRight via foldLeft is useful because it lets us implement
    * foldRight tail-recursively, which means it works even for large lists without overflow-
    * ing the stack.
    */
  def foldLeft1[A, B](as: List[A], z: B)(f: (B, A) => B): B = foldRight(as, (b:B) => b)((a,g) => b => g(f(b,a)))(z)
  def foldRight2[A,B](l:  List[A], z: B)(f: (A, B) => B): B = foldLeft(reverse(l ), z)((b,a) => f(a, b))

  /**
    * EXERCISE 3.14
    * Implement append in terms of either foldLeft or foldRight .
    */
  def append1[A](l1: List[A], l2: List[A]): List[A] = l1 match {
    case Nil => l2
    case Cons(x, xs) => Cons(x, append1(xs, l2))
  }

  def append2[A](l1: List[A], l2: List[A]): List[A] = foldRight(l1, Nil: List[A])(Cons(_, _))
//  def append3[A](l1: List[A], l2: List[A]): List[A] = foldLeft(reverse(l1), Nil: List[A])(Cons(_, _))

  /**
    * EXERCISE 3.15
    * Hard: Write a function that concatenates a list of lists into a single list. Its runtime
    * should be linear in the total length of all lists. Try to use functions we have already
    * defined.
    */
  def concat[A](as: List[List[A]]): List[A] = foldRight(as, Nil: List[A])(append1)

  /**
    * EXERCISE 3.16
    * Write a function that transforms a list of integers by adding 1 to each element.
    * (Reminder: this should be a pure function that returns a new List !)
    */
  def mapMatch[A, B](as: List[A])(f: A => B): List[B] = as match {
    case Nil => Nil
    case Cons(x: A, xs: List[A]) => Cons(f(x), mapMatch(xs)(f))
  }

  def addOneViaMap(ls: List[Int]): List[Int] = mapMatch(ls)(_ + 1)
  def addOneViaFold(ls: List[Int]): List[Int] = foldRight(ls, Nil: List[Int])((h,t) => Cons(h+1,t))

  /**
    * EXERCISE 3.17
    * Write a function that turns each value in a List[Double] into a String . You can use
    * the expression d.toString to convert some d: Double to a String .
    */
  def double2StringViaMap(as: List[Double]): List[String] = mapMatch(as)(_.toString)
  def double2StringViaFold(as: List[Double]): List[String] = foldRight(as, Nil: List[String])((h,t) => Cons(h.toString, t))
  /**
    * EXERCISE 3.18
    * Write a function map that generalizes modifying each element in a list while maintaining
    * the structure of the list.
    */
  def map[A,B](as: List[A])(f: A => B): List[B] = foldRight(as, Nil: List[B])((h,t) => Cons(f(h), t))

  /**
    * EXERCISE 3.19
    * Write a function filter that removes elements from a list unless they satisfy a given
    *predicate. Use it to remove all odd numbers from a List[Int] .
    */
  def filter[A](as: List[A])(f: A => Boolean): List[A] = foldRight(as, Nil: List[A])((h,t) => if(f(h)) Cons(h, t) else t)

  /**
    * EXERCISE 3.20
    * Write a function flatMap that works like map except that the function given will return
    * a list instead of a single result, and that list should be inserted into the final resulting
    * list. Here is its signature:
    * For instance, flatMap(List(1,2,3))(i => List(i,i)) should result in
    * List(1,1,2,2,3,3) .
    */
  def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] = concat(map(as)(f))

  /**
    * EXERCISE 3.21
    * Use flatMap to implement filter .
    */
  def filterViaFlatMap[A](as: List[A])(f: A => Boolean): List[A] = flatMap(as)(x => if(f(x)) List(x) else Nil)

  /**
    * EXERCISE 3.22
    * Write a function that accepts two lists and constructs a new list by adding correspond-
    * ing elements. For example, List(1,2,3) and List(4,5,6) become List(5,7,9) .
    */
  def two2One(as: List[Int], bs: List[Int]): List[Int] = (as, bs) match {
    case (_, Nil) => Nil
    case (Nil, _) => Nil
    case (Cons(x, xs), Cons(y, ys)) => Cons(x + y, two2One(xs, ys))
  }

  /**
    * EXERCISE 3.23
    * Generalize the function you just wrote so that it’s not specific to integers or addition.
    * Name your generalized function zipWith
    */
  def zipWith[A, B, C](as: List[A], bs: List[B])(f: (A, B) => C): List[C] = (as, bs) match {
    case (_, Nil) => Nil
    case (Nil, _) => Nil
    case (Cons(x, xs), Cons(y, ys)) => Cons(f(x, y), zipWith(xs, ys)(f))
  }

  /**
    * EXERCISE 3.24
    * Hard: As an example, implement hasSubsequence for checking whether a List contains
    * another List as a subsequence. For instance, List(1,2,3,4) would have
    * List(1,2) , List(2,3) , and List(4) as subsequences, among others. You may have
    * some difficulty finding a concise purely functional implementation that is also efficient.
    * That’s okay. Implement the function however comes most naturally. We’ll
    * return to this implementation in chapter 5 and hopefully improve on it. Note: Any
    * two values x and y can be compared for equality in Scala using the expression x == y .
    * def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean
    */
}

/////////////////////////////////

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]

object Tree {
  /**
    * EXERCISE 3.25
    * Write a function size that counts the number of nodes (leaves and branches) in a tree.
    */
  def size[A](tree: Tree[A]): Int = tree match {
    case Leaf(_) => 1
    case Branch(l, r) => 1 + size(l) + size(r)
  }

  /** EXERCISE 3.26
    * Write a function maximum that returns the maximum element in a Tree[Int] . (Note:
    * In Scala, you can use x.max(y) or x max y to compute the maximum of two integers x
    * and y .)
    */
  def maximum(tree: Tree[Int]): Int = tree match {
    case Leaf(n) => n
    case Branch(l, r) => maximum(l) max maximum(r)

  }

  /** EXERCISE 3.27
    * Write a function depth that returns the maximum path length from the root of a tree
    * to any leaf.
    */
  def depth[A](tree: Tree[A]): Int = tree match {
    case Leaf(_) => 0
    case Branch(l, r) => 1 + (depth(l) max depth(r))
  }

  /** EXERCISE 3.28
    * Write a function map , analogous to the method of the same name on List , that modi-
    * fies each element in a tree with a given function.
    */
  def map[A, B](tree: Tree[A])(f: A => B): Tree[B] = tree match {
    case Leaf(n) => Leaf(f(n))
    case Branch(l, r) => Branch(map(l)(f), map(r)(f))
  }

  /** EXERCISE 3.29
    * Generalize size , maximum , depth , and map , writing a new function fold that abstracts
    * over their similarities. Reimplement them in terms of this more general function. Can
    * you draw an analogy between this fold function and the left and right folds for List ?
    */
  def fold[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B): B = tree match {
    case Leaf(n) => f(n)
    case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
  }
  def size1[A](tree: Tree[A]): Int   = fold(tree)(a => 1)(1 + _ + _)
  def maximum1(tree: Tree[Int]): Int = fold(tree)(a => a)(_ max _)
  def depth1[A](tree: Tree[A]): Int  = fold(tree)(a => 0)((dl, dr) => 1 + (dl max dr))
  def map[A, B](tree: Tree[A])(f: A => B): Tree[B] = fold(tree)(n => Leaf(f(n)): Tree[B])((d1, d2) => Branch(d1, d2))
}

////////////////////////////////////

sealed trait Option[+A]
case class Some[+A](get: A) extends Option[A]
case object None extends Option[Nothing]