For a given list, returns all the possible partitions of that list.

Partitions.scala

type Partition[A] = List[List[A]]

def partitions[A](xs: List[A]): List[Partition[A]] = l match {
  case Nil => Nil
  case h :: Nil => List(List(List(h)))
  case h :: t => 
    val ps = partitions(t)
    ps.map(List(h) :: _) ::: ps.flatMap(interpolate(h, _))
}

private def interpolate[A](item: A, partition: Partition[A]): List[Partition[A]] = interpolateAcc(item, partition, Nil)

private def interpolateAcc[A](item: A, partition: Partition[A], prev: Partition[A]): List[Partition[A]] = partition match {
  case Nil => Nil
  case h :: t => (prev ::: ((item :: h) :: t)) :: interpolateAcc(item, t, prev :+ h)
}