在scala中的一次迭代中實現遍歷函數

它將Option的列表組合到一個Option中，其中包含原始列表中所有Some值的列表。如果原始列表甚至包含一次None，則函數的結果應該是None，否則結果應該是Some以及所有值的列表。簽名是在scala中的一次迭代中實現遍歷函數

def sequence[A](a: List[Option[A]]): Option[List[A]]

我想出了以下解決方案

def sequence[A](l: List[Option[A]]): Option[List[A]] = { 
    if (l.exists(_.isEmpty)) None 
    else Some(l.map(_.get)) 
}

這似乎並沒有完美可言，因爲它迭代列表，並兩次施加f功能元素的平均50％。

來源

2015-08-09 zapadlo

非功能性風格的快速失敗：

def sequence[A](xs: List[Option[A]]): Option[List[A]] = 
    Some(xs map (_.getOrElse(return None))) //this return (inside lambda) is implemented with exception in scala

遞歸之一：

def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match { 
    case Nil => None //or `Some(Nil)` 
    case None :: tail => None 
    case Some(head) :: Nil => Some(head :: Nil) 
    case Some(head) :: tail => sequence(tail).map(head :: _) 
}

Vector-based N（not 1。5 * N）的步驟，但沒有快速失敗：

def sequence[A](xs: Vector[Option[A]]): Option[Vector[A]] = 
    Some(xs.flatten) filter (_.size == xs.size) //getting size is fast for vector

Vector + view基於快速失敗：

//`view` doesn't create intermidiate collection and applies everything in one iteration 
def sequence[A](xs: Vector[Option[A]]): Option[Seq[A]] = 
    Some(xs.view.takeWhile(_.nonEmpty).map(_.get).force) filter (_.size == xs.size)

總之，只有性能測試會告訴你效力的真正在這裏。所有這些算法（包括你的）都是線性的O（N），它是你可以得到的最好的複雜度。所以，進一步的優化可能不值得。

來源

2015-08-09 10:31:48 dk14

這裏有一個可能性：

import scala.annotation.tailrec 

def sequence[A](a: List[Option[A]]): Option[List[A]] = { 
    @tailrec 
    def seq(remaining: List[Option[A]], result: Option[List[A]]): Option[List[A]] = { 
    if (remaining.isEmpty) { 
     result 
    } else { 
     (remaining.head, result) match { 
     case (Some(item), Some(list)) => seq(remaining.tail, Some(item :: list)) 
     case _ => None 
     }  
    } 
    } 

    seq(a, Some(Nil)) 
}

，因爲它擊中了第一None元素，它會很快停止評估名單。並且應該返回與實現相同的結果。但是，注意這個實現對於空輸入列表將返回Some（Nil）非常重要。

的實施可以縮短一點，這取決於你對錶現和其他可讀性標準的偏好：

def sequence[A](a: List[Option[A]]): Option[List[A]] = { 
    @tailrec 
    def seq(remaining: List[Option[A]], result: Option[List[A]]): Option[List[A]] = { 
     (remaining, result) match { 
     case (Nil, _) => result 
     case (Some(item) :: tail, Some(list)) => seq(tail, Some(item :: list)) 
     case _ => None 
     } 
    } 

    seq(a, Some(Nil)) 
}

結果將Some單子或None。如果您想保留列表順序，你將不得不

取代seq(a, Some(Nil))與seq(a, Some(Nil)).map(_.reverse)
或list :+ item更換item :: list。

雖然，list :+ item不追加項目的List的最佳方式。如果您想保留訂單並使用'@tailrec'方法，我建議您使用Vector作爲結果類型，而不是List。

來源

2015-08-09 09:16:28

您對結果缺少'.map（_。reverse）'。你也可以將兩個'None'匹配情況合併爲_ _> None，並將它們放在'Some'情況之後。 – Arjan

編輯我的答案與關於列表順序的評論。然而，如果我申請你的第二個建議，我不得不放棄'@ tailrec'，would'nt I. –

不，要成爲尾部遞歸，recusrive調用不必在最新的匹配語句中，只是該特定情況下的最後一項陳述。 – Arjan

def sequence[A](xs: List[Option[A]]): Option[List[A]] = xs match { 
    case x :: xs => // Get one element at a time (Opton[A]) 
     for { 
      a <- x // unwrap the Option[A] to A 
      as <- sequence(xs) // Unwrap the recursive result of Option[List[A]] into List[A] 
     } yield a :: as // Merge the elements and warp in Option 
    case _ => Some(Nil) // sequence of an empty list is Some(List()) 
}

println(sequence(List[Some[Int]]())) // Some(List()) 
println(sequence(List(Some(1), None, Some(3)))) // None 
println(sequence(List(Some(1), Some(2), Some(3)))) // Some(List(1, 2, 3))

來源

2015-08-09 09:43:25 Arjan

這裏有一個快速和骯髒的解決方案，一定要得罪大家的良好的功能情面:)

import scala.util.Try 

def sequence[A](xs: List[Option[A]]): Option[List[A]] = 
    Try(xs.map(_.get)).toOption

來源

2015-08-09 09:56:28

在scala中的一次迭代中實現遍歷函數

回答

相關問題