Implémentez la fonction flatMap

Question

Avertissement: ceci fait partie d'un devoir. Je veux implémenter le flatMap pour l'objet List personnalisé. J'ai implémenté la carte avec succès, mais j'ai un problème avec flatmap. Je ne sais pas comment aplatir la liste des listes que je reçois de la carte. Je ne sais pas si je devrais vraiment utiliser la carte du tout.

trait List[+A] { 
    /** The first element */ 
    def head: A 
    /** The rest of the elements */ 
    def tail: List[A] 
    def flatMap[B](f: A => List[B]): List[B] 
    def map[B](f: A => B): List[B] 

    // Concatenate two lists 
    def concat[B >: A](that: List[B]): List[B] = this match { 
    case Empty => that 
    case NonEmpty(head, tail) => NonEmpty(head, tail concat that) 
    } 
} 

case object Empty extends List[Nothing] { 
    def head = throw new UnsupportedOperationException("Empty.head") 
    def tail = throw new UnsupportedOperationException("Empty.tail") 
    def flatMap[B](f: Nothing => List[B]): List[B] = Empty 
    def map[B](f: Nothing => B): List[B] = Empty 

    override def toString = "Empty" 
} 

case class NonEmpty[A](head: A, tail: List[A]) extends List[A] { 

    def map[B](f: A => B): List[B] = { 

    NonEmpty(f(head), tail.map(f)) 

    } 
def flatMap[B](f: A => List[B]): List[B] = { 
    val a = this.map(f) 
    for (x <- a; y <- x) yield y 
    } 
} 

Answer 1

Vous devez écrire flatMap pour une liste de longueur n. Essayez de le résoudre en supposant que vous l'avez déjà résolu pour une liste de longueur n-1. Si vous pouvez le faire, alors vous avez résolu le problème, car n => n-1 => ... => 1 => 0, et pour 0 vous avez déjà une solution.

Ce type de pensée convient à votre liste, car il s'agit d'un type récursif.

Vous l'avez déjà fait avec map, faites de même avec flatMap. Les deux fonctions sont une transformation de List [A] en List [B], la seule différence est l'outil qu'ils peuvent utiliser, map a une fonction qui convertit A en B, tandis que flatMap a une fonction qui convertit A en List [B]

Answer 2

comme c'est un devoir, je ne veux pas vous donner une solution complète, juste quelques conseils.

1. Vous n'avez pas besoin de mettre en œuvre mapflatMap (en fait il est plus facile de le faire dans l'autre sens)
2. vous avez tout ce dont vous avez besoin (flatMap prend une fonction qui renvoie une List[B] et List a défini concat)
3. mettre en œuvre le flatMap de Empty premier ;-)