Tail Recursive or while loop

I typically prefer iteration over recursion, but I guess it really is a
matter of taste.
However using higher-order-functions on collections is often the better way.
I would recommend:

def bmap[T](test: => Boolean)(block: => T): List[T] =
Iterator.continually(block).takeWhile(_ => test).toList

Tail recursion should get converted internally into a while loop, so both methods should be approximately equally fast.  Use whichever one is easier to get right in your case.  For example, there is a bug in your second (tail recursive) loop; you either need
  def cond(t: => Boolean)
or
  def cond(t: Boolean):Unit = if (t) { ret += block; cond(test) }

There is also more overhead in the second version since you need to form a closure around the value ret.  So in this case, I'd say
  * Tail recursion is a more complex algorithm, leading to a greater chance for bugs
  * Tail recursion is slightly slower
so a while loop is preferable _if_ you're going to write the algorithm that way.

On the other hand, I'd have written the tail-recursive version like so:

  def bmap[T](test: => Boolean)(block: => T, part: List[T] = Nil): List[T] =
    if (test) bmap(test)(block, block :: part) else part

which is better than the iterative version because it doesn't require creating a second collection.  In general, this is usually the better way to build something with a tail-recursive method: have it pass the collection-so-far forward, and provide a default parameter that contains the empty collection.

Just for completeness, you can, of course, do this also with mutable iterative code:

  def bmap[T](test: => Boolean)(block: => T) = {
    var res: List[T] = Nil
    while (test) res ::= block
    res
  }

and this is approximately what the tail-recursive version gets turned into anyway.

(If you insist that the list be created in the correct order at the end, "else part.reverse" or "res.reverse" will do the trick, but then you're only slightly better off than with the ListBuffer, and would be better off with an ArrayBuffer in most cases:
  def bmap[T](test: => Boolean)(block: => T) = {
    var res = ArrayBuffer[T]()
    while (test) res += block
    res.toList
  }
Anyway, as you can see, this can get almost arbitrarily involved if you let it.)

Of course, if this isn't performance-critical code (and most code is not), then you can try to find a library function that does the same thing already.

  --Rex

On Wed, Nov 10, 2010 at 9:07 AM, Amador Antonio Cuenca <sphi02ac@gmail.com> wrote:

Hi guys, 
I'm reading the Beginning Scala book by David Pollak. I've done this example(Chapter 4 pg. 110):

def bmap[T](test: => Boolean)(block: => T): List[T] = {

    val ret = new ListBuffer[T]

    while(test) ret += block

    ret.toList

 }

But I readed before that tail recursion is better than looping. So I wonder if this implementation is better or is unnecesary:

def bmap[T](test: => Boolean)(block: => T): List[T] = {

    val ret = new ListBuffer[T]

    def cond(t: Boolean): Unit = if(t) {ret += block; cond(t)} 

    cond(test)    

    ret.toList

  }

Regards,--
TSU. Amador Cuenca

Thank you guys for yours suggestions, It helped me a lot.
Regards,
--
TSU. Amador Cuenca

On Wed, Nov 10, 2010 at 6:07 AM, Amador Antonio Cuenca <sphi02ac@gmail.com> wrote:

Hi guys, 
I'm reading the Beginning Scala book by David Pollak. I've done this example(Chapter 4 pg. 110):

def bmap[T](test: => Boolean)(block: => T): List[T] = {

    val ret = new ListBuffer[T]

    while(test) ret += block

    ret.toList

 }

But I readed before that tail recursion is better than looping. So I wonder if this implementation is better or is unnecesary:

def bmap[T](test: => Boolean)(block: => T): List[T] = {

    val ret = new ListBuffer[T]

    def cond(t: Boolean): Unit = if(t) {ret += block; cond(t)} 

    cond(test)    

    ret.toList

  }

Regards,

Tail recurse code is preferable to while loops... mainly for readability.

Let's look at the two methods both in desugared mode and as bytecode:

object Foo {

  import scala.collection.mutable._
  import scala.annotation.tailrec

  def bmap[T](test: => Boolean)(block: => T): List[T] = {
    val ret = new ListBuffer[T]

    @tailrec  def cond(t: Boolean): Unit = if(t) {ret += block; cond(t)}

    cond(test)   
    ret.toList
  }


  def bmap2[T](test: => Boolean)(block: => T): List[T] = {
    val ret = new ListBuffer[T]

    while (test) ret += block
  
    ret.toList
  }
}

So, let's look at the (2.8.0) desugared output:

