5

Recursion is cool, but sort of low level when you are surrounding by higher order library functions. I am trying to avoid writing a recursive function for a process that depends on the last value generated.

I would usually use iterate function in Clojure over a "zipped" list of last value and current parameter. Is there an equivalent function in Scala's collection API?

Here is an attempt at an abstract example in some crazy pseudo code:

Say you have

  • An input list: Seq(1,2,3)

  • Some action you perform to the last value generated and the next item in the list:

    lastValue ^ 2 + nextInt(i)

and you want to accumulate all the values generated.

I am trying avoid writing something similar to:

def f(ls:Seq[Int]):Seq[Float] = {

  def g(pos:Int, lastGen:Float):Seq[Float] = { 
    val v = gen(lastGen, ls(pos))
    if( end(v) )
      Seq(v)
    else
      Seq(v) ++ g(pos+1, v)
  }

  f(0, 1)
}

I have seen something similar in defining a lazy stream version of Fibonacci in Haskell, so hypothetically I could use a lazy stream that referred to itself, but that is harder to wrap my brain around than Clojure's iterate.

Improve this question

3 Answers 3

Reset to default
6

Is this what you're looking for? It's basically the same thing as iterate in Clojure:

List.iterate(1, 5) { _ + 1 }
// res1: List[Int] = List(1, 2, 3, 4, 5)

I think the definition of iterate for List comes from GenTraversableFactory.

The only downside is that the second argument len is the number of arguments you want, so it doesn't return an infinite sequence like iterate does in Clojure.

Update:

Just learned something new! The Stream object has an iterate method too, and this lets you create infinite lazy streams:

(Stream.iterate(1) { _ * 2 } take 5).toList
// res1: List[Int] = List(1, 2, 4, 8, 16)
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

sorry i should have searched beyond google, straight in scala api. i'll try to ask less obvious q's in future (:
Don't worry. It took me a while to find it—and I already knew it existed. The Scala API is kind of confusing in my opinion, especially with all the implicit conversions. You can't actually find "iterate" on the List's API page, and just googling for "iterate" returns a bunch of results on Iterator instead. I actually found it by looking for the tabulate method, which I figured would be in the same place.
I recommend using Iterator instead of Stream because it doesn't cache the calculated values (which is not needed here).
3

The code you showed is basically equivalent to something like:

ls.foldLeft(List(1.0))((a, b) => gen(a.head, b) :: a).reverse
Improve this answer

Comments

0

It sounds like the higher order function you want is scanLeft, which is like a fold that remembers its intermediate steps. For example, say you have the following:

val ls = Seq(1, 2, 3)
def gen(lastValue: Double, n: Int) = math.pow(lastValue, 2) + n

Then you can combine them like this with scanLeft:

scala> ls.scanLeft(1.0)(gen)
res0: Seq[Double] = List(1.0, 2.0, 6.0, 39.0)

This is more or less equivalent to Apocalisp's formulation with foldLeft, except that scanLeft takes care of holding on to the intermediate values for you.

Improve this answer

1 Comment

exactly. i was trying to decipher why it was called scan left when i was reading about this method previously. still a little shaky on why its named so

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.