Skip to content

Instantly share code, notes, and snippets.

@SethTisue
Created May 6, 2011 23:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SethTisue/960010 to your computer and use it in GitHub Desktop.
Save SethTisue/960010 to your computer and use it in GitHub Desktop.
Seasoned Schemer, chapter 13
// page 37
/*
def intersect[T](set1: List[T], set2: List[T]): List[T] =
set1 match {
case Nil => Nil
case car :: cdr =>
if (set2.contains(car))
car :: intersect(cdr, set2)
else
intersect(cdr, set2)
}
*/
/*
def intersect[T](set1: List[T], set2: List[T]): List[T] = {
def recurse(set: List[T]): List[T] =
set match {
case Nil => Nil
case car :: cdr =>
if (set2.contains(car))
car :: recurse(cdr)
else
recurse(cdr)
}
recurse(set1)
}
*/
// my version using HOF
def intersect[T](set1: List[T], set2: List[T]): List[T] = {
if(set2.isEmpty) Nil
else set1.filter(set2.contains(_))
}
// page 38
/*
def intersectAll[T](sets: List[List[T]]): List[T] = sets match {
case Nil => Nil
case car :: Nil => car
case car :: cdr =>
intersect(car, intersectAll(cdr))
}
*/
/*
def intersectAll[T](sets: List[List[T]]): List[T] = {
def recurse(sets: List[List[T]]): List[T] = sets match {
case car :: Nil => car
case car :: cdr => intersect(car, recurse(cdr))
}
if (sets.isEmpty) Nil
else recurse(sets)
}
*/
/*
// my version using HOF
def intersectAll[T](sets: List[List[T]]): List[T] = {
if (sets.isEmpty) Nil
else sets.reduceLeft(intersect)
}
*/
// page 50
/*
// my version using try/catch
def intersectAll[T](sets: List[List[T]]): List[T] = {
if(sets.isEmpty) Nil
else {
case class Result(x: List[T]) extends Throwable
def A(sets: List[List[T]]): List[T] = sets match {
case Nil :: cdr => throw Result(Nil)
case car :: Nil => car
case car :: cdr => I(car, A(cdr))
case _ => throw new IllegalArgumentException
}
def I(set1: List[T], set2: List[T]): List[T] = {
def J(set: List[T]): List[T] = set match {
case Nil => Nil
case car :: cdr =>
if (!set2.contains(car)) J(cdr)
else car :: J(cdr)
}
if (set2.isEmpty) throw Result(Nil)
else J(set1)
}
try A(sets)
catch { case Result(x) => x }
}
}
*/
/*
// my version using reduceLeft + return.
// (note that this works because return returns from not the innermost
// method, but the innermost *named* method; see SLS 6.20)
def intersectAll[T](sets: List[List[T]]): List[T] = {
sets.reduceLeft{(set1, set2) =>
val next = intersect(set1, set2)
if(next.isEmpty) return Nil
else next
}
}
*/
/*
// this stuff comes from euler/src/Euler.scala
object Seth {
implicit def pimpMyStream[T](s1: Stream[T]): RichStream[T] = new RichStream(s1)
class RichStream[T1](s1: Stream[T1]) {
def scanl1(fn: (T1, T1) => T1): Stream[T1] =
s1.tail.scanl(s1.head)(fn)
def scanl[T2](initial: T2)(fn: (T2, T1) => T2): Stream[T2] =
initial #::
(if(s1.isEmpty) Stream()
else s1.tail.scanl(fn(initial, s1.head))(fn))
def tails: Stream[Stream[T1]] =
if(s1.isEmpty) Stream(Stream())
else s1 #:: s1.tail.tails
}
}
import Seth.pimpMyStream
*/
/*
// first version using Stream + scanl1.
def intersectAll[T](sets: List[List[T]]): List[T] = {
if(sets.isEmpty) Nil
else {
val results = sets.scanl1(intersect)
if(results.contains(Nil)) Nil
else results.last
}
}
*/
/*
// second version using Stream + scanl1.
// a little harder to understand, but avoids any extra passes.
// in theory it ought to be able to run in constant space;
// in Haskell I think it would, in Scala who knows
def intersectAll[T](sets: List[List[T]]): List[T] = {
if(sets.isEmpty) Nil
else sets.scanl1(intersect).tails
.find(xs => xs.tail.isEmpty || xs.head.isEmpty)
.get.head
}
*/
/*
// Oliver's recursive version (his code was in Haskell)
def intersectAll[T](sets: List[List[T]]): List[T] = sets match {
case Nil => Nil
case set :: Nil => set
case Nil :: _ => Nil
case set1 :: set2 :: sets =>
intersectAll(intersect(set1, set2) :: sets)
}
*/
/*
// imperative version
def intersectAll[T](sets: List[List[T]]): List[T] = {
if(sets.isEmpty) Nil
else {
var result :: remaining = sets
while(result.nonEmpty && remaining.nonEmpty) {
result = intersect(result, remaining.head)
remaining = remaining.tail
}
result
}
}
*/
// page 57
/*
// try/catch version, ported directly from the Scheme
// code in the book.
def remberUpToLast[T](x: T, xs: List[T]): List[T] = {
case class Result(x: List[T]) extends Throwable
def R(xs: List[T]): List[T] = xs match {
case Nil => Nil
case x2 :: rest if x == x2 => throw Result(R(rest))
case x2 :: rest => x2 :: R(rest)
}
try R(xs)
catch { case Result(x) => x }
}
*/
object Seth {
implicit def pimpMyList[T](l1: List[T]): RichList[T] = new RichList(l1)
class RichList[T1](l1: List[T1]) {
def tails: Stream[List[T1]] =
if(l1.isEmpty) Stream(Nil)
else l1 #:: l1.tail.tails
}
}
import Seth.pimpMyList
// foldLeft-based solution
/*
def remberUpToLast[T](x: T, xs: List[T]): List[T] =
xs.tails.foldLeft(xs)((result, tail) =>
if(tail.nonEmpty && tail.head == x) tail.tail
else result)
*/
// imperative solution
def remberUpToLast[T](x: T, xs: List[T]): List[T] = {
var (result, rest) = (xs, xs)
while(rest.nonEmpty) {
if(x == rest.head)
result = rest.tail
rest = rest.tail
}
result
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment