Scala - 增加序列的前綴

Question

我想知道獲取給定序列的增加前綴的最優雅方式是什麼。我的想法是如下，但它不是純粹的功能性或優雅：

val sequence = Seq(1,2,3,1,2,3,4,5,6) 
var currentElement = sequence.head - 1 
val increasingPrefix = sequence.takeWhile(e => 
      if (e > currentElement) { 
       currentElement = e 
       true 
      } else 
       false) 

上述結果是：

List(1,2,3) 

Answer 1

您可以將您的解決方案@Samlik有效地壓縮到currentElement變量中，然後在完成後將其映射出來。

sequence.take(1) ++ sequence.zip(sequence.drop(1)). 
    takeWhile({case (a, b) => a < b}).map({case (a, b) => b}) 

而且具有無限序列的工作原理：

val sequence = Seq(1, 2, 3).toStream ++ Stream.from(1) 

sequence現在是一個無限Stream，但我們可以在第一10個項目偷看：

scala> sequence.take(10).toList 
res: List[Int] = List(1, 2, 3, 1, 2, 3, 4, 5, 6, 7) 

現在，使用上面的代碼片段：

val prefix = sequence.take(1) ++ sequence.zip(sequence.drop(1)). 
    takeWhile({case (a, b) => a < b}).map({case (a, b) => b}) 

同樣，prefix是Stream，但不是無限的。

scala> prefix.toList 
res: List[Int] = List(1, 2, 3) 

N.b：這不處理的情況下，當sequence是空的，或者前綴也是無限的。

Answer 2

如果優雅你的意思是簡潔和不言自明的，它可能像下面這樣：

sequence.inits.dropWhile(xs => xs != xs.sorted).next 

inits給了我們時間最長的第一返回前綴的迭代器。我們刪除所有未排序的內容並進行下一個。

如果你不想做這一切的排序，你可以寫這樣的事情：

sequence.scanLeft(Some(Int.MinValue): Option[Int]) { 
    case (Some(last), i) if i > last => Some(i) 
    case _ => None 
}.tail.flatten 

如果此操作的性能是非常重要的，雖然（它可能不是），你因爲這個解決方案仍然遍歷整個集合（兩次），所以我想要使用更重要的東西。

Answer 3

我會將優雅解釋爲最接近我們人類思考問題的方式，儘管極其高效的算法也可能是一種優雅的形式。

val sequence = List(1,2,3,2,3,45,5) 
val increasingPrefix = takeWhile(sequence, _ < _) 

我相信這個代碼片段捕捉了我們大多數人可能會考慮解決這個問題的方法。

當然需要定義takeWhile：

/** 
* Takes elements from a sequence by applying a predicate over two elements at a time. 
* @param xs The list to take elements from 
* @param f The predicate that operates over two elements at a time 
* @return This function is guaranteed to return a sequence with at least one element as 
*   the first element is assumed to satisfy the predicate as there is no previous 
*   element to provide the predicate with. 
*/ 
def takeWhile[A](xs: Traversable[A], f: (Int, Int) => Boolean): Traversable[A] = { 
    // function that operates over tuples and returns true when the predicate does not hold 
    val not = f.tupled.andThen(!_) 
    // Maybe one day our languages will be better than this... (dependant types anyone?) 
    val twos = sequence.sliding(2).map{case List(one, two) => (one, two)} 
    val indexOfBreak = twos.indexWhere(not) 
    // Twos has one less element than xs, we need to compensate for that 
    // An intuition is the fact that this function should always return the first element of 
    // a non-empty list 
    xs.take(i + 1) 
} 

Answer 4

而且，另一種方法對皮膚的貓：

val sequence = Seq(1,2,3,1,2,3,4,5,6) 
sequence.head :: sequence 
        .sliding(2) 
        .takeWhile{case List(a,b) => a <= b} 
        .map(_(1)).toList 
// List[Int] = List(1, 2, 3)