package datastructures

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

val : G[A] = G[B]

val : G[B] = G[A]

val : G[A] = G[B]

val x1: A => AnyRef = B => AnyRef型の値
x1(A型の値)

def tail[A](l: List[A]): List[A] = l match {
    case Nil => Nil
    case Cons(x, xs) = xs
  }

def tail[A](l: List[A]): List[A] = 
  l match {
    case Nil => sys.error("tail of empty list")
    case Cons(_,t) => t
  }

def setHead[A](l: List[A], h: A): List[A] = l match {
    case Nil => sys.error("setHead of empty list")
    case Cons(_,t) => Cons(h, t)
  }

def drop[A](l: List[A], n: Int): List[A] = n match {
    case m if m < 0 => sys.error("n should be positive.")
    case 0 => l
    case m => l match {
      case Nil => sys.error("drop of empty list")
      case Cons(x, xs) => drop(xs, n - 1)
    }
  }

/* 
Again, it's somewhat subjective whether to throw an exception when asked to drop more elements than the list contains. The usual default for `drop` is not to throw an exception, since it's typically used in cases where this is not indicative of a programming error. If you pay attention to how you use `drop`, it's often in cases where the length of the input list is unknown, and the number of elements to be dropped is being computed from something else. If `drop` threw an exception, we'd have to first compute or check the length and only drop up to that many elements.  
*/
def drop[A](l: List[A], n: Int): List[A] = 
  if (n <= 0) l
  else l match {
    case Nil => Nil
    case Cons(_,t) => drop(t, n-1) 
  }

def init[A](l: List[A]): List[A] = l match {
    case Nil => Nil
    case Cons(x, Nil) => Nil
    case Cons(x, xs) => Cons(x, init(xs))
  }

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))
  }

def dropWhile[A](l :List[A]), f: A => Boolean): List[A]

val xs: List[Int] = List(1,2,3,4,5)
val ex1 = dropWhile(xs, (x: Int) => x < 4)

def dropWhile[A](as: List[A])(f: A => Boolean): List[A] =
  as match {
    case Cons(h, t) if(h) => dropWhile(t)(f)
    case _ => as

val xs: List[Int] = List(1,2,3,4,5)
val ex1 = dropWhile(xs)(x => x < 4)

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

def reverse[A](l: List[A]): List[A] =
    foldLeft(l, Nil: List[A])((b, a) => a match {
      case Nil => b
      case x => Cons(x, b)
    })

def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc,h) => Cons(h,acc))

