@tailrec private def sameLength[T, U](xs: List[T], ys: List[U]): Boolean = { if (xs.isEmpty) ys.isEmpty else ys.nonEmpty && sameLength(xs.tail, ys.tail) }
On a quick glance, this did not appear to be tail recursive to me, as there is the && operation that needs to be called after the recursive call.
However, thinking a little more about it, && is a short-circuit operator and the recursive operation would get called only if the ys.nonEmpty statement evaluates to true, thus maintaining the definition of a tail recursion.
The decompiled class clarifies this a little more, surprisingly the && operator does not appear anywhere in the decompiled code!:
public <T, U> boolean org$bk$sample$SameLengthTest$$sameLength(List<T> xs, List<U> ys) { for (; ys.nonEmpty(); xs = (List)xs.tail()) ys = (List)ys.tail(); return xs.isEmpty() ? ys.isEmpty() : false; }
If the operator were changed to something that does not have short-circuit behavior, the method of course will not be a tail-recursion at that point, say a hypothetical method with the XOR operator:
private def notWorking[T, U](xs: List[T], ys: List[U]): Boolean = { if (xs.isEmpty) ys.isEmpty else ys.nonEmpty ^ notWorking(xs.tail, ys.tail) }
Something fairly basic that tripped me up today!
No comments:
Post a Comment