Digging through arbitrarily nested case classes, tuples, and lists

needle-in-haystack.scala

/**
 * Digging through arbitrarily nested case classes, tuples, and lists
 * by Travis Brown
 *
 * In response to this question by Channing Walton on the Shapeless dev list:
 *
 *     https://groups.google.com/d/msg/shapeless-dev/hn7_U21tupI/Zm9h3uNb51gJ
 *
 * Tested with Scala 2.9.2 and Shapeless 1.2.3. Should work on 1.2.2 with minor edits.
 */

import shapeless._

// Our type class:
trait Searchable[A, Q] {
  def find(p: Q => Boolean)(a: A): Option[Q]
}

// Our instances:
implicit def elemSearchable[A] = new Searchable[A, A] {
  def find(p: A => Boolean)(a: A) = if (p(a)) Some(a) else None
}

implicit def listSearchable[A, Q](implicit s: Searchable[A, Q]) =
  new Searchable[List[A], Q] {
    def find(p: Q => Boolean)(a: List[A]) = a.flatMap(s.find(p)).headOption
  }

implicit def hnilSearchable[Q] = new Searchable[HNil, Q] {
  def find(p: Q => Boolean)(a: HNil) = None
}

implicit def hlistSearchable[H, T <: HList, Q](
  implicit hs: Searchable[H, Q] = null, ts: Searchable[T, Q]
) = new Searchable[H :: T, Q] {
  def find(p: Q => Boolean)(a: H :: T) =
    Option(hs).flatMap(_.find(p)(a.head)) orElse ts.find(p)(a.tail)
}

implicit def hlistishSearchable[A, L <: HList, Q](
  implicit iso: Iso[A, L], s: Searchable[L, Q]
) = new Searchable[A, Q] {
  def find(p: Q => Boolean)(a: A) = s.find(p)(iso to a)
}

// A wrapper class and converter for convenience: 
case class SearchableWrapper[A](a: A) {
  def deepFind[Q](p: Q => Boolean)(implicit s: Searchable[A, Q]) =
    s.find(p)(a)
}

implicit def wrapSearchable[A](a: A) = SearchableWrapper(a)

// An example predicate:
val p = (_: String) endsWith "o"

// On strings:
"hello".deepFind(p) == Some("hello")
"hell".deepFind(p) == None

// On lists:
List("yes", "maybe", "no").deepFind(p) == Some("no")

// On arbitrarily sized and nested tuples:
("yes", "maybe", ("no", "why")).deepFind(p) == Some("no")
("a", ("b", "c"), "d").deepFind(p) == None

// On tuples with non-string elements:
(1, "two", ('three, '4')).deepFind(p) == Some("two")

// Search the same tuple for a specific character instead:
(1, "two", ('three, '4')).deepFind((_: Char) == 52) == Some('4')

// Our case class:
case class Foo(a: String, b: String, c: List[String])

// Plus one line of boilerplate:
implicit def fooIso = Iso.hlist(Foo.apply _, Foo.unapply _)

// And it works:
Foo("four", "three", List("two", "one")).deepFind(p) == Some("two")
Foo("a", "b", "c" :: Nil).deepFind(p) == None