/*
The implementation of `foldRight` in terms of `reverse` and `foldLeft` is a common trick for avoiding stack overflows when implementing a strict `foldRight` function as we've done in this chapter. (We'll revisit this in a later chapter, when we discuss laziness).

The other implementations build up a chain of functions which, when called, results in the operations being performed with the correct associativity. We are calling `foldRight` with the `B` type being instantiated to `B => B`, then calling the built up function with the `z` argument. Try expanding the definitions by substituting equals for equals using a simple example, like `foldLeft(List(1,2,3), 0)(_ + _)` if this isn't clear. Note these implementations are more of theoretical interest - they aren't stack-safe and won't work for large lists.
*/
def foldRightViaFoldLeft[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
  foldLeft(reverse(l), z)((b,a) => f(a,b))

def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
  foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

// Here is the same function with much more description
def foldLeftViaFoldRight_1[A,B](as: List[A], outerIdent: B)(combiner: (B, A) => B): B = {

  // foldLeft processes items in the reverse order from foldRight.  It's
  // cheating to use reverse() here because that's implemented in terms of
  // foldLeft!  Instead, wrap each operation in a simple identity function to
  // delay evaluation until later and stack (nest) the functions so that the
  // order of application can be reversed.  We'll call the type of this
  // particular identity/delay function BtoB so we aren't writing B => B
  // everywhere:
  type BtoB = B => B

  // Here we declare a simple instance of BtoB according to the above
  // description.  This function will be the identity value for the inner
  // foldRight.
  def innerIdent:BtoB = (b:B) => b

  // For each item in the 'as' list (the 'a' parameter below), make a new
  // delay function which will use the combiner function (passed in above)
  // when it is evaluated later.  Each new function becomes the input to the
  // previous function (delayFunc).
  //
  //                        This much is just the type signature
  //                  ,-------^-------.
  def combinerDelayer:(A, BtoB) => BtoB =
    (a: A, delayFunc: BtoB) => (b:B) => delayFunc(combiner(b, a))
  // `----------v---------'    `----------------v---------------'
  //         Paramaters                 The returned function

  // Pass the original list 'as', plus the simple identity function and the
  // new combinerDelayer to foldRight.  This will create the functions for
  // delayed evaluation with an combiner inside each one, but will not
  // apply any of those functions.
  def go:BtoB = foldRight(as, innerIdent)(combinerDelayer)

  // This forces all the evaluations to take place
  go(outerIdent)
}

/*
Here is a sample run for further illustration purposes
foldLeftViaFoldRight_1(List(1,2,3), Nil:List[Int])((b:B, a:A) => Cons(a, b))

Becomes:
foldRight(List(1,2,3), innerIdent)(combinerDelayer)(Nil)

Becomes:
def delay3(b:B) = innerIdent(combiner(b,  3))
def delay2(b:B) = delay3(combiner(b, 2))
def delay1(b:B) = delay2(combiner(b,  1))
delay1(Nil)

Becomes:
def delay3(b:B) = innerIdent(combiner(b,  3))
def delay2(b:B) = delay3(combiner(b, 2))
delay2(combiner(Nil,  1))

Becomes:
def delay3(b:B) = innerIdent(combiner(b,  3))
delay3(combiner(combiner(Nil,  1), 2))

Becomes:
innerIdent(combiner(combiner(combiner(Nil,  1), 2),  3))

Becomes:
combiner(combiner(combiner(Nil,  1), 2),  3)

Becomes:
combiner(combiner(Cons(1,Nil), 2),  3)

Becomes:
combiner(Cons(2,Cons(1,Nil)),  3)

Becomes:
Cons(3,Cons(2,Cons(1,Nil)))
Voila!



Alternate Route:
def delay3(b:B) = innerIdent(combiner(b,  3))
def delay2(b:B) = delay3(combiner(b, 2))
def delay1(b:B) = delay2(combiner(b,  1))
delay1(Nil)

Becomes:
def delay2(b:B) = innerIdent(combiner(combiner(b, 2),  3))
def delay1(b:B) = delay2(combiner(b,  1))
delay1(Nil)

Equivalent:
def delay1(b:B) = innerIdent(combiner(combiner(combiner(b,  1), 2),  3))
delay1(Nil)

Equivalent:
((b:B) => innerIdent(combiner(combiner(combiner(b,  1), 2),  3)))(Nil)

Equivalent:
innerIdent(combiner(combiner(combiner(Nil,  1), 2),  3))
*/

def append2[A](a1: List[A], a2: List[A]): List[A] =
    foldRight(a1, a2)((a, b) => a match {
      case Nil => b
      case x => Cons(x, b)
    })

def appendViaFoldRight[A](l: List[A], r: List[A]): List[A] = 
  foldRight(l, r)(Cons(_,_))

def flat[A](l: List[List[A]]): List[A] =
    foldRight(l, List[A]())((a, b) => append2(a,b))

/*
Since `append` takes time proportional to its first argument, and this first argument never grows because of the right-associativity of `foldRight`, this function is linear in the total length of all lists. You may want to try tracing the execution of the implementation on paper to convince yourself that this works. 

Note that we're simply referencing the `append` function, without writing something like `(x,y) => append(x,y)` or `append(_,_)`. In Scala there is a rather arbitrary distinction between functions defined as _methods_, which are introduced with the `def` keyword, and function values, which are the first-class objects we can pass to other functions, put in collections, and so on. This is a case where Scala lets us pretend the distinction doesn't exist. In other cases, you'll be forced to write `append _` (to convert a `def` to a function value) or even `(x: List[A], y: List[A]) => append(x,y)` if the function is polymorphic and the type arguments aren't known. 
*/
def concat[A](l: List[List[A]]): List[A] = 
  foldRight(l, Nil:List[A])(append)

def addOne(l: List[Int]): List[Int] =
    foldRight(l, List[Int]())((a: Int, b) => Cons(a + 1, b))

def add1(l: List[Int]): List[Int] = 
  foldRight(l, Nil:List[Int])((h,t) => Cons(h+1,t))

def doubleToString(l: List[Double]): List[String] =
    foldRight(l, List[String]())((a, b) => Cons(a.toString, b))

def doubleToString(l: List[Double]): List[String] = 
  foldRight(l, Nil:List[String])((h,t) => Cons(h.toString,t))

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

/* 
A natural solution is using `foldRight`, but our implementation of `foldRight` is not stack-safe. We can use `foldRightViaFoldLeft` to avoid the stack overflow (variation 1), but more commonly, with our current implementation of `List`, `map` will just be implemented using local mutation (variation 2). Again, note that the mutation isn't observable outside the function, since we're only mutating a buffer that we've allocated. 
*/
def map[A,B](l: List[A])(f: A => B): List[B] = 
  foldRight(l, Nil:List[B])((h,t) => Cons(f(h),t))

def map_1[A,B](l: List[A])(f: A => B): List[B] = 
  foldRightViaFoldLeft(l, Nil:List[B])((h,t) => Cons(f(h),t))

def map_2[A,B](l: List[A])(f: A => B): List[B] = {
  val buf = new collection.mutable.ListBuffer[B]
  def go(l: List[A]): Unit = l match {
    case Nil => ()
    case Cons(h,t) => buf += f(h); go(t)
  }
  go(l)
  List(buf.toList: _*) // converting from the standard Scala list to the list we've defined here
}

def filter[A](as: List[A])(f: A => Boolean): List[A] =
    foldRight(as, List[A]())((h, t) => if (f(h)) Cons(h, t) else t)

/* 
The discussion about `map` also applies here.
*/
def filter[A](l: List[A])(f: A => Boolean): List[A] = 
  foldRight(l, Nil:List[A])((h,t) => if (f(h)) Cons(h,t) else t)

def filter_1[A](l: List[A])(f: A => Boolean): List[A] = 
  foldRightViaFoldLeft(l, Nil:List[A])((h,t) => if (f(h)) Cons(h,t) else t)

def filter_2[A](l: List[A])(f: A => Boolean): List[A] = {
  val buf = new collection.mutable.ListBuffer[A]
  def go(l: List[A]): Unit = l match {
    case Nil => ()
    case Cons(h,t) => if (f(h)) buf += h; go(t)
  }
  go(l)
  List(buf.toList: _*) // converting from the standard Scala list to the list we've defined here
}

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

/* 
This could also be implemented directly using `foldRight`.
*/
def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] = 
  concat(map(l)(f))

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

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

