scala - 如何根据 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))(_ < _)