How to split an iterator based on a condition on prev and curr elements?

Question

I want to split a list of elements into a list of lists such that neighboring elements in the inner list satisfy a given condition.

A simple condition would be neighboring elements are equal. Then if the input is List(1,1,1,2,2,3,3,3,3) output is List(List(1,1,1),List(2,2),List(3,3,3)).

Another condition could be current element should be greater than prev element. Then if the input is List(1,2,3,1,4,6,5,7,8), the output is List(List(1,2,3), List(1,4,6), List(5,7,8)). It would also be wonderful if the method can act on Iterator. The typedef of the method is

def method[A](lst:List[A], cond:(A,A)=>Boolean):List[List[A]]
def method[A](lst:Iterator[A], cond:(A,A)=>Boolean):Iterator[Iterator[A]]

Answer 1

You can use sliding together with span in a recursive function for the desired effect. This quick and dirty version is less efficient, but terser than some of the alternative:

def method[A](lst: TraversableOnce[A], cond: (A, A) => Boolean): List[List[A]] = {
    val iterable = lst.toIterable
    iterable.headOption.toList.flatMap { head => 
        val (next, rest) = iterable.sliding(2).filter(_.size == 2).span(x => cond(x.head, x.last))
        (head :: next.toList.map(_.last)) :: method(rest.map(_.last), cond)
    }
}

If you want to lazily execute the code, you can return an Iterator[List[A]] instead of List[List[A]]:

def method[A](lst: TraversableOnce[A], cond: (A, A) => Boolean): Iterator[List[A]] = {
    val iterable = lst.toIterable
    iterable.headOption.toIterator.flatMap { head => 
        val (next, rest) = iterable.sliding(2).filter(_.size == 2).span(x => cond(x.head, x.last))
        Iterator(head :: next.toList.map(_.last)) ++ method(rest.map(_.last), cond)
    }
}  

And you can verify that this is lazy:

val x = (Iterator.range(0, 10) ++ Iterator.range(3, 5) ++ Iterator.range(1, 3)).map(x => { println(x); x })
val iter = method(x, (x: Int, y: Int) => x < y) //Only prints 0-9, and then 3!
iter.take(2).toList //Prints more
iter.toList //Prints the rest

You can make it even lazier by returning an Iterator[Iterator[A]]:

def method[A](lst: TraversableOnce[A], cond: (A, A) => Boolean): Iterator[Iterator[A]] = {
    val iterable = lst.toIterable
    iterable.headOption.toIterator.flatMap { head => 
        val (next, rest) = iterable.sliding(2).filter(_.size == 2).span(x => cond(x.head, x.last))
        Iterator(Iterator(head) ++ next.toIterator.map(_.last)) ++ method(rest.map(_.last), cond)
    }
} 

As a relatively unrelated side note, when you have generic parameters of this form, you're better off using 2 parameter lists:

def method[A](lst: TraversableOnce[A])(cond: (A, A) => Boolean)

When you have 2 parameter lists like this, the type inference can be a little bit smarter:

//No need to specify parameter types on the anonymous function now!
method(List(1, 3, 2, 3, 4, 1, 8, 1))((x, y) => x < y).toList
//You can now even use underscore anonymous function notation!
method(List(1, 4, 2, 3, 4, 1, 8))(_ < _)