fpinscala

ch10.scala

package fpinscala

object Ch10 {

  trait Monoid[T] {
    def op(x: T, y: T): T
    def zero: T
  }

  // 10.1
  val intAddition = new Monoid[Int] {
    def op(x: Int, y: Int) = x + y
    def zero = 0
  }
  val intMultiplication = new Monoid[Int] {
    def op(x: Int, y: Int) = x * y
    def zero = 1
  }
  val booleanOr = new Monoid[Boolean] {
    def op(x: Boolean, y: Boolean) = x || y
    def zero = false
  }
  val booleanAnd = new Monoid[Boolean] {
    def op(x: Boolean, y: Boolean) = x && y
    def zero = true
  }

  // 10.2
  def optionMonoid[A]: Monoid[Option[A]] = new Monoid[Option[A]] {
    def op(x: Option[A], y: Option[A]) = x orElse y
    def zero = None
  }
  // 10.3
  def endoMonoid[A]: Monoid[A => A] = new Monoid[A => A] {
    def op(f: A => A, g: A => A): A => A = f compose g
    def zero = a => a
  }


  // 10.4
  // :(

  // 10.5
  def foldMap[A,B](as: List[A], m: Monoid[B])(f: A => B): B =
    as.map(f).fold(m.zero)(m.op)

  // 10.6
  def foldRight[A,B](as: List[A])(b: B)(f: (A,B) => B): B =
    foldMap(as, endoMonoid[B])(f.curried)(b)

  // 10.7
  def foldMapV[A,B](v: IndexedSeq[A], m: Monoid[B])(f: A => B): B = {
    if(v.isEmpty) m.zero
    else if (v.length == 1) f(v.head)
    else {
      val (left, right) = v.splitAt(v.length / 2)
      m.op(foldMapV(left, m)(f), foldMapV(right,m)(f))
    }
  }


  // 10.8
  // 10.9
  def isOrdered(v: IndexedSeq[Int]): Boolean = {
    val m = new Monoid[IndexedSeq[Int]] {
      override def op(l: IndexedSeq[Int], r: IndexedSeq[Int]):
      override def zero = ???
    }
  }

  sealed trait WC
  case class Stub(chars: String) extends WC
  case class Part(lStub: String, words: Int, rStub: String) extends WC
  object WC {
    def fromString(string: String) = {
      val splitted = string.split(" ")
      if (splitted.length == 1) Stub(splitted.head)
      else if (splitted.length == 2) Part(splitted.head, 1, "")
      else Part(splitted.head, splitted.length - 2, splitted.last)
    }
  }

  val wcMonoid: Monoid[WC] = new Monoid[WC] {
    override def op(a: WC, b: WC): WC = (a,b) match {
      case (Stub(ca), Stub(cb)) => Stub(ca + cb)
      case (Stub(ca), Part(lStub, words, rStub)) =>
        val (left, rest) = (ca + lStub).span(_ != " ")
        Part(left, rest.split(" ").length + words, rStub)
      case (Part(lStub, words, rStub), Stub(cb)) =>
        val (left, rest) = (cb + lStub).span(_ != " ")
        Part(left, rest.split(" ").length + words, rStub)
      case (Part(lStubA, wordsA, rStubA), Part(lStubB, wordsB, rStubB)) =>
        Part(lStubA, wordsA + (rStubA + lStubB).split(" ").length + wordsB, rStubB)
    }
    override def zero = Stub("")
  }

  // 10.11
  def countWords(string: String): Int = {
    def miniCountWords(str: String): Int = if(str.nonEmpty) 1 else 0

    WC.fromString(string) match {
      case Stub(chars) => miniCountWords(chars)
      case Part(l, words, r) => miniCountWords(l) + words + miniCountWords(r)
    }
  }
}

ch2.scala

// 2.1
def fib(n: Int): Int = {
  def loop(m: Int, curr: Int, next: Int): Int =
    if (m == n) curr
    else loop(m + 1, next, curr + next)

  loop(0, 0, 1)
}

// 2.2
def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = {
  def loop(as1: Array[A]): Boolean = {
    if(as1.length <= 1) true
      else if (!ordered(as1(0),as1(1))) false
    else loop(as1.tail)
  }
  loop(as)
}

// 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: A) => f(g(a))

ch3.scala

