Conversione lista [Opzione [A]] a un'opzione [Elenco [A]] in Scala

Question

Sono nuovo a FP e Scala e sto leggendo il libro Programmazione funzionale in Scala. Uno degli esercizi del capitolo 4 ci chiede di scrivere una funzione denominata sequence che converta uno List[Option[A]] in uno Option[List[A]]. Qui Option è una reimplementazione di Option fornita dalla libreria Scala. Ecco il codice richiesto.

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 

Ora ho provato un sacco, ma ho dovuto cercare la soluzione per la scrittura sequence, che è,

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

voglio solo per assicurarsi che ho capito la soluzione corretta. Quindi ecco le mie domande.

1. La mia intuizione sul valore di ritorno per case Nil è corretta? È davvero una decisione di progettazione o è in un modo migliore rispetto all'altro?
2. Per case h :: t, questo è quello che ho capito. Passiamo il valore h in primo luogo alla funzione anonima in flatMap (come hh) che richiama in modo ricorsivo sequence. Questa chiamata ricorsiva di sequence restituisce un Option che incapsula i Option s in t. Invochiamo map su questo valore restituito e passiamo a h alla funzione anonima (come hh) che crea quindi un nuovo List[A] con l'elenco restituito dalla chiamata ricorsiva come coda e h come capo. Questo valore viene quindi incapsulato in Option invocando Some e restituito.

La mia comprensione per la seconda parte è corretta? Se sì, c'è un modo migliore per spiegarlo?

Answer 1

Sembra che sequence sia inteso per restituire None se qualsiasi elemento nell'elenco è None e restituire altrimenti Some valori nell'elenco. Quindi la tua intuizione sul caso Nil non è corretta - Nil è una lista vuota che non contiene None s, quindi il risultato non dovrebbe essere None.

Facciamo un passo alla volta, dall'interno verso l'esterno.

Supponiamo di avere qualche variabile optionList di tipo Option[List[A]] e qualche variabile a di tipo A. Che cosa si ottiene quando chiamiamo:

optionList.map(a :: _) 

Se optionList è None, allora questo sarà None. Se optionList contiene un elenco, ad esempio list, questo sarà Some(a :: list).

Ora, se per qualche variabile di tipo optionOption[A], cosa otteniamo quando chiamiamo:

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

Se option è None, allora questo sarà None.Se option contiene un valore, ad esempio a, questo sarà optionList.map(a :: _), che abbiamo scoperto sopra (dalla definizione di flatMap).

Ora se lo leghiamo insieme, vediamo che se un elemento è None, la chiamata ricorsiva viene evitata e l'intero risultato sarà None. Se nessun elemento è None, la chiamata ricorsiva continuerà ad aggiungere i valori dell'elemento e il risultato sarà Some dei valori interni dell'elemento della lista.

potrebbe essere più chiaro se si riscrive la parte interna:

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

o anche meno idiomatica, ma forse chiarire:

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

Si potrebbe anche riscrivere questa bella, naturalmente, come fold senza ricorsione, nel caso in cui sia ciò che ti confonde:

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

Answer 2

Se vuoi convertire un elenco [Opzione [T]] in Elenco [T] appiattisci per completare l'altro lato, che è Nessuno per la lista vuota e Alcuni per elenco non vuoto usano solo la corrispondenza del modello.

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

Answer 3

Penso che stavo cercando di risolvere stessa domanda dallo stesso libro e si avvicinò con questo. Funziona per me e sembra abbastanza chiaro e consolato

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 

    } 

    } 

}