2

Is there a benefit to build a Stream in a tail-recursive way with an accumulator? The @tailrec annotation will turn a recursion into a loop, but the loop would be evaluated strictly.

I can figure out a simple way to add at the head of the stream in a tail-recursive way

  @tailrec
    def toStream(current:A, f: A => B, next: A => A, previous:Stream[B]):Stream[B]] = {
        if(exitCondition(a))
            previous
        else{
            val newItem =  f(current)
            val newCurrent = next(a)
            toStream(nextCurrent,f,next,Stream cons (newItem, previous) )
        }
    }

And how to add at the end (building a real lazy stream) without tail-recursion

    def toStream(current:A, f: A => B, next: A => A):Stream[B] = {
        if(exitCondition(a))
            Stream.empty[B]
        else{
            val newItem =  f(current)
            val newCurrent = next(a)
            Stream.cons (newItem, toStream(newCurrent))
        }
    }

How would you code the dual of this function:

  • Add at the head in non tail-recursive?
  • Add the end tail-recursive
Edmondo
  • 19,559
  • 13
  • 62
  • 115
  • 2
    There's no real notion of tail recursion for potentially infinite data (codata). In fact, recursion itself isn't really a thing over codata, although we like to pretend it is in some languages. Codata allows for unfolds and that's more or less what your `toStream` function is. Tail calls in general are still useful in these situations, but unfortunately Scala/JVM can't handle arbitrary tail calls. – Mysterious Dan Feb 28 '14 at 18:17
  • So can you help with the implementation of add in head non tail recursive / add the end tail recursive? – Edmondo Mar 03 '14 at 10:22
  • Possible duplicate of [What is the standard way to optimise mutual recursion in F#/Scala?](http://stackoverflow.com/questions/2798831/what-is-the-standard-way-to-optimise-mutual-recursion-in-f-scala) – Paul Sweatte Jun 17 '16 at 18:06

0 Answers0