def plusEachElement(l1: List[Int], l2: List[Int]): List[Int] = (l1, l2) match {
    case (Cons(h, t), Cons(hh, tt)) => Cons(h + hh, plusEachElement(t, tt))
    case (x, Nil) => x
    case (Nil, x) => x
    case _ => Nil
  }

/* 
To match on multiple values, we can put the values into a pair and match on the pair, as shown next, and the same syntax extends to matching on N values (see sidebar "Pairs and tuples in Scala" for more about pair and tuple objects). You can also (somewhat less conveniently, but a bit more efficiently) nest pattern matches: on the right hand side of the `=>`, simply begin another `match` expression. The inner `match` will have access to all the variables introduced in the outer `match`. 

The discussion about stack usage from the explanation of `map` also applies here.
*/
def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(h1+h2, addPairwise(t1,t2))
}

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

/* 
This function is usually called `zipWith`. The discussion about stack usage from the explanation of `map` also applies here. By putting the `f` in the second argument list, Scala can infer its type from the previous argument list. 
*/
def zipWith[A,B,C](a: List[A], b: List[B])(f: (A,B) => C): List[C] = (a,b) match {
  case (Nil, _) => Nil
  case (_, Nil) => Nil
  case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2), zipWith(t1,t2)(f))
}

def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
    def startsWith(p: List[A], b: List[A]): Boolean = (p, b) match {
      case (Cons(h1, _), Cons(h2, Nil)) if (h1 == h2) => true
      case (Cons(h1, t1), Cons(h2, t2)) if (h1 == h2) => startsWith(t1, t2)
      case _ => false
    }

    (sup, sub) match {
      case (Cons(h1, t1), Cons(_, t2)) => startsWith(sup, sub) || hasSubsequence(t1, sub)
      case _ => false
    }
  }

/*
There's nothing particularly bad about this implementation,
except that it's somewhat monolithic and easy to get wrong.
Where possible, we prefer to assemble functions like this using
combinations of other functions. It makes the code more obviously
correct and easier to read and understand. Notice that in this
implementation we need special purpose logic to break out of our
loops early. In Chapter 5 we'll discuss ways of composing functions
like this from simpler components, without giving up the efficiency
of having the resulting functions work in one pass over the data.

It's good to specify some properties about these functions.
For example, do you expect these expressions to be true?

(xs append ys) startsWith xs
xs startsWith Nil
(xs append ys append zs) hasSubsequence ys
xs hasSubsequence Nil
*/
@annotation.tailrec
def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l,prefix) match {
  case (_,Nil) => true
  case (Cons(h,t),Cons(h2,t2)) if h == h2 => startsWith(t, t2)
  case _ => false
}
@annotation.tailrec
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
  case Nil => sub == Nil
  case _ if startsWith(sup, sub) => true
  case Cons(_,t) => hasSubsequence(t, sub)
}

def size[A](tree: Tree[A]): Int = tree match {
    case Leaf(_) => 1
    case Branch(left, right) => 1 + size(left) + size(right)
  }

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

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

