travisbrown · November 13, 2012 22:57 · Nov 13, 2012 · Nov 13, 2012
diff --git a/needle-in-haystack.scala b/needle-in-haystack.scala
@@ -6,7 +6,7 @@
  *
  *     https://groups.google.com/d/msg/shapeless-dev/hn7_U21tupI/Zm9h3uNb51gJ
  *
- * Tested with Scala 2.9.2 and Shapeless 1.2.3.
+ * Tested with Scala 2.9.2 and Shapeless 1.2.3. Should work on 1.2.2 with minor edits.
  */
 
 import shapeless._

diff --git a/needle-in-haystack.scala b/needle-in-haystack.scala
@@ -0,0 +1,82 @@
+/**
+ * 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.
+ */
+
+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