This question is about the way that Scala does pattern matching and recursion with lists and the performance thereof.
If I have a function that recurses over a list and I do it with matching on a cons, for example something like:
def myFunction(xs) = xs match {
case Nil => Nil
case x :: xs => «something» myFunction(xs)
}
In Haskell:
myFunction [] = []
myFunction (x:xs) = «something» : myFunction xs
I'm using the same semantics as I would do with, for example, Haskell. I don't think there would be any question about the Haskell implementation as that's simply the way that you deal with lists. For a long list (I would be operating on a list with a few thousand nodes), Haskell wouldn't blink (I imagine though; I've never tried).
But from what I understand with Scala, the match statement would call the unapply extractor method to split the list around the cons and, to extend the example to a function that does nothing to the list:
def myFunction(xs) = xs match {
case Nil => Nil
case x :: xs => x :: myFunction(xs)
}
In Haskell:
myFunction [] = []
myFunction (x:xs) = x : myFunction xs
it would call apply extractor method to cons it back together. For a long list I imagine this would be very expensive.
To illustrate, in my specific case I want to recurse over a list of characters and accumulate various things, where the input string is anything up to a few tens of kilobytes.
Will I really be calling constructors and extractors for each step of the recursion if I want to recurse over a long list? Or are there optimisations? Or better ways to do it? In this case I would need several accumulator variables and obviously I wouldn't just be recursing over a list doing nothing…
(Please excuse my Haskell, I've not written a line for two years.)
(And yes, I'm going for tail recursion.)
Best Answer
First, Haskell is non-strict, so these function calls on the tail might never be evaluated at all. Scala, on the other hand, will compute all of the list before returning. A closer implementation to what happens in Haskell would be this:
That receives a
List
, which is strict, and returns aStream
which is non-strict.Now, if you want to avoid pattern matching and extractors (though none is called in this particular case -- see below), you might just do this:
I just realized you intend to go for tail recursion. What you wrote is not tail-recursive, because you prepend
x
to the result of the recursion. When handling lists, you'll get tail recursion if you compute the results backwards and then invert:Last, let's decompile an example to see how it works:
Generates:
Decoding, it first calls the method
equals
on the passed parameter and the objectNil
. Returns the latter if true. Otherwise, it callsinstanceOf[::]
on the object. If true, it casts the object to that, and invokes the methodtl
on it. Failing all that, loads the cosntantnull
and returns it.So, you see,
x :: xs
is not calling any extractor.As for accumulating, there's another pattern you might want to consider:
The default parameters and copy methods are a Scala 2.8 feature I used just to make the example simpler, but the point is using the
foldLeft
method when you want to accumulate things over a list.