package fpinscala

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: _*))
}

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 Ch3 extends App{

  // 3.1
  //matches 3rd statement, so resolves to 3

  // 3.2
  def tail[A](list: List[A]) = list match {
    case Cons(head, tail) => tail
    case Nil => throw new IllegalArgumentException("tail of empty list")
  }

  // 3.3
  def setHead[A](list: List[A], head: A) = list match {
    case Cons(_, tail) => Cons(head, tail)
    case Nil => throw new UnsupportedOperationException("setHead of empty list")
  }

  // 3.4
  def drop[A](l: List[A], n: Int): List[A] = l match {
    case xs if n == 0 => xs
    case Cons(head, tail) if n > 0 => drop(tail, n - 1)
    case _ if n < 0 => throw new UnsupportedOperationException("drop more elements than exist")
  }

  // 3.5
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] =  l match {
    case Cons(head, tail) if f(head) => dropWhile(tail, f)
    case _ => l
  }

  // 3.6
  def init[A](l: List[A]): List[A] = l match {
    case Cons(head, tail: Cons[A]) => Cons(head, init(tail))
    case Cons(head, Nil) => Nil
    case _ => throw new UnsupportedOperationException("init of Nil")
  }

  // 3.7
  // no

  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))
  }
  //3.8
  // you get the same list back

  // 3.9
  def length[A](list: List[A]) = foldRight(list, 0)((a,b) => b + 1)

  // 3.10
  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 sum(list: List[Int]) = foldLeft(list, 0)(_ + _)
  def product(list: List[Int]) = foldLeft(list, 1)(_ * _)
  def length2[A](list: List[A]) = foldLeft(list, 0)((a, b) => a + 1)

  // 3.12
  def reverse[A](list: List[A]) = foldLeft(list, Nil: List[A])((xs, a) => Cons(a, xs))

  // 3.13
  def foldLeft2[A, B](as: List[A], z: B)(f: (B, A) => B): B =
    foldRight(reverse(as), z)((a, b) => f(b,a))

  // 3.14
  def append[A](first: List[A], second: List[A]) = foldRight(first, second)(Cons(_,_))

  // 3.15
  def concat[A](lists: List[List[A]]) =
    foldRight(lists, Nil: List[A])(append)

  // 3.16
  // Write a function that transforms a list of integers by adding 1 to each element.
  def mapPlusOne(list: List[Int]) =
    foldRight(list, Nil: List[Int])((a: Int, b: List[Int]) => Cons[Int](a + 1, b))

  // 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 mapToString(list: List[Double]) =
    foldRight(list, Nil: List[String])((a: Double, b: List[String]) => Cons(a.toString, b))

  // 3.18
  // Write a function map that generalizes modifying each element in a list while maintain- ing the structure of the list
  def map[A, B](as: List[A])(f: A => B): List[B] =
    foldRight(as, Nil: List[B])((a: A, bs: List[B]) => Cons(f(a), bs))

  // 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])((a: A, tail: List[A]) => if(f(a)) Cons(a, tail) else tail)

  // 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.
  def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] =
    foldRight(as, Nil: List[B])((a: A, tail: List[B]) => append(f(a), tail))

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

  // 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 zipAdd(as0: List[Int], as1: List[Int]): List[Int] = (as0, as1) match {
    case (Cons(head0, tail0), Cons(head1, tail1)) => Cons(head0 + head1, zipAdd(tail0, tail1))
    case (_: Cons, Nil) => as0
    case (Nil, _: Cons) => as1
    case _ => Nil
  }

  // 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](as0: List[A], as1: List[A])(f: (A, A) => A): List[A] = {
    def go(xs: List[A], ys: List[A]): List[A] = (xs, ys) match {
      case (Cons(head0, tail0), Cons(head1, tail1)) => Cons(f(head0, head1), go(tail0, tail1))
      case (_: Cons, Nil) => xs
      case _ => ys
    }
    go(as0, as1)
  }

  // 3.24
  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
    def beginsWith(l: List[A], prefix: List[A]): Boolean = (l, prefix) match {
      case (Cons(headL, tailL), Cons(headPrefix, tailPrefix)) if headL == headPrefix => beginsWith(tailL, tailPrefix)
      case (_, _: Cons) => false
      case _ => true
    }

    (sup, sub) match {
      case _ if beginsWith(sup, sub) => true
      case (supC: Cons, _) => hasSubsequence(supC, sub)
      case _ => false
    }
  }

  // 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 = {
    case _: Leaf => 1
    case Branch(_, _) => size(_) + size(_)
  }

  // 3.26
  def maximum(tree: Tree[Int]): Int = {
    case Leaf(_) => _
    case Branch(_, _) => maximum(_) max maximum(_)
  }

  // 3.27
  def depth[A](tree: Tree[A]): Int = {
    case _: Leaf => 0
    case Branch(l, r) => 1 + (depth(l) max depth(r))
  }
  
  // 3.28
  def map[A, B](tree: Tree[A], f: A => B ): Tree[B] = tree match {
    case Leaf(value) => Leaf(f(value))
    case Branch(l, r) => Branch(map(l, f), map(r, f))
  }

  // 3.29
  def fold[A, B](tree: Tree[A], b: B)(f: A => B)(g: (B,B) => B): B = tree match {
    case Leaf(a) => f(a)
    case Branch(l, r) => g(fold(l, b)(f)(g), fold(r, b)(f)(g))
  }

}

