Iteration with stop condition - functionally

[Michael Sperber]

Another newbie question:

I'm trying to iterate over the elements of a collection (in the sense
of: accumulating stuff as I'm going along), and (possibly) stop before
the end is reached, based on some condition. (Something like: sum up
the elements of a collection until a limit has been reached.)

I was looking for something along the lines of Oleg Kiselyov's
enumeratee/iteratee interface:

http://okmij.org/ftp/Streams.html

... but couldn't find anything like it in the collections interfaces.
In fact, the only way I could find of doing it involved either an
explicit use of an iterator (not functional), or break (not functional
either). There's no inherent reason why this needs to be imperative,
which is why I'd like to do it functionally.

Am I missing something?

--
Cheers =8-} Mike
Friede, V�lkerverst�ndigung und �berhaupt blabla

[Alec Zorab]

scala> def sumUntilCondition(l: List[Double], p: Double => Boolean,
acc: Double): Double = {
l match {
case h :: t if !p(acc) => sumUntilCondition(t, p, acc + h)
case _ => acc
}
}
| | | | | sumUntilCondition: (l:
List[Double],p: (Double) => Boolean,acc: Double)Double

scala> sumUntilCondition(List(1,2,3,4), d => d > 9, 0)
res0: Double = 10.0

This is just a fold, and no doubt Tony will appear in a minute and do
some Type-Fu magic that puts my example to shame, but I think this
should give you an idea.

> Friede, Völkerverständigung und überhaupt blabla
>

[Alexey Zlobin]

Something like this:

scala> def stopCond(x: Int) = x == 3
stopCond: (x: Int)Boolean

scala> def condFold(a: (Int, Boolean), e: Int): (Int, Boolean) = a match {
| case (x, false) => (x, false)
| case (x, true) => if (stopCond(x)) (x, false) else (x+e, true)
| }
r: (a: (Int, Boolean),e: Int)(Int, Boolean)

scala> (1 to 10).foldLeft ((0,true)) (condFold)
res7: (Int, Boolean) = (3,false)

?

2011/2/11 Michael Sperber <spe...@deinprogramm.de>:

> Friede, Völkerverständigung und überhaupt blabla
>

--
С уважением,
Алексей Злобин.

[Dennis Haupt]

i guess the collection framework can't do this because someone would have to modify each and every implementation of "foreach" and add a "stop now" boolean - or offer 2 different foreachs. and you'd have to traverse your collection recursively.
i think these are 2 good reasons

sometimes, the iterative way is simpler.

-------- Original-Nachricht --------
> Datum: Fri, 11 Feb 2011 17:43:16 +0100
> Von: Michael Sperber <spe...@deinprogramm.de>
> An: scala...@googlegroups.com
> Betreff: [scala-user] Iteration with stop condition - functionally

> Friede, Völkerverständigung und überhaupt blabla

[Dennis Haupt]

that one doesn't stop traversing, it just stops adding the rest of the elements.

-------- Original-Nachricht --------
> Datum: Fri, 11 Feb 2011 19:57:51 +0300
> Von: Alexey Zlobin <alexey...@gmail.com>
> An: Michael Sperber <spe...@deinprogramm.de>
> CC: scala...@googlegroups.com
> Betreff: Re: [scala-user] Iteration with stop condition - functionally

[Nate Nystrom]

You could use a scan and takeWhile. For instance, to sum all the
elements of a list, stopping just before reaching a sum >= 10:

scala> List(1,2,3,4,5,6).view.scanLeft(0)(_+_).takeWhile(x => x < 10).last
res4: Int = 6

Note the use of view to prevent the entire list from being traversed
when doing the scan.

Nate

[Philippe Lhoste]

On 11/02/2011 17:43, Michael Sperber wrote:
> I'm trying to iterate over the elements of a collection (in the sense
> of: accumulating stuff as I'm going along), and (possibly) stop before
> the end is reached, based on some condition. (Something like: sum up
> the elements of a collection until a limit has been reached.)

Funny, if I understood correctly your question, I asked something very similar yesterday:
http://comments.gmane.org/gmane.comp.lang.scala.user/35817 - Partial loop run

If I adapt one of the answers with my test code (clumsy, I know), I would show this example:

class Foo
{
var r = 0
val rand = new scala.util.Random(System.nanoTime)
def isItOk() =
{
r = rand.nextInt(10)
println("One more: " + r)
r
}
}

object TT
{
def main(args: Array[String])
{
val foos = for (i <- 0 until 50) yield new Foo
val res = foos.takeWhile(_.isItOk() != 1).foldLeft(0)(_ + _.r)
println(res)
}
}

HTH.

--
Philippe Lhoste
-- (near) Paris -- France
-- http://Phi.Lho.free.fr
-- -- -- -- -- -- -- -- -- -- -- -- -- --

[Brian Maso]

I like this solution the best for sure because you can easily generalize it to work over any sequence of any type for which you have a Monoid:

//...I'm sure Scalaz has one of these, but defining here so we're sure what a Monoid is:
//   A Monoid[X] is something that defines a "zero" of type X, and a way to "sum" two Xs
//   to produce a new X...
trait Monoid[A] {
    val zero: A
    def sum(a1: A, a2: A)
    }

//...Example Monoid[Int]...
implicit object MonoidInt extends Monoid[Int] {
    val zero = 0
    def sum(a1: Int, a2: Int) = a1 + a2
    }

object Ops {
    def sumWhileLeft[A : Monoid] (a: Seq[A])(f: A => Boolean) = {
        val m = implicitly[Monoid[A]]
        a.view.scanLeft(m.zero)(m.sum).takeWhile(f).last
        }
        }

//...example use:

scala> import Ops._
import Ops._

scala> val l = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
l: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> def cond(i:Int): Boolean = i < 50
cond: (i: Int)Boolean

scala> sumWhileLeft(l)(cond)
res0: Int = 45

Brian Maso

(P.S., re the funny indentation style above: I'm trying out Whitehead indentation this week, which was mentioned on this list within the past few days, to see if I like it. So far I do!)

--
Best regards,
Brian Maso
(949) 395-8551
br...@blumenfeld-maso.com

[Tony Morris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

takeWhileM + State.

case class State[S, A](f: S => (S, A))
def takeWhileM[M[_], A](p: A => M[Boolean], as: List[A]): M[List[A]]

Implement yourself for fun, or see scalaz.

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk1VnIUACgkQmnpgrYe6r62yugCfcy3kbiUux3rsaXdGEjvF8SK2
1CkAn32Vs89T+dXUfbZ5vnqqujaY/89H
=rM+y
-----END PGP SIGNATURE-----