Clever Geek Handbook

Reverse use of foldLeft in scala

def foldLeft[A, B] (as: List[A], z: B) (f: (B, A) => B) : B = as match {
  case Nil => z
  case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
}

def reverse[A] (as: List[A]): List[A] =
  foldLeft(as, List[A]())((h, acc) => Cons(acc, h))

I'm not sure how List [A] in foldLeft is of type B. Could someone clean up the process going on in these functions?

+3


source to share


2 answers


This reverse implementation calls foldLeft

c A

as a type 1 argument ( foldLeft#A = A

) and List[A]

as a type 2 argument ( foldLeft#B = List[A]

). Here's an annotated version of the type that makes it very explicit:



def reverse[A] (as: List[A]): List[A] =
  foldLeft[A, List[A]](as = as: List[A], z = List[A]())(
    (h: List[A], acc: A) => Cons(acc, h): List[A]
  )
+1


source


Also Cons

(if it's Cons

from the standard library) creates a stream instead of a list. You probably want to use ::

instead:



def reverse[A] (as: List[A]): List[A] =
    foldLeft(as, List[A]())((acc, h) => h :: acc)
+1


source






More articles:


All Articles