Scala takeWhile Method with foldLeft and foldRight

Question

I need to make takeWhile() using foldLeft() and foldRight(). I've come up with this:

def takeWhile(ls:List[Int], p:Int => Boolean): List[Int] = {
    ls.foldLeft(List[Int]())(a,z) =>
    if (p(z)) z :: a
    else a)
}

def takeWhile(ls:List[Int], p:Int => Boolean): List[Int] = {
    ls.foldRight(List[Int]())(a,z) =>
    if (p(a)) a :: z
    else z)
}

But with foldLeft when I call

takeWhile(List(1,2,3,4,5), _< 3)
takeWhile(List(1,2,3,4,5), _> 4)
takeWhile(List(5,6,7,1,2,5), _> 4)

It returns

List(2,1)
List(5)
List(5,7,6,5)

With foldRight I get

List(5)
List(5,6,7,5)

But it should be

List(1,2)
List()
List(5,6,7)

How do I make it stop when condition is not met?

No doubt you have your reasons for re-inventing takeWhile. I think what you will need to do is to make your accumulator a tuple of List[Int] and Boolean. As long as the latter is true, you will continue. Finally, of course you will want to extract just the List[Int] for your result. Your operator will now be a bit more complex, of course. Also, you might want to try inverting z :: a and a :: z. — Phasmid, Jun 02 '17 at 14:38
Do you have to use the fold* methods? They aren't designed for this, they loop the entire collection. If you are set on using a fold, you can do things like call return or maybe throw an exception to exit early. See https://stackoverflow.com/questions/12892701/abort-early-in-a-fold — puhlen, Jun 02 '17 at 14:42

Thomas Böhm · Accepted Answer · 2017-06-02T14:51:13.210

One way to do is the following (pretty much the same as you did it):

def takeWhile(ls:List[Int], p:Int => Boolean): List[Int] = {
    ls.foldLeft(List[Int]()){
      case (a,z) =>
      if (p(z)) z :: a
      else return a.reverse
    }
}

It prints the following:

List(1, 2)
List()
List(5, 6, 7)

The return Returns from the takeWhile-method, so it does what you want, because it stops the foldLeft-operation.

Sorry I modified your Code (other brackets etc), but it didn't compile when copying.

score 1 · Answer 2 · answered Jun 02 '17 at 14:38

Here is one way to get foldLeft() to work. It's hacky, but it gets the job done and it's a starting point:

def takeWhile(ls:List[Int], p:Int => Boolean): List[Int] = {
  ls.foldLeft((List[Int](), true)) {
    (a, z) =>
      if (a._2 && p(z)) (z :: a._1, a._2)
      else (a._1, false)
  }._1.reverse
}

score 0 · Answer 3 · answered Jun 02 '17 at 15:31

Here's one using foldRight (since you asked for both):

def takeWhile[T](list: List[T], p: T => Boolean) =
  list.foldRight(List.empty[T]){
    case (t, l) if p(t) => t :: l
    case (t, l) => Nil
  }

It reinitialize the state to Nil whenever it finds a value that should not be taken.

Scala takeWhile Method with foldLeft and foldRight

3 Answers3