如何根据prev和curr元素的条件拆分迭代器？

Question

我想将一个元素列表拆分成一个列表列表,以便内部列表中的相邻元素满足给定条件.

一个简单的条件是相邻元素是相等的.然后,如果输入是List(1,1,1,2,2,3,3,3,3)输出List(List(1,1,1),List(2,2),List(3,3,3)).

另一个条件可能是当前元素应该大于prev元素.然后,如果输入是List(1,2,3,1,4,6,5,7,8),则输出为List(List(1,2,3), List(1,4,6), List(5,7,8)).如果该方法可以采取行动也将是很好的Iterator.方法的typedef是

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

您可以在递归函数中sliding一起使用span以获得所需的效果.这种快速而肮脏的版本效率较低,但比其他选择更为简洁:

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)
    }
}

如果你想懒惰地执行代码,你可以返回一个Iterator[List[A]]而不是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)
    }
}  

你可以验证这是懒惰的:

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

您可以通过返回以下内容使其更加懒散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)
    }
} 

作为一个相对不相关的旁注,当你有这个表格的通用参数时,你最好使用2个参数列表:

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

当你有这样的2个参数列表时,类型推断可以更聪明一些:

//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))(_ < _)