title: Scala list recursion performance
body: <p>This question is about the way that Scala does pattern matching and recursion with lists and the performance thereof.</p>
  
  <p>If I have a function that recurses over a list and I do it with matching on a cons, for example something like:</p>
  
  <pre><code>def myFunction(xs) = xs match { 
    case Nil =&gt; Nil
    case x :: xs =&gt; «something» myFunction(xs)
  }
  </code></pre>
  
  <p>In Haskell:</p>
  
  <pre><code>myFunction [] = []
  myFunction (x:xs) = «something» : myFunction xs
  </code></pre>
  
  <p>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). </p>
  
  <p>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:</p>
  
  <pre><code>def myFunction(xs) = xs match { 
    case Nil =&gt; Nil
    case x :: xs =&gt; x :: myFunction(xs)
  }
  </code></pre>
  
  <p>In Haskell:</p>
  
  <pre><code>myFunction [] = []
  myFunction (x:xs) = x : myFunction xs
  </code></pre>
  
  <p>it would call apply extractor method to cons it back together. For a long list I imagine this would be very expensive.</p>
  
  <p>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. </p>
  
  <p>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...</p>
  
  <p>(Please excuse my Haskell, I've not written a line for two years.)</p>
  
  <p>(And yes, I'm going for tail recursion.)</p>