Scala: Umsetzung von flatMap mit foldRight

Question

Ich habe Probleme, die Lösung der funktionalen Programmierung für das Verständnis:

Implementieren flatMap nur foldRight verwenden, Nil und :: (cons).

Die Lösung ist wie folgt:

def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = 
    xs.foldRight(List[B]())((outCurr, outAcc) => 
    f(outCurr).foldRight(outAcc)((inCurr, inAcc) => inCurr :: inAcc)) 

ich versucht habe, anonyme Funktionen in Funktionsdefinitionen Faktor aus der Lösung ohne Glück neu zu schreiben. Ich kann nicht verstehen, was passiert oder über einen Weg nachdenken, um es zu brechen, so dass es weniger kompliziert ist. Also, jede Hilfe oder Erklärung in Bezug auf die Lösung würde geschätzt werden.

Danke!

Answer 1

Zuerst ignorieren Sie einfach die Einschränkungen und denken über die flatMap Funktion in diesem Fall nach. Sie haben eine List[A] und eine Funktion f: A => List[B]. Normalerweise, wenn Sie nur eine map auf der Liste und wenden Sie die f Funktion, erhalten Sie wieder eine List[List[B]], richtig? Also, um eine List[B] zu bekommen, was würdest du tun? Sie würden über die List[List[B]] eine List[B] zurückbekommen, indem Sie einfach alle Elemente in die List[List[B]] anhängen. So wird der Code aussehen etwas wie folgt aus:

def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
    val tmp = xs.map(f) // List[List[B]] 
    tmp.foldRight(List[B]())((outCurr, outAcc) => outCurr ++ outAcc) 
} 

Um zu überprüfen, was wir haben, so weit, laufen Sie den Code in REPL und überprüfen Sie das Ergebnis mit integrierten in flatMap Methode:

scala> def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
|  val tmp = xs.map(f) // List[List[B]] 
|  tmp.foldRight(List[B]())((outCurr, outAcc) => outCurr ++ outAcc) 
| } 
flatMap: [A, B](xs: List[A])(f: A => List[B])List[B] 

scala> flatMap(List(1, 2, 3))(i => List(i, 2*i, 3*i)) 
res0: List[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9) 

scala> List(1,2,3).flatMap(i => List(i, 2*i, 3*i)) 
res1: List[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9) 

OK, so Sehen Sie sich nun unsere Einschränkungen an, wir dürfen map hier nicht verwenden. Aber das brauchen wir nicht wirklich, denn die map hier ist nur zum Durchlaufen der Liste xs. Wir können dann für diesen Zweck verwenden. Also lassen Sie uns schreiben die map Teil mit foldRight:

def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
    val tmp = xs.foldRight(List[List[B]]())((curr, acc) => f(curr) :: acc) // List[List[B]] 
    tmp.foldRight(List[B]())((outCurr, outAcc) => outCurr ++ outAcc) 
} 

OK, lassen Sie uns den neuen Code überprüfen:

scala> def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
    |   val tmp = xs.foldRight(List[List[B]]())((curr, acc) => f(curr) :: acc) // List[List[B]] 
    |   tmp.foldRight(List[B]())((outCurr, outAcc) => outCurr ++ outAcc) 
    |  } 
flatMap: [A, B](xs: List[A])(f: A => List[B])List[B] 

scala> flatMap(List(1, 2, 3))(i => List(i, 2*i, 3*i)) 
res3: List[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9) 

OK, so weit so gut. Lassen Sie uns also den Code etwas optimieren, anstatt zwei aufeinanderfolgende foldRight zu haben, werden wir sie in nur einem foldRight kombinieren. Das sollte nicht allzu schwierig sein:

def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
    xs.foldRight(List[B]()) { (curr, acc) => // Note: acc is List[B] 
     val tmp2 = f(curr) // List[B] 
     tmp2 ++ acc 
    } 
} 

Überprüfen Sie erneut:

scala> def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
    |  xs.foldRight(List[B]()) { (curr, acc) => // Note: acc is List[B] 
    |   val tmp2 = f(curr) // List[B] 
    |   tmp2 ++ acc 
    |  } 
    | } 
flatMap: [A, B](xs: List[A])(f: A => List[B])List[B] 

scala> flatMap(List(1, 2, 3))(i => List(i, 2*i, 3*i)) 
res4: List[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9) 

OK, also lassen Sie uns unsere Zwänge aus, es sieht aus wie wir nicht ++ Betrieb nutzen können.Nun, ++ ist nur ein Weg, um die beiden List[B] zusammenhängen, so können wir mit Sicherheit die gleiche Sache mit foldRight Verfahren erreichen, wie folgt aus:

def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = { 
    xs.foldRight(List[B]()) { (curr, acc) => // Note: acc is List[B] 
     val tmp2 = f(curr) // List[B] 
     tmp2.foldRight(acc)((inCurr, inAcc) => inCurr :: inAcc) 
    } 
} 

Und dann haben wir sie alle in einer Zeile durch kombinieren:

def flatMap[A, B](xs: List[A])(f: A => List[B]): List[B] = 
    xs.foldRight(List[B]())((curr, acc) => 
    f(curr).foldRight(acc)((inCurr, inAcc) => inCurr :: inAcc)) 

ist es nicht die gegebene Antwort :)

Answer 2

Manchmal ist es einfacher, mit einem einfachen Beispiel zu verstehen: wir eine val xs = List[Int](1,2,3) und eine Funktion Angenommen haben f: Int => List[Int], f(x) = List(x,x) (lambda x => List(x,x)) Appling f zu jedem Element von xs List(f(1),f(2), f(3)) wird List(List(1,1),List(2,2),List(3,3)) ergeben, also müssen wir diese Liste [Liste [Int]] reduzieren. Das Endergebnis sollte Liste (1, 1, 2, 2, 3, 3) sein. Gegeben Cons (: :) der Konstruktor der nicht leeren Liste, sollte dies sein. Beobachten Sie foldRight Operation im Ergebnis, die den Konstruktor Cons (: :) auf das Ergebnis von f angewendet auf jedes Element der Liste xs angewendet. So eine erste Implementierung von flatMap würde in dieser Form

def flatMap[A,B](xs: List[A])(f: A => List[B]): List[B] = xs match { 
    case Cons(head, tail) => foldRight(f(head), Nil)((a,b) => Cons(a,b)) 
} 

sein, flatMap(List(1,2,3)) kehrt Liste (1,1) oder Cons(1,1,Nil) (durch Substitution). Wir müssen also mit einem rekursiven Aufruf von flatMap am Ende fortfahren (indem wir das Problem um 1 von 3 (Elemente) auf 2 (Elemente) reduzieren) und den Basisfall für den Fall einer leeren Liste als Nil hinzufügen (Nil ist die "Null" Element für Cons Betrieb)

def flatMap[A,B](xs: List[A])(f: A => List[B]): List[B] = xs match { 
    case Nil => Nil 
    case Cons(head, tail) => foldRight(f(head), flatMap(tail)(f))((a,b) => Cons(a,b)) 
} 

, die die endgültige Implementierung ist.