Scala Non-Tail Recursive Solution

Question

I have this tail-recursive function that returns true if any element in the list is a Boolean value.

def anyBoolTailRec[A](test: A=> Boolean, a: List[A]): Boolean = a match {
    case Nil => false
    case h :: t if(!test(h)) => anyBoolTailRec(test, t)
    case _ => true
}

The test parameter is just a function to check the values type:

def isBool(i: Any) = i match {
    case _: Boolean => true
    case _    => false
}

The function is called like this:

anyBoolTailRec(isBool, List(1, 2, "hi", "test", false))
>>> true

Question: How can I turn this tail recursive solution into a non-tail recursive solution? Since we're returning Booleans I'm not sure how to do it.

Note: I am aware tail-recursive solutions are better in Scala.

change second line to `case h :: t if(!test(h)) => val foo = anyBoolTailRec(test, t); foo` Is the next question going to be how to make it exponential? — Dima, Oct 06 '17 at 20:28
How to make it exponential? No I was just wondering how I could change my function into non-tail solution. The boolean return value was throwing me off. I'm using to doing something like foo(test, t + 1) — Phil, Oct 06 '17 at 20:34
Why are you asking things twice? You already asked about this topic: https://stackoverflow.com/questions/46598594/scala-tail-recursive-to-not-tail-recursive — The Archetypal Paul, Oct 07 '17 at 16:56

puhlen · Accepted Answer · 2017-10-06T20:51:58.997

3

There's no reason to do this. You're just making your code worse for no benefit, but...

Turning a tail-recursive solution into a non-tail recursive is easy. You could just add some operation that doesn't affect the result so that the recursive call is no longer in a tail position. A simple solution that will always work is to store the result of the recursive call in a local variable before returning it.

def anyBoolTailRec[A](test: A=> Boolean, a: List[A]): Boolean = a match {
    case Nil => false
    case h :: t if(!test(h)) => val foo = anyBoolTailRec(test, t); foo
    case _ => true
}

edited Oct 06 '17 at 20:51

answered Oct 06 '17 at 20:29

puhlen

8,400
1
16
31

Makes sense! Thanks. But since we're evaluating false in the second line with `|| false` is there a need for case Nil anymore? – Phil Oct 06 '17 at 20:30
1

@Phillip Yes, without the `Nil => false` case, `Nil` would evaluate to true, since it doesn't match the pattern `h :: t` it would fall to the default case `_ => true`. – puhlen Oct 06 '17 at 20:34
@Phillip Dima's comment provides a more general solution that will work for any data type while mine would only work for booleans, I will edit my answer to include his method. – puhlen Oct 06 '17 at 20:35

Scala Non-Tail Recursive Solution

1 Answers1