Scala implementation of @rolfl's integer-partitioning algorithm
Keep in mind that I likely know less about scala than you and that this is my first review ;)


  Is there a way to write topUp without explicit recursion, yet still avoiding ::: concatenation?


I don't think so, but I may be wrong.


  Is the : Option[Sum] type annotation on Some(List.fill(n)(1)) avoidable?


Yes! You can use the Option type constructor like this:

Iterator.iterate(Option(List.fill(n)(1)))(advance)



  There seems to be a lot of Option / None / Some noise in advance. Is there a better way to handle the termination condition? (Perhaps by using lift?)


I think so, but not with lift. This just uses the standard map and filter (please let me know if this is incorrect logic).

def advance(partition: Option[Sum]): Option[Sum] =
   partition.filter(_.size &gt; 1)
            .map(p =&gt; topUp(p.head - 1, p.tail.head + 1 :: p.tail.tail))



  Similarly, Iterator.iterate(…)(…).takeWhile(! _.isEmpty).map(_.get) seems cumbersome. Is there a less verbose way to say "repeatedly apply this function until exhausted" using the standard Scala library?


I really don't know.

One minor point. Here

Iterator.iterate(Some(List.fill(n)(1)): Option[Sum])(advance)
        .takeWhile(! _.isEmpty)
        .map(_.get)


You use ! _.isEmpty, but option has a perfect method for you, isDefined.