Type based collection partitioning in Scala

An "immutable" solution would use your mutable solution except not show you the collections. I'm not sure there's a strong reason to think it's okay if library designers do it but anathema for you. However, if you want to stick to purely immutable constructs, this is probably about as good as it gets:

def segregate4(basket: Set[Fruit]) = {
  val apples = basket.collect{ case a: Apple => a }
  val pears = basket.collect{ case p: Pear => p }
  (apples, pears)
}

  val emptyBaskets: (List[Apple], List[Pear]) = (Nil, Nil)

  def separate(fruits: List[Fruit]): (List[Apple], List[Pear]) = {
    fruits.foldRight(emptyBaskets) { case (f, (as, ps)) =>
      f match {
        case a @ Apple(_, _) => (a :: as, ps)
        case p @ Pear(_, _)  => (as, p :: ps)
      }
    }
  }