在 Scala 中将 List[Option[A]] 转换为 Option[List[A]] [英] Converting List[Option[A]] to an Option[List[A]] in Scala

问题描述

我是 FP 和 Scala 的新手，正在阅读《Scala 函数式编程》一书.第 4 章中的一个练习要求我们编写一个名为 sequence 的函数，它将把 List[Option[A]] 转换为 Option[List[A]]].这里的 Option 是 Scala 库提供的 Option 的重新实现.这是所需的代码.

I am new to FP and Scala and am reading the book Functional Programming in Scala. One of the exercises in Chapter 4 asks us to write a function called sequence which would convert a List[Option[A]] to an Option[List[A]]. Here Option is a reimplementation of the Option provided by the Scala library. Here's the required code.

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的解决方案，也就是，

Now I tried a lot, but I had to look up the solution for writing sequence, which is,

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

我只是想确保我正确理解了解决方案.下面是我的问题.

I just want to make sure I understood the solution correctly. So here are my questions.

1. 我对 case Nil 返回值的直觉是否正确?这真的是一个设计决定还是某种方式比另一种方式更好?
2. 对于case h :: t，我是这么理解的.我们首先将值 h 传递给 flatMap 中的匿名函数(作为 hh)，该函数递归调用 sequence.sequence 的这个递归调用返回一个 Option，将 Option 封装在 t 中.我们在这个返回值上调用 map 并将 h 传递给匿名函数(作为 hh)，然后它创建一个新的 List[A] 以递归调用返回的列表为尾部，h 为头部.然后通过调用 Some 将该值封装在 Option 中并返回.

1. Is my intuition about the return value for case Nil correct? Is it really a design decision or is one way better than the other?
2. For case h :: t, this is what I understood. We pass the value h firstly to the anonymous function in flatMap (as hh) which invokes sequence recursively. This recursive call of sequence returns an Option encapsulating the Options in t. We invoke map on this returned value and pass h to the anonymous function (as hh) which then creates a new List[A] with the list returned by the recursive call as the tail and h as the head. This value is then encapsulated in Option by invoking Some and returned.

我对第二部分的理解正确吗?如果是，有没有更好的解释方法?

Is my understanding for the the second part correct? If yes, is there a better way to explain it?

推荐答案

sequence 似乎是为了返回 None 如果列表中的任何元素是 None，否则返回列表中的 Some 值.所以你对 Nil 情况的直觉是不正确的——Nil 是一个不包含 None 的空列表，所以结果不应该是无.

It seems that sequence is intended to return None if any element in the list is None, and return Some of values in the list otherwise. So your intuition about the Nil case is not correct -- Nil is an empty list that contains no Nones, so the result should not be None.

让我们一步一步，从内到外.

Let's take it one step at a time, from the inside out.

假设我们有一些 Option[List[A]] 类型的变量 optionList 和 A<类型的一些变量 a/代码>.当我们打电话时我们得到了什么:

Suppose we have some variable optionListof type Option[List[A]] and some variable a of type A. What do we get when we call:

optionList.map(a :: _)

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

If optionList is None, then this will be None. If optionList contains a list, say list, this will be Some(a :: list).

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

Now if for some variable option of type Option[A], what do we get when we call:

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

如果option 是None，那么这将是None.如果 option 包含一个值，比如 a，那么这将是 optionList.map(a :: _)，我们在上面找到了(由flatMap的定义).

If option is None, then this will be None. If option contains a value, say a, then this will be optionList.map(a :: _), which we figured out above (by the definition of flatMap).

现在，如果我们把它联系起来，我们会看到如果任何元素是 None，那么递归调用就被避免了，整个结果将是 None.如果没有元素是 None，那么递归调用将继续追加元素的值，结果将是列表元素内部值的 Some.

Now if we tie it together, we see that if any element is None, then the recursive call is avoided and the whole result will be None. If no element is None, then the recursive call will keep appending the element's values, and the result will be Some of the list's element's internal values.

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

It might be more clearer if you rewrite the inner part:

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

甚至不那么惯用语，但也许可以澄清一下:

Or even less idiomatic, but maybe clarifying:

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 而不使用递归，以防您感到困惑:

You could also rewrite this pretty naturally as a fold without recursion, in case that is what's confusion you:

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

这篇关于在 Scala 中将 List[Option[A]] 转换为 Option[List[A]]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！