yankov
10/25/2013 - 10:25 PM

## Reading Functional Programing In 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``````