dpp@appa:~$ scalac -print TestIt.scala
[[syntax trees at end of cleanup]]// Scala source: TestIt.scala
package <empty> {
  final class Foo extends java.lang.Object with ScalaObject {
    def bmap(test: Function0, block$1: Function0): List = {
      val ret$1: scala.collection.mutable.ListBuffer = new scala.collection.mutable.ListBuffer();
      Foo.this.cond$1(test.apply$mcZ$sp(), block$1, ret$1);
      ret$1.toList()
    };
    def bmap2(test: Function0, block: Function0): List = {
      val ret: scala.collection.mutable.ListBuffer = new scala.collection.mutable.ListBuffer();
      while$1(){
        if (test.apply$mcZ$sp())
          {
            ret.+=(block.apply());
            while$1()
          }
        else
          ()
      };
      ret.toList()
    };
    @scala.annotation.tailrec final private[this] def cond$1(t: Boolean, block$1: Function0, ret$1: scala.collection.mutable.ListBuffer): Unit = {
      <synthetic> val _$this: object Foo = Foo.this;
      _cond(_$this,t){
        if (t)
          {
            ret$1.+=(block$1.apply());
            _cond(Foo.this, t)
          }
        else
          ()
      }
    };
    def this(): object Foo = {
      Foo.super.this();
      ()
    }
  }
}

So, both methods desugar almost identically.  Next, let's look at the bytecode:

dpp@appa:~$ javap -c -private Foo\$
Compiled from "TestIt.scala"
public final class Foo$ extends java.lang.Object implements scala.ScalaObject{
public static final Foo$ MODULE$;

public static {};
  Code:
   0:    new    #9; //class Foo$
   3:    invokespecial    #12; //Method "<init>":()V
   6:    return

public scala.collection.immutable.List bmap(scala.Function0, scala.Function0);
  Code:
   0:    new    #16; //class scala/collection/mutable/ListBuffer
   3:    dup
   4:    invokespecial    #18; //Method scala/collection/mutable/ListBuffer."<init>":()V
   7:    astore_3
   8:    aload_0
   9:    aload_1
   10:    invokeinterface    #24,  1; //InterfaceMethod scala/Function0.apply$mcZ$sp:()Z
   15:    aload_2
   16:    aload_3
   17:    invokespecial    #28; //Method cond$1:(ZLscala/Function0;Lscala/collection/mutable/ListBuffer;)V
   20:    aload_3
   21:    invokevirtual    #32; //Method scala/collection/mutable/ListBuffer.toList:()Lscala/collection/immutable/List;
   24:    areturn

public scala.collection.immutable.List bmap2(scala.Function0, scala.Function0);
  Code:
   0:    new    #16; //class scala/collection/mutable/ListBuffer
   3:    dup
   4:    invokespecial    #18; //Method scala/collection/mutable/ListBuffer."<init>":()V
   7:    astore_3
   8:    aload_1
   9:    invokeinterface    #24,  1; //InterfaceMethod scala/Function0.apply$mcZ$sp:()Z
   14:    ifeq    31
   17:    aload_3
   18:    aload_2
   19:    invokeinterface    #46,  1; //InterfaceMethod scala/Function0.apply:()Ljava/lang/Object;
   24:    invokevirtual    #50; //Method scala/collection/mutable/ListBuffer.$plus$eq:(Ljava/lang/Object;)Lscala/collection/mutable/ListBuffer;
   27:    pop
   28:    goto    8
   31:    aload_3
   32:    invokevirtual    #32; //Method scala/collection/mutable/ListBuffer.toList:()Lscala/collection/immutable/List;
   35:    areturn

private final void cond$1(boolean, scala.Function0, scala.collection.mutable.ListBuffer);
  Code:
   0:    iload_1
   1:    ifeq    18
   4:    aload_3
   5:    aload_2
   6:    invokeinterface    #46,  1; //InterfaceMethod scala/Function0.apply:()Ljava/lang/Object;
   11:    invokevirtual    #50; //Method scala/collection/mutable/ListBuffer.$plus$eq:(Ljava/lang/Object;)Lscala/collection/mutable/ListBuffer;
   14:    pop
   15:    goto    0
   18:    return

private Foo$();
  Code:
   0:    aload_0
   1:    invokespecial    #57; //Method java/lang/Object."<init>":()V
   4:    aload_0
   5:    putstatic    #59; //Field MODULE$:LFoo$;
   8:    return

}

So, at the byte-code level, the code is identical (with the exception of one method call to cond$1).

Your choice of using tail recursive (which is much easier with the 2.8 @tailrec annotation) or while loop.

Thanks for reading Beginning Scala and thanks for your question.

David


 

--
TSU. Amador Cuenca

--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Blog: http://goodstuff.im
Surf the harmonics

On Wed, Nov 10, 2010 at 7:42 AM, Rex Kerr <ichoran@gmail.com> wrote:

Tail recursion should get converted internally into a while loop, so both methods should be approximately equally fast.  Use whichever one is easier to get right in your case.  For example, there is a bug in your second (tail recursive) loop; you either need
  def cond(t: => Boolean)
