CODEWITHSUNDEEP
scala
Kevin Meredith
Kevin Meredith

Reputation: 41909

Implementing Foldable[List[A]]

I'm working on a Functional Programming in Scala exercise to implement List[A] on the following trait.

trait Foldable[F[_]] {
    def foldRight[A, B](as: F[A])(f: (A, B) => B): B
    def foldLeft[A, B](as: F[A])(f: (B, A) => B): B
    def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
    def concatenate[A](as: F[A])(m: Monoid[A]): A = foldLeft(as)(m.zero)(m.op)
}

In my attempt to implement foldLeft, how can I specify an initial value if there's none in the signature? 

trait Foldable[List[_]] {
    def foldLeft[A,B](as: List[A])(f: (A, B) => B): B = {
        go(bs: List[A], acc: B): B = bs match {
            case x :: xs => go(xs, f(x, acc))
            case Nil => acc
        }
    go(as, ???) // No start value in the signature? And no Monoid for m.zero
    }
}

Upvotes: 0

Views: 245

Answers (1)

Noah
Noah

Reputation: 13959

It's an error in the book. Take a look at the source on github and you'll see a zero method param:

https://github.com/pchiusano/fpinscala/blob/master/exercises/src/main/scala/fpinscala/monoids/Monoid.scala#L84

trait Foldable[F[_]] {
  import Monoid._

  def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B =
    sys.error("todo")

  def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B =
    sys.error("todo")

  def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B =
    sys.error("todo")

  def concatenate[A](as: F[A])(m: Monoid[A]): A =
    sys.error("todo")

  def toList[A](as: F[A]): List[A] =
    sys.error("todo")
}

Upvotes: 3

Related Questions