/*
We're using the method `max` that exists on all `Int` values rather than an explicit `if` expression.

Note how similar the implementation is to `size`. We'll abstract out the common pattern in a later exercise. 
*/
def maximum(t: Tree[Int]): Int = t match {
  case Leaf(n) => n
  case Branch(l,r) => maximum(l) max maximum(r)
}

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

/*
Again, note how similar the implementation is to `size` and `maximum`.
*/
def depth[A](t: Tree[A]): Int = t match {
  case Leaf(_) => 0
  case Branch(l,r) => 1 + (depth(l) max depth(r))
}

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

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

"map" should "mapping function on each node" in {
    val leaf1 = Leaf(1)
    val leaf2 = Leaf(2)
    val root = Branch(leaf1,leaf2)

    val mappedTree = map(root)(a => a + a)

    mappedTree match {
      case Branch(l, r) => (l, r) match {
        case (Leaf(lv), Leaf(rv)) => {
          lv shouldEqual 2
          rv shouldEqual 4
        }
        case _ => throw new Exception()
      }
      case _ => throw new Exception()
    }
  }

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

/* 
Like `foldRight` for lists, `fold` receives a "handler" for each of the data constructors of the type, and recursively accumulates some value using these handlers. As with `foldRight`, `fold(t)(Leaf(_))(Branch(_,_)) == t`, and we can use this function to implement just about any recursive function that would otherwise be defined by pattern matching.
*/
def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
  case Leaf(a) => f(a)
  case Branch(l,r) => g(fold(l)(f)(g), fold(r)(f)(g))
}

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

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

def depthViaFold[A](t: Tree[A]): Int = 
  fold(t)(a => 0)((d1,d2) => 1 + (d1 max d2))

/*
Note the type annotation required on the expression `Leaf(f(a))`. Without this annotation, we get an error like this: 

type mismatch;
  found   : fpinscala.datastructures.Branch[B]
  required: fpinscala.datastructures.Leaf[B]
     fold(t)(a => Leaf(f(a)))(Branch(_,_))
                                    ^  

This error is an unfortunate consequence of Scala using subtyping to encode algebraic data types. Without the annotation, the result type of the fold gets inferred as `Leaf[B]` and it is then expected that the second argument to `fold` will return `Leaf[B]`, which it doesn't (it returns `Branch[B]`). Really, we'd prefer Scala to infer `Tree[B]` as the result type in both cases. When working with algebraic data types in Scala, it's somewhat common to define helper functions that simply call the corresponding data constructors but give the less specific result type:  
  
  def leaf[A](a: A): Tree[A] = Leaf(a)
  def branch[A](l: Tree[A], r: Tree[A]): Tree[A] = Branch(l, r)
*/
def mapViaFold[A,B](t: Tree[A])(f: A => B): Tree[B] = 
  fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_,_))

def failingFn(i: Int): Int = {
  val y: Int = throw new Exception("fail!")
  try {
    val x = 42 + 5
    x + y
  }
  catch { case e: Exception => 43 }
}

