Monday 12 October 2009

Scala: C style iterate function for building lists

In my previous post, I used a forloop function for creating a List from a sort of c-like for loop

val rets = forloop(today)(d => d >= _start && d >= limit)(d => d - 7.days) {
day =>
val ret = getReturn(day - 7.days, day)
ret.get // might throw Exception (same as c# code)
}


I liked the fact that I could use break and continue semantics in the loop although I didn't need it in the algorithm.

But perhaps foreach is/was trying to do too much, effectively (a) producing a list of dates (etc) and then (b) for each date in the List calculating another value (a Double) to return in a list. Of course (b) is just the map function. So here's another function that I've called iterateFor which only does (a). Using it to replace the code above gives:


val dates = iterateFor(today)(d => d >= _start && d >= limit)(d => d - 7.days)
val rets = dates.map(d => getReturn(d - 7.days, d).get)


I was hoping to find something already built it to the scala libraries that would do what iterateFor does . As Daniel pointed out in the comments there is Iterator.iterate:

def iterate [T](start : T)(f : (T) => T) : Iterator[T]


and if you use takeWhile on the Iterator then the implementation of iterateFor is simple:


def iterateFor[T]
(init: T)
(cond: T => Boolean)
(next: T => T)
: List[T] =
{
Iterator.iterate(init)(next) takeWhile cond toList
}


Or it can be implemented as a recursive function like this:


def iterateFor[T]
(init: T)
(cond: T => Boolean)
(next: T => T)
: List[T] =
{
def _iterateFor(currentResults: List[T])(loopcounter: T) : List[T] = {
if (cond(loopcounter)) {
val newResults = loopcounter :: currentResults
_iterateFor(newResults)(next(loopcounter))
} else {
currentResults
}
}
_iterateFor(List())(init).reverse
}


I suspect that there are plenty of little while loop type algorithms that use vars that could be replaced by iterateFor (or forloop).

5 comments:

Johan said...

This function is very similar to until (but with a reversed predicate) in Haskell: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#v%3Auntil. Basically, it's iterate and takeWhile.

Unfortunately, the iterate functions in Scala's traversable collections are not polymorphic. (Maybe it's because it would only work for lazy collections.) But here's one for Stream:

def iterate[A](step: A => A)(seed: A): Stream[A] = seed lazy_:: iterate(step)(step(seed))

Now it's easy to write iterateFor:

def iterateFor[A](predicate: A => Boolean)(step: A => A)(seed: A): Stream[A] = iterate(step)(seed) takeWhile predicate

or, all in one go:

def until[A](...) = if (predicate(seed)) seed lazy_:: until(predicate)(step)(step(seed)) else Stream.empty

TimA said...

@Johan: Thanks, this is great stuff. 25 years ago I had the good chance to do some Miranda at UKC (under the watchful glare of the now Proj Simon Thomson) Finally it is paying off, and I have a vague clue of what you are talking about!
By the way lazy_:: is gone and now known as #:: in the latest version of scala 2.8pre that I am using (via eclipse plugin)

Daniel said...

Welcome to Scala version 2.8.0.r18637-b20090903020149 (Java HotSpot(TM) Client VM, Java 1.6.0_16).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val x = Iterator.iterate(0)(_ + 1)
x: Iterator[Int] = non-empty iterator

scala> x takeWhile (_ < 20)
res0: Iterator[Int] = non-empty iterator

scala> res0.toList
res1: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)

TimA said...

@Daniel: Thanks (and doh!). The moral of the story is: learn he APIs. I'll update my blog so as not to mislead anybody about the simplest solution. The journey has been a good one though. What is intereresting is the radically differency implementations of Iterorator.iterate and
def iterate[A]
(seed: A)(step: A => A)
: Stream[A]
= seed #:: iterate(step(seed))(step)
With the former using internal state and the latter using the lazy Stream mechanism (whatever that is). Is there is anything you can do with a Stream based iterate function that you can't do with Iterator.iterate?

Daniel said...

Notice that is 2.8. There are many, many iterator builders in Scala 2.8. I think this one, in particular, is one of the new builders.

There are two advantages of Stream over iterators. First, it is functional. Relevantly, if you pass a reference to some part of the stream around, you need not be concerned about the reference you kept being modified.

The second advantage, closely related to the first, is that a Stream persists. If you make a Stream for prime numbers (such as the one in the API docs for Stream), you may rest assured that each element will be computed only once. If you ever need it again, and haven't lost the reference to it, it will be available in memory.