ch6.scala

package fpinscala

trait RNG {
  def nextInt: (Int, RNG)
}

case class SimpleRNG(seed: Long) extends RNG {
  override def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
    val nextRNG = SimpleRNG(newSeed)
    val n = (newSeed >>> 16).toInt
    (n, nextRNG)
  }
}
object Ch6 extends App {

  type Rand[+A] = RNG => (A, RNG)

  // 6.1
  def nonNegativeInt(rng: RNG): (Int, RNG) = rng.nextInt match {
    case (i, rng0) if i >= 0 => (i, rng0)
    case (Int.MinValue, rng0) => nonNegativeInt(rng0)
    case (neg, rng0) => (-neg, rng0)
  }

  // 6.2
  def double(rng: RNG): (Double, RNG) = {
    def numer(rng0: RNG): (Int, RNG) = nonNegativeInt(rng) match {
      case (Int.MaxValue, rng1) => numer(rng1)
      case (i, rng1) => (i, rng1)
    }

    val (numerator, rng0) = numer(rng)
    (numerator.toDouble / Int.MaxValue.toDouble, rng0)
  }

  // 6.3
  def intDouble(rng: RNG): ((Int,Double), RNG) = {
    val (i, rng0) = rng.nextInt
    val (d, rng1) = double(rng0)
    ((i, d), rng1)
  }
  def doubleInt(rng: RNG): ((Double, Int), RNG) = {
    val (i, rng0) = rng.nextInt
    val (d, rng1) = double(rng0)
    ((d, i), rng1)
  }
  def double3(rng: RNG): ((Double, Double, Double), RNG) = {
    val (a, rngA) = double(rng)
    val (b, rngB) = double(rngA)
    val (c, rngC) = double(rngB)
    ((a,b,c), rngC)
  }

  // 6.4
  def ints(count: Int)(rng: RNG): (List[Int], RNG) =
    if (count > 0) {
      val (next, rngNext) = rng.nextInt
      val (tail, rngTail) = ints(count - 1)(rngNext)
      (next :: tail, rngTail)
    } else {
      (List(), rng)
    }

  val int: Rand[Int] = _.nextInt


  def unit[A](a: A): Rand[A] = rng => (a, rng)

  def map[A,B](s: Rand[A])(f: A => B): Rand[B] =
    rng => {
      val (a, rng2) = s(rng)
      (f(a), rng2)
    }

  def nonNegativeEven: Rand[Int] = map(nonNegativeInt)(i => i - i % 2)

  // 6.5
  def doubleAgain: Rand[Double] = map(nonNegativeInt)(i => i.toDouble / Int.MaxValue)

  // 6.6
  def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
    rng => {
      val (a, rnga) = ra(rng)
      val (b, rngb) = rb(rnga)
      (f(a,b), rngb)
    }

  // 6.7
  def sequence[A](fs: List[Rand[A]]): Rand[List[A]] =
    fs.foldRight[Rand[List[A]]](rng0  => (List.empty[A], rng0)){ (randA, randListA) => rng0 =>
      val (a, rng1) = randA(rng0)
      val (list: List[A], rng2) = randListA(rng1)
      (a :: list, rng2 )
    }

  // 6.8
  def flatMap[A, B](f: Rand[A])(g: A => Rand[B]): Rand[B] =
    rng => {
      val (a, rng0) = f(rng)
      g(a)(rng0)
    }

  def nonNegativeLessThan(n: Int): Rand[Int] =
    flatMap(nonNegativeInt)({
      case i if i + n - 1 - (i % n) >= 0 => rng => (i, rng)
      case _ => nonNegativeLessThan(n)
    })

  // 6.9


}