def failingFn(i: Int): Int = {
  try {
    val x = 42 + 5
    x + ((throw new Exception("fail!"): Int)
  }
  catch { case e: Exception => 43 }
}

sealed trait Option[+A] {
  def map[B](f: A => B): Option[B] = this match {
    case None => None
    case Some(a) => Some(f(a))
  }
  def flatMap[B](f: A => Option[B]): Option[B] = map(f).getOrElse(None: Option[B])
  def getOrElse[B >: A](default: => B): B = this match {
    case None => default
    case Some(a) => a
  }
  def orElse[B >: A](ob: => Option[B]): Option[B] = map(Some(_)).getOrElse(ob)
  def filter(f: A => Boolean): Option[A] = flatMap(a => if (f(a)) Some(a) else None)
}

def map[B](f: A => B): Option[B] = this match {
  case None => None
  case Some(a) => Some(f(a))
}

def getOrElse[B>:A](default: => B): B = this match {
  case None => default
  case Some(a) => a
}

def flatMap[B](f: A => Option[B]): Option[B] = 
  map(f) getOrElse None

/*
Of course, we can also implement `flatMap` with explicit pattern matching.
*/
def flatMap_1[B](f: A => Option[B]): Option[B] = this match {
  case None => None
  case Some(a) => f(a)
}

def orElse[B>:A](ob: => Option[B]): Option[B] = 
  this map (Some(_)) getOrElse ob

/*
Again, we can implement this with explicit pattern matching. 
*/
def orElse_1[B>:A](ob: => Option[B]): Option[B] = this match {
  case None => ob 
  case _ => this
}

/*
This can also be defined in terms of `flatMap`.
*/
def filter_1(f: A => Boolean): Option[A] =
  flatMap(a => if (f(a)) Some(a) else None)

/* Or via explicit pattern matching. */  
def filter(f: A => Boolean): Option[A] = this match {
  case Some(a) if f(a) => this
  case _ => None
}

def variance(xs: Seq[Double]): Option[Double] = Some(xs).flatMap(s =>
    if (d.isEmpty) None
    else {
      val m = s.sum / s.length
      s.foldLeft(0)((acc, x) => acc + scala.math.pow(x - m, 2)) / s.length
    }
  )

def variance(xs: Seq[Double]): Option[Double] = 
  mean(xs) flatMap (m => mean(xs.map(x => math.pow(x - m, 2))))

def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
    a.flatMap(av => b.map(bv => f(av, bv)))

// a bit later in the chapter we'll learn nicer syntax for 
// writing functions like this
def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
  a flatMap (aa => b map (bb => f(aa, bb)))

def sequence[A](a: List[Option[A]]): Option[List[A]] =
    a.foldRight(Some(List[A]()): Option[List[A]])((aa, b) => b.flatMap(bb => aa.map(aaa => aaa +: bb)))

/*
Here's an explicit recursive version:
*/
def sequence[A](a: List[Option[A]]): Option[List[A]] =
  a match {
    case Nil => Some(Nil)
    case h :: t => h flatMap (hh => sequence(t) map (hh :: _))
  }
/*
It can also be implemented using `foldRight` and `map2`. The type annotation on `foldRight` is needed here; otherwise Scala wrongly infers the result type of the fold as `Some[Nil.type]` and reports a type error (try it!). This is an unfortunate consequence of Scala using subtyping to encode algebraic data types.
*/
def sequence_1[A](a: List[Option[A]]): Option[List[A]] =
  a.foldRight[Option[List[A]]](Some(Nil))((x,y) => map2(x,y)(_ :: _))

def traverse[A,B](a: List[A])(f: A => Option[B]): Option[List[B]] =
    a.foldRight(Some(Nil))((aa, b) => map2(f(aa), b)(_ :: _))

def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] =
  a match {
    case Nil => Some(Nil)
    case h::t => map2(f(h), traverse(t)(f))(_ :: _)
  }

def traverse_1[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] =
  a.foldRight[Option[List[B]]](Some(Nil))((h,t) => map2(f(h),t)(_ :: _))

def sequenceViaTraverse[A](a: List[Option[A]]): Option[List[A]] =
  traverse(a)(x => x)

def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
  for {
    aa <- a
    bb <- b
  } yield f(aa, bb)

sealed trait Either[+E, +A]
case class Left[+E](value: E) extends Either[E, Nothing]
case Right[+A](value) extends Either[Nothing, A]

sealed trait Either[+E, +A] {
  def map[B](f: A => B): Either[E, B] = this match {
    case Left(value) => Left(value)
    case Right(value) => Right(f(value))
  }

  def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match {
    case Left(e) => Left(e)
    case Right(a) => f(a)
  }

  def orElse[EE >: E, B >: A](b: => Either[EE, B]): Either[EE, B] = this match {
    case Left(_) => b
    case Right(a) => Right(a)
  }
  
  def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] =
    flatMap(a => b.map(bb => f(a, b)))
}

def map[B](f: A => B): Either[E, B] = 
  this match {
    case Right(a) => Right(f(a))
    case Left(e) => Left(e)
  }
  
def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] =
  this match {
    case Left(e) => Left(e)
    case Right(a) => f(a)
  }
def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] =
  this match {
    case Left(_) => b
    case Right(a) => Right(a)
  }
def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): 
  Either[EE, C] = for { a <- this; b1 <- b } yield f(a,b1)

def sequence[E, A](es: List[Either[E, A]]): Either[E, List[A]] =
    es.foldRight(Right(List[A]()): Either[E, List[A]])((a, b) => a.map2(b)((aa, bb) => aa +: bb))

  def traverse[E, A, B](as: List[A])(f: A => Either[E, B]): Either[E, List[B]] =
    as.foldRight(Right(List[B]()): Either[E, List[A]])((a, b) => f(a).map2(b)(_ :: _))

def traverse[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
  es match {
    case Nil => Right(Nil)
    case h::t => (f(h) map2 traverse(t)(f))(_ :: _)
  }

def traverse_1[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
  es.foldRight[Either[E,List[B]]](Right(Nil))((a, b) => f(a).map2(b)(_ :: _))

def sequence[E,A](es: List[Either[E,A]]): Either[E,List[A]] = 
  traverse(es)(x => x)

/*
There are a number of variations on `Option` and `Either`. If we want to accumulate multiple errors, a simple approach is a new data type that lets us keep a list of errors in the data constructor that represents failures:

trait Partial[+A,+B]
case class Errors[+A](get: Seq[A]) extends Partial[A,Nothing]
case class Success[+B](get: B) extends Partial[Nothing,B]

There is a type very similar to this called `Validation` in the Scalaz library. You can implement `map`, `map2`, `sequence`, and so on for this type in such a way that errors are accumulated when possible (`flatMap` is unable to accumulate errors--can you see why?). This idea can even be generalized further--we don't need to accumulate failing values into a list; we can accumulate values using any user-supplied binary function. 

It's also possible to use `Either[List[E],_]` directly to accumulate errors, using different implementations of helper functions like `map2` and `sequence`.
*/

def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A =
  if (cond) onTrue() else onFalse()

$ if (a > 22,
        () => println("a"),
        () => println("b")
)

def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A =
  if (cond) onTrue else onFalse

def maybeTwice(b: Boolean, i: => Int) = {
  lazy val j = i
  if (b) j+j else 0
}

trait Stream[+A]
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }
  def empty[A]: Stream[A] = Empty

  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty
    else cons(as.head, apply(as.tail: _*))
}

trait Stream[+A] {
  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(h, t) => Some(h())
  }
}

val x = Cons(() => expensive(x), tl)
val h1 = x.headOption
val h2 = x.headOption

def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }

// The natural recursive solution
def toListRecursive: List[A] = this match {
  case Cons(h,t) => h() :: t().toListRecursive
  case _ => List()
}

/*
The above solution will stack overflow for large streams, since it's
not tail-recursive. Here is a tail-recursive implementation. At each
step we cons onto the front of the `acc` list, which will result in the
reverse of the stream. Then at the end we reverse the result to get the
correct order again.
[:ben] are the line breaks above okay? I'm unclear on whether these "hints" are supposed to go in the book or not
*/
def toList: List[A] = {
  @annotation.tailrec
  def go(s: Stream[A], acc: List[A]): List[A] = s match {
    case Cons(h,t) => go(t(), h() :: acc)
    case _ => acc
  }
  go(this, List()).reverse
}

/* 
In order to avoid the `reverse` at the end, we could write it using a
mutable list buffer and an explicit loop instead. Note that the mutable
list buffer never escapes our `toList` method, so this function is
still _pure_.
*/
def toListFast: List[A] = {
  val buf = new collection.mutable.ListBuffer[A] 
  @annotation.tailrec
  def go(s: Stream[A]): List[A] = s match {
    case Cons(h,t) =>
      buf += h()
      go(t())
    case _ => buf.toList
  }
  go(this)
}

def take(n: Int): List[A] = this match {
    case Cons(h, t) if (n <= 1) => List(h())
    case Cons(h, t) => h() :: t().take(n - 1)
    case _ => List()
  }

  def drop(n: Int): Stream[A] = this match {
    case Cons(h, t) if (n < 1) => this
    case Cons(h, t) => t().drop(n - 1)
    case _ => Empty
  }

/*
`take` first checks if n==0. In that case we need not look at the stream at all.
*/
def take(n: Int): Stream[A] = this match {
  case Cons(h, t) if n > 1 => cons(h(), t().take(n - 1))
  case Cons(h, _) if n == 1 => cons(h(), empty)
  case _ => empty
}


/*
Unlike `take`, `drop` is not incremental. That is, it doesn't generate the
answer lazily. It must traverse the first `n` elements of the stream eagerly.
*/
@annotation.tailrec
final def drop(n: Int): Stream[A] = this match {
  case Cons(_, t) if n > 0 => t().drop(n - 1)
  case _ => this
}

def takeWhile(p: A => Boolean): Stream[A] = this match {
    case Cons(h, t) if (p(h())) => cons(h(), t().takeWhile(p))
    case _ => Empty
  }

/*
It's a common Scala style to write method calls without `.` notation, as in `t() takeWhile f`.  
*/
def takeWhile(f: A => Boolean): Stream[A] = this match { 
  case Cons(h,t) if f(h()) => cons(h(), t() takeWhile f)
  case _ => empty 
}

def forAll(p: A => Boolean): Boolean =
    foldRight(true)((a, b) => b && p(a))

/* 
Since `&&` is non-strict in its second argument, this terminates the traversal as soon as a nonmatching element is found. 
*/
def forAll(f: A => Boolean): Boolean =
  foldRight(true)((a,b) => f(a) && b)

package laziness

