将列表[选项[A]]转换为Scala中的选项[列表[A]]

Question

我是FP和Scala的新手,正在阅读Scala中的Functional Programming一书.其中在第4章的练习要求我们写一个调用的函数sequence这将转换List[Option[A]]成Option[List[A]].这Option是OptionScala库提供的重新实现.这是必需的代码.

trait Option[+A] {
    /* Function to convert Option[A] to Option[B] using the function passed as an argument */
    def map[B](f: A => B): Option[B] = this match {
        case None => None
        case Some(v) => Some(f(v))
    }

    /* Function to get the value in `this` option object or return the default value provided. Here,
     * `B >: A` denotes that the data type `B` is either a super-type of `A` or is `A`
     */
    def getOrElse[B >: A](default: => B): B = this match {
        case None => default
        case Some(v) => v
    }

    /* Used to perform (nested) operations on `this` and aborts as soon as the first failure is
     * encountered by returning `None`
     */
    def flatMap[B](f: A => Option[B]): Option[B] = {
        map(f).getOrElse(None)
    }
}

case class Some[+A](get: A) extends Option[A]   // used when the return value is defined
case object None extends Option[Nothing]        // used when the return value is undefined

现在我尝试了很多,但我不得不查找写作的解决方案sequence,即

def sequence[A](l: List[Option[A]]): Option[List[A]] = l match {
    case Nil => Some(Nil)                   // Or `None`. A design decision in my opinion
    case h :: t => h.flatMap(hh => sequence(t).map(hh :: _))
}

我只是想确保我正确理解解决方案.所以这是我的问题.

1. 我的直觉是关于case Nil正确的回报值吗？它真的是一个设计决定还是比另一个更好？
2. 因为case h :: t,这就是我的理解.我们h首先将值传递给flatMap(as hh)中的匿名函数,该函数以sequence递归方式调用.这种递归调用sequence返回Option封装了Options t.我们调用map这个返回值并传递h给匿名函数(as hh),然后创建一个new List[A],其中递归调用返回的列表作为尾部和h头部.然后Option通过调用Some和返回来封装该值.

我对第二部分的理解是否正确？如果是,是否有更好的解释方法？

Answer 1

如果列表中的任何元素为，则似乎sequence旨在返回，否则返回None列表中的值。所以你对这个案例的直觉是不正确的——是一个不包含s的空列表，所以结果不应该是.NoneSomeNilNilNoneNone

让我们一步一步，从内而外。

假设我们有一些optionList类型的Option[List[A]]变量和一些a类型的变量A。当我们调用时我们会得到什么：

optionList.map(a :: _)

如果optionList是None，那么这将是None。如果optionList包含一个列表，比如说list，这将是Some(a :: list)。

现在，如果对于某个option类型的变量，Option[A]当我们调用时我们会得到什么：

option.flatMap(a => optionList.map(a :: _))

如果option是None，那么这将是None。如果option包含一个值，例如a，那么这将是optionList.map(a :: _)，这是我们在上面计算出来的（根据 的定义flatMap）。

现在，如果我们将它联系起来，我们会看到如果有任何元素是None，则避免递归调用，整个结果将是None。如果没有元素是None，则递归调用将继续附加元素的值，结果将是Some列表元素的内部值。

如果你重写内部部分可能会更清楚：

def sequence[A](l: List[Option[A]]): Option[List[A]] = l match {
    case Nil => Some(Nil)
    case h :: t => h match {
        case None => None
        case Some(head) => sequence(t) match {
            case None => None
            case Some(list) => Some(head :: list)
        }
    }
}

或者甚至不那么惯用语，但也许可以澄清：

def sequence[A](l: List[Option[A]]): Option[List[A]] = l match {
    case Nil => Some(Nil)
    case h :: t => 
        val restOfList = sequence(t)
        if (h == None || restOfList == None) None else Some(h.get :: restOfList.get)
}

您也可以很自然地将其重写为fold无递归，以防您感到困惑：

def sequence[A](l: List[Option[A]]) = (Option(List.empty[A]) /: l) {
    case(Some(sofar), Some(value)) => Some(value :: sofar); 
    case(_, _) => None 
}