Reading Functional Programing In Scala

ch5_streams.scala

// Excercies from chapter 5: Strictness and laziness

def foldRight[A,B](z: => B)(s: Stream[A])(f: (A, => B) => B): B =
  s match {
    case hd #:: tail => f(hd, foldRight(z)(tail)(f))
    case _ => z
  }

def exists[A](s: Stream[A])(p: A => Boolean): Boolean =
	foldRight(false)(s)((x,a) => if (p(x)) true else a)

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

def map[A,B](s: Stream[A])(f: A => B): Stream[B] =
	unfold(s) ({
		case hd #:: tail => Some (f(hd), tail)
		case _ => None
	})

def take[A](s: Stream[A], n: Int): Stream[A] =
	unfold((n, s)) (v => {
		val (n, s) = (v._1, v._2)
		if (n > 0) {
			s match {
			        case hd #:: tail => Some ((hd, (n - 1, tail)))
				case _ => None
			}
		}
		else None		
	})

def takeWhile[A](s: Stream[A])(p: A => Boolean): Stream[A] =
	unfold(s) ({
		case hd #:: tail => if (p(hd)) Some (hd, tail) else None
		case _ => None
	})

def zip[A,B](s1: Stream[A], s2: Stream[B]): Stream[(A, B)] =
	unfold ((s1, s2)) ({
		case (hd1 #:: tail1, hd2 #:: tail2) =>
			Some ( (hd1, hd2), (tail1, tail2) )
		case _ => None
	})

def zipAll[A,B](s1: Stream[A], s2: Stream[B]): Stream[(Option[A], Option[B])] =
	unfold ((s1, s2)) ({
		case (hd1 #:: tail1, hd2 #:: tail2) => Some ( 
			((Some(hd1), Some(hd2)), (tail1, tail2))
		)
		case (hd1 #:: tail1, _) => Some (
			((Some(hd1), None), (tail1, Stream.empty[B]))
		)
		case (_, hd2 #:: tail2) => Some (
			((None, Some(hd2)) , (Stream.empty[A], tail2))
		)
		case _ => None
	})

def startsWith[A](s1: Stream[A], s2: Stream[A]): Boolean = {
	(s1,s2) match {
		case (hd1 #:: tail1, hd2 #:: tail2) => {
			if (hd1 != hd2) false
			else startsWith(tail1, tail2)
		}
		case (_, hd2 #:: tail2) => false
		case _ => true
	}
}

def tails[A](s: Stream[A]): Stream[Stream[A]] =
	unfold (s) ({
		case hd #:: tail => Some (hd #:: tail, tail)
		case _ => None
	})

def hasSubsequence[A](s1: Stream[A], s2: Stream[A]): Boolean =
	exists(tails(s1)) (tail => startsWith(tail, s2))


// Some concrete examples:
def fib = unfold((BigInt(0), BigInt(1)))(p => Some(p._1, (p._2, p._1 + p._2)) )

fib take 10 toList
//res1: List[scala.math.BigInt] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

hasSubsequence(Stream(1,2,3,4,5,6,7,8,9),Stream(6,7,8))
//res2: Boolean = true