Seasoned Schemer, chapter 13

ch13.scala

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