Danh sách chuyển đổi [Tùy chọn [A]] thành Tùy chọn [Liệt kê [A]] trong Scala

Question

Tôi mới tham gia FP và Scala và đang đọc cuốn sách Lập trình chức năng trong Scala. Một trong các bài tập trong Chương 4 yêu cầu chúng tôi viết một hàm có tên là sequence sẽ chuyển đổi một số List[Option[A]] thành một số Option[List[A]]. Ở đây Option là một reimplementation của Option được cung cấp bởi thư viện Scala. Đây là mã được yêu cầu.

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 

Bây giờ tôi đã cố gắng rất nhiều, nhưng tôi đã phải tìm kiếm các giải pháp cho các văn bản sequence, đó là,

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

Tôi chỉ muốn chắc chắn rằng tôi hiểu các giải pháp một cách chính xác. Vì vậy, đây là những câu hỏi của tôi.

1. Trực giác của tôi về giá trị trả lại cho case Nil có đúng không? Nó thực sự là một quyết định thiết kế hoặc là một cách tốt hơn so với khác?
2. Đối với case h :: t, đây là những gì tôi đã hiểu. Chúng tôi vượt qua giá trị h trước hết đến chức năng ẩn danh trong flatMap (dưới dạng hh) gọi số sequence đệ quy. Cuộc gọi đệ quy này của sequence trả về một số Option đóng gói Option s trong t. Chúng ta gọi map trên giá trị trả về này và vượt qua h đến hàm ẩn danh (như hh), sau đó tạo một List[A] mới với danh sách được trả về bằng cách gọi đệ quy làm đuôi và h làm đầu. Giá trị này sau đó được đóng gói trong Option bằng cách gọi Some và trả lại.

Sự hiểu biết của tôi về phần thứ hai có đúng không? Nếu có, có cách nào tốt hơn để giải thích nó không?

Answer 1

Dường như sequence có ý định trả lại None nếu có bất kỳ phần tử nào trong danh sách là None và trả lại Some giá trị trong danh sách khác. Do đó trực giác của bạn về trường hợp Nil không chính xác - Nil là danh sách trống không chứa None s, do đó kết quả không được là None.

Hãy thực hiện từng bước một, từ trong ra ngoài.

Giả sử chúng tôi có một số biến số optionList loại Option[List[A]] và một số biến a loại A. Chúng ta có được những gì khi chúng ta gọi là:

optionList.map(a :: _) 

Nếu optionList là None, thì đây sẽ là None. Nếu optionList chứa danh sách, hãy nói list, đây sẽ là Some(a :: list).

Bây giờ nếu đối với một số biến option loại Option[A], những gì chúng ta nhận được khi chúng ta gọi là:

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

Nếu option là None, thì đây sẽ là None.Nếu option chứa một giá trị, hãy nói a, thì đây sẽ là optionList.map(a :: _), mà chúng tôi đã tìm ra ở trên (theo định nghĩa của flatMap).

Bây giờ, nếu chúng ta kết hợp với nhau, chúng ta thấy rằng nếu có bất kỳ phần tử nào là None thì cuộc gọi đệ quy sẽ bị tránh và toàn bộ kết quả sẽ là None. Nếu không có phần tử là None, thì cuộc gọi đệ quy sẽ tiếp tục nối các giá trị của phần tử và kết quả sẽ là Some giá trị nội bộ của phần tử trong danh sách.

Nó có thể là rõ ràng hơn nếu bạn viết lại phần bên trong:

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

Hoặc thậm chí còn ít thành ngữ, nhưng có lẽ làm rõ:

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

Bạn cũng có thể viết lại này khá tự nhiên như một fold không đệ quy, trong trường hợp đó là điều khiến bạn bối rối:

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

Answer 2

Nếu bạn muốn chuyển đổi một List [Option [T]] thành List [T] chỉ cần flatten để hoàn thành phía bên kia là None cho danh sách rỗng và một số cho danh sách không trống chỉ cần sử dụng pattern matching.

val list = List(Some("a"), Some("b"), None, Some("c")) 
    list.flatten match { 
    case Nil => None 
    case l => Some(l) 
    } 

Answer 3

Tôi nghĩ rằng tôi đang cố gắng giải quyết cùng một câu hỏi từ cùng một cuốn sách và đã nghĩ ra điều này. Nó hoạt động cho tôi và trông khá rõ ràng và consice

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

    a.foldLeft(Option(List[A]())) { 

    (prev, cur) => { 

     for { 
     p <- prev if prev != None 
     x <- cur 
     } yield x :: p 

    } 

    } 

}