or
  def cond(t: Boolean):Unit = if (t) { ret += block; cond(test) }

There is also more overhead in the second version since you need to form a closure around the value ret.  So in this case, I'd say
  * Tail recursion is a more complex algorithm, leading to a greater chance for bugs
  * Tail recursion is slightly slower
so a while loop is preferable _if_ you're going to write the algorithm that way.

On the other hand, I'd have written the tail-recursive version like so:

  def bmap[T](test: => Boolean)(block: => T, part: List[T] = Nil): List[T] =
    if (test) bmap(test)(block, block :: part) else part

which is better than the iterative version because it doesn't require creating a second collection.  In general, this is usually the better way to build something with a tail-recursive method: have it pass the collection-so-far forward, and provide a default parameter that contains the empty collection.

Just for completeness, you can, of course, do this also with mutable iterative code:

  def bmap[T](test: => Boolean)(block: => T) = {
    var res: List[T] = Nil
    while (test) res ::= block
    res
  }

and this is approximately what the tail-recursive version gets turned into anyway.

(If you insist that the list be created in the correct order at the end, "else part.reverse" or "res.reverse" will do the trick, but then you're only slightly better off than with the ListBuffer, and would be better off with an ArrayBuffer in most cases:

Which cases would these be?  ListBuffer is O(1) append and O(1) prepend.  .toList is free... the only cost is doing a prepend or append after doing a toList.
 

  def bmap[T](test: => Boolean)(block: => T) = {
    var res = ArrayBuffer[T]()
    while (test) res += block
    res.toList
  }
Anyway, as you can see, this can get almost arbitrarily involved if you let it.)

Of course, if this isn't performance-critical code (and most code is not), then you can try to find a library function that does the same thing already.

  --Rex

On Wed, Nov 10, 2010 at 9:07 AM, Amador Antonio Cuenca <sphi02ac@gmail.com> wrote:

Hi guys, 
I'm reading the Beginning Scala book by David Pollak. I've done this example(Chapter 4 pg. 110):

def bmap[T](test: => Boolean)(block: => T): List[T] = {

    val ret = new ListBuffer[T]

    while(test) ret += block

    ret.toList

 }

But I readed before that tail recursion is better than looping. So I wonder if this implementation is better or is unnecesary:

def bmap[T](test: => Boolean)(block: => T): List[T] = {

    val ret = new ListBuffer[T]

    def cond(t: Boolean): Unit = if(t) {ret += block; cond(t)} 

    cond(test)    

    ret.toList

  }

Regards,--
TSU. Amador Cuenca

--
Lift, the simply functional web framework http://liftweb.net
Beginning Scala http://www.apress.com/book/view/1430219890
Follow me: http://twitter.com/dpp
Blog: http://goodstuff.im
Surf the harmonics

On Thu, Nov 11, 2010 at 11:03 AM, David Pollak <feeder.of.the.bears@gmail.com> wrote:

Your choice of using tail recursive (which is much easier with the 2.8 @tailrec annotation) or while loop.

I find the @tailrec annotation annoying. I would rather have tail recursion be the default assumption, with a compiler warning when not possible (and an optional @notailrec or something like that).

On Thu, Nov 11, 2010 at 12:13 PM, David Pollak <feeder.of.the.bears@gmail.com> wrote:

On Wed, Nov 10, 2010 at 7:42 AM, Rex Kerr <ichoran@gmail.com> wrote:

(If you insist that the list be created in the correct order at the end, "else part.reverse" or "res.reverse" will do the trick, but then you're only slightly better off than with the ListBuffer, and would be better off with an ArrayBuffer in most cases:

Which cases would these be?  ListBuffer is O(1) append and O(1) prepend.  .toList is free... the only cost is doing a prepend or append after doing a toList.

My mistake.  I'd forgotten that ListBuffer was one of the watch-self-for-mutation classes.  The only penalty is a little extra space for the extra pointer per item.

You're still better off if you can use ArrayBuffer the _whole_ way through (to avoid creating one object per element in the buffer), but if you need to end up with a list, ListBuffer is the way to go.

  --Rex

On Thu, Nov 11, 2010 at 12:50:22PM -0600, Nils Kilden-Pedersen wrote:
> I find the @tailrec annotation annoying. I would rather have tail
> recursion be the default assumption, with a compiler warning when not
> possible (and an optional @notailrec or something like that).

What, you want it to issue a warning on every recursive method which
isn't tail recursive? You have to be kidding.

On Thu, Nov 11, 2010 at 2:33 PM, Paul Phillips <paulp@improving.org> wrote:

On Thu, Nov 11, 2010 at 12:50:22PM -0600, Nils Kilden-Pedersen wrote:
> I find the @tailrec annotation annoying. I would rather have tail
> recursion be the default assumption, with a compiler warning when not
> possible (and an optional @notailrec or something like that).

What, you want it to issue a warning on every recursive method which
isn't tail recursive? You have to be kidding.

Not really. It's a stack overflow waiting to happen.

On Thu, Nov 11, 2010 at 6:42 PM, Nils Kilden-Pedersen <nilskp@gmail.com> wrote:

On Thu, Nov 11, 2010 at 2:33 PM, Paul Phillips <paulp@improving.org> wrote:

On Thu, Nov 11, 2010 at 12:50:22PM -0600, Nils Kilden-Pedersen wrote:
> I find the @tailrec annotation annoying. I would rather have tail
> recursion be the default assumption, with a compiler warning when not
> possible (and an optional @notailrec or something like that).

What, you want it to issue a warning on every recursive method which
isn't tail recursive? You have to be kidding.

Not really. It's a stack overflow waiting to happen.

It's also the only way to write divide-and-conquer recursion (which usually has log N depth, which usually is no worry for the stack).

I suppose one could argue for a compiler flag that would automatically apply a @tailrec to all methods that did not have a @notailrec, but aside from that too many normal use cases of recursion would be made too unpleasant.

(Keep in mind that @tailrec is just there to make sure that you have to written a tail-recursive function; if you've written a function that can be made tail-recursive, it will be, @tailrec or no.)

  --Rex

You realize that @tailrec is not required for a tail-recursive method to be rewritten? It's only purpose is, if you're not sure whether a method can be rewritten or not (or someone reading your code may be unsure), by annotating the method you are requiring the compiler to fail if it cannot be rewritten, thus ensuring that it will be rewritten. If you know the rules pretty well and are writing code for yourself then most of the time you don't need it.

On Thu, Nov 11, 2010 at 1:50 PM, Nils Kilden-Pedersen <nilskp@gmail.com> wrote:

On Thu, Nov 11, 2010 at 11:03 AM, David Pollak <feeder.of.the.bears@gmail.com> wrote:

Your choice of using tail recursive (which is much easier with the 2.8 @tailrec annotation) or while loop.

I find the @tailrec annotation annoying. I would rather have tail recursion be the default assumption, with a compiler warning when not possible (and an optional @notailrec or something like that).

On Thu, Nov 11, 2010 at 6:28 PM, Naftoli Gugenheim <naftoligug@gmail.com> wrote:

You realize that @tailrec is not required for a tail-recursive method to be rewritten? It's only purpose is, if you're not sure whether a method can be rewritten or not (or someone reading your code may be unsure), by annotating the method you are requiring the compiler to fail if it cannot be rewritten, thus ensuring that it will be rewritten. If you know the rules pretty well and are writing code for yourself then most of the time you don't need it.

I realize that, which is part of why I find it a little bit annoying, i.e. it's essentially unnecessary when things are coded correctly.

"when things are coded correctly" is your failing assumption, I
guess... "Help the compiler help you", is a very simple and reliable
axiom when you don't absolutely trust your abilities to code properly.

Alex

2010/11/12, Nils Kilden-Pedersen :
> On Thu, Nov 11, 2010 at 6:28 PM, Naftoli Gugenheim
> wrote:
>
>> You realize that @tailrec is not required for a tail-recursive method to
>> be
>> rewritten? It's only purpose is, if you're not sure whether a method can
>> be
>> rewritten or not (or someone reading your code may be unsure), by
>> annotating
>> the method you are requiring the compiler to fail if it cannot be
>> rewritten,
>> thus ensuring that it will be rewritten. If you know the rules pretty well
>> and are writing code for yourself then most of the time you don't need it.
>>
>
> I realize that, which is part of why I find it a little bit annoying, i.e.
> it's essentially unnecessary when things are coded correctly.
>

On Fri, Nov 12, 2010 at 7:03 AM, Repain Alex <alex.repain@gmail.com> wrote:

"when things are coded correctly" is your failing assumption, I
guess...  "Help the compiler help you", is a very simple and reliable
axiom when you don't absolutely trust your abilities to code properly.

You misunderstand. I'm not saying the annotation is useless. I merely find it annoying to work with annotations that work in the negative. @switch works the same way, and in both cases I understand the reasoning, although I disagree with @tailrec. Stack overflows are too common and almost impossible to predict until your code fails at runtime at the most inconvenient, and potentially costly, moment.

On Fri, Nov 12, 2010 at 5:37 AM, Nils Kilden-Pedersen wrote:
> You misunderstand. I'm not saying the annotation is useless. I merely find
> it annoying to work with annotations that work in the negative. @switch
> works the same way, and in both cases I understand the reasoning, although I
> disagree with @tailrec. Stack overflows are too common and almost impossible
> to predict until your code fails at runtime at the most inconvenient, and
> potentially costly, moment.

if i follow, then +1 from me, along the lines of how @Override in Java
is really kinda sad.