import org.scalatest._
import laziness.Stream._
import laziness.{Stream,Cons,Empty}

class StreamSpec extends FlatSpec with Matchers {
  "forAll" should "forAll" in {
    val s = Stream.apply(1,2,3,4,5)

    s.forAll(n => n < 3) shouldEqual false
  }
}

def forAll(p: A => Boolean): Boolean =
    foldRight(true)((a, b) => {
      p(a) && {
        println(a)
        b
      }
    })

$ [info] Compiling 1 Scala source to /workspace/target/scala-2.12/classes ...
$ [info] Done compiling.
$ 1
$ 2

def takeWhileViaFoldRight(p: A => Boolean): Stream[A] =
    foldRight(empty[A])((a, b) => if(p(a)) cons(a, b) else b)

def takeWhile_1(f: A => Boolean): Stream[A] =
  foldRight(empty[A])((h,t) => 
    if (f(h)) cons(h,t)
    else      empty)

def headOptionViaFoldRight: Option[A] =
    foldRight(None: Option[A])((a, b) => Some(a))

def headOption: Option[A] =
  foldRight(None: Option[A])((h,_) => Some(h))

def map[B](f: A => B): Stream[B] =
    foldRight(empty: Stream[B])((h, t) => cons(f(h), t))

  def filter(f: A => Boolean): Stream[A] =
    foldRight(empty[A])((h, t) => if (f(h)) cons(h, t) else t)

  def append[AA >: A](s: Stream[AA]): Stream[AA] =
    foldRight(s)((h, t) => cons(h, t))

  def flatMap[B](f: A => Stream[B]): Stream[B] =
    foldRight(empty: Stream[B])((h, t) => f(h).append(t))

def map[B](f: A => B): Stream[B] =
  foldRight(empty[B])((h,t) => cons(f(h), t)) 

def filter(f: A => Boolean): Stream[A] =
  foldRight(empty[A])((h,t) => 
    if (f(h)) cons(h, t)
    else t) 

def append[B>:A](s: => Stream[B]): Stream[B] = 
  foldRight(s)((h,t) => cons(h,t))

def flatMap[B](f: A => Stream[B]): Stream[B] = 
  foldRight(empty[B])((h,t) => f(h) append t)

def constant[A](a: A): Stream[A] = cons(a, constant(a))

// This is more efficient than `cons(a, constant(a))` since it's just
// one object referencing itself.
def constant[A](a: A): Stream[A] = {
  lazy val tail: Stream[A] = Cons(() => a, () => tail) 
  tail
}

def from(n: Int): Stream[Int] = cons(n, from(n + 1))

def from(n: Int): Stream[Int] =
  cons(n, from(n+1))

def fibs(): Stream[Int] = {
    def go(p1: Int, p2: Int): Stream[Int] = {
      lazy val cur = p1 + p2
      cons(cur, go(cur, p1))
    }
    cons(0, go(0, 1))
  }

val fibs = {
  def go(f0: Int, f1: Int): Stream[Int] = 
    cons(f0, go(f1, f0+f1))
  go(0, 1)
}

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
    f(z).map {
      case (a, s) => cons(a, unfold(s)(f))
    }.getOrElse(empty)

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
  f(z) match {
    case Some((h,s)) => cons(h, unfold(s)(f))
    case None => empty
  }

val fibsViaUnfold = {
    unfold((0, 1)){
      case (i1, i2) => Some((i1, (i2, i1 + i2)))
    }
  }

def fromViaUnfold(n: Int): Stream[Int] =
    unfold(n)(s => Some((s, s + 1)))

def constantViaUnfold[A](a: A): Stream[A] =
    unfold(a)(aa => Some(aa, aa))

val ones: Stream[Int] = unfold(1)(i => Some(1, 1))

/*
Scala provides shorter syntax when the first action of a function literal is to match on an expression.  The function passed to `unfold` in `fibsViaUnfold` is equivalent to `p => p match { case (f0,f1) => ... }`, but we avoid having to choose a name for `p`, only to pattern match on it.
*/
val fibsViaUnfold = 
  unfold((0,1)) { case (f0,f1) => Some((f0,(f1,f0+f1))) }

def fromViaUnfold(n: Int) = 
  unfold(n)(n => Some((n,n+1)))

def constantViaUnfold[A](a: A) = 
  unfold(a)(_ => Some((a,a)))

// could also of course be implemented as constant(1)
val onesViaUnfold = unfold(1)(_ => Some((1,1)))

def mapViaUnfold[B](f: A => B): Stream[B] =
    unfold(this)(s => s match {
      case Cons(h, t) => Some((f(h()), t()))
      case _ => None
    })

  def takeViaUnfold(n: Int): Stream[A] =
    unfold(this) {
      case Cons(h, t) if 0 < n => Some((h(), t().takeViaUnfold(n - 1)))
      case _ => None
    }

  def takeWhileViaUnfold(f: A => Boolean): Stream[A] =
    unfold(this) {
      case Cons(h, t) if (f(h())) => Some((h(), t().takeWhileViaUnfold(f)))
      case _ => None
    }

  def zipWith[B, C](s: Stream[B])(f: (A, B) => C): Stream[C] =
    unfold((this, s)) {
      case (Cons(h, t), Cons(hh, tt)) => Some((f(h(), hh()), (t(), tt())))
      case _ => None
    }

  def zipAll[B](s2: Stream[B]): Stream[(Option[A], Option[B])] =
    unfold((this, s2)) {
      case (Cons(h, t), Cons(hh, tt)) => Some(((Some(h()), Some(hh())), (t(), tt())))
      case (Cons(h, t), _) => Some(((Some(h()), None), (t(), empty)))
      case (_, Cons(h, t)) => Some(((None, Some(h())), (empty, t())))
      case _ => None
    }

def mapViaUnfold[B](f: A => B): Stream[B] =
  unfold(this) {
    case Cons(h,t) => Some((f(h()), t()))
    case _ => None
  }

def takeViaUnfold(n: Int): Stream[A] =
  unfold((this,n)) {
    case (Cons(h,t), 1) => Some((h(), (empty, 0)))
    case (Cons(h,t), n) if n > 1 => Some((h(), (t(), n-1)))
    case _ => None
  }

def takeWhileViaUnfold(f: A => Boolean): Stream[A] =
  unfold(this) {
    case Cons(h,t) if f(h()) => Some((h(), t()))
    case _ => None
  }

def zipWith[B,C](s2: Stream[B])(f: (A,B) => C): Stream[C] =
  unfold((this, s2)) {
    case (Cons(h1,t1), Cons(h2,t2)) =>
      Some((f(h1(), h2()), (t1(), t2())))
    case _ => None
  }

// special case of `zipWith`
def zip[B](s2: Stream[B]): Stream[(A,B)] =
  zipWith(s2)((_,_))


def zipAll[B](s2: Stream[B]): Stream[(Option[A],Option[B])] =
  zipWithAll(s2)((_,_))

def zipWithAll[B, C](s2: Stream[B])(f: (Option[A], Option[B]) => C): Stream[C] =
  Stream.unfold((this, s2)) {
    case (Empty, Empty) => None
    case (Cons(h, t), Empty) => Some(f(Some(h()), Option.empty[B]) -> (t(), empty[B]))
    case (Empty, Cons(h, t)) => Some(f(Option.empty[A], Some(h())) -> (empty[A] -> t()))
    case (Cons(h1, t1), Cons(h2, t2)) => Some(f(Some(h1()), Some(h2())) -> (t1() -> t2()))
  }

def takeViaUnfold(n: Int): Stream[A] =
    unfold(this) {
      case Cons(h, t) if 0 < n => Some((h(), t().takeViaUnfold(n - 1)))
      case _ => None
    }

def takeViaUnfold(n: Int): Stream[A] =
  unfold((this,n)) {
    case (Cons(h,t), 1) => Some((h(), (empty, 0)))
    case (Cons(h,t), n) if n > 1 => Some((h(), (t(), n-1)))
    case _ => None
  }

def startsWith[A](s: Stream[A]): Boolean =
  zipAll(s).forAll {
    case (s1, s2) => (s1.nonEmpty && s2.isEmpty) || (s1.nonEmpty && s2.nonEmpty && s1.get == s2.get)
  }

/* 
`s startsWith s2` when corresponding elements of `s` and `s2` are all equal, until the point that `s2` is exhausted. If `s` is exhausted first, or we find an element that doesn't match, we terminate early. Using non-strictness, we can compose these three separate logical steps--the zipping, the termination when the second stream is exhausted, and the termination if a nonmatching element is found or the first stream is exhausted.
*/
def startsWith[A](s: Stream[A]): Boolean = 
  zipAll(s).takeWhile(!_._2.isEmpty) forAll {
    case (h,h2) => h == h2
  }

def tails: Stream[Stream[A]] =
    unfold(this) {
      case Cons(h, t) => Some(cons(h(), t()), t())
      case _ => None
    }

/*
The last element of `tails` is always the empty `Stream`, so we handle this as a special case, by appending it to the output.
*/
def tails: Stream[Stream[A]] =
  unfold(this) {
    case Empty => None
    case s => Some((s, s drop 1))
  } append Stream(empty)