Hacker News Reader

Comment by mark242 | Hacker News Reader

Here's a more functional version of complete_items, if you're interested.

  def complete_items(...) = bin.items.flatMap((item, v) => 
    expectedSymbol(item).map(nonterminal => 
      grammar.nextValue(document, item.origin, bin.binindex, completed_binindex, nonterminal, item.ruleindex, item.dot, v, value)
        .map(nextvalue => (item.inc -> nextvalue)
    )
  )

View on HN

What can I say, I like my loops :-)

http://arxiv.org/abs/1007.3023

Loops obviously have their place, no question, but you're going to find that assigning a List to a var, and then appending to it / re-assigning it is going to generate a ton of garbage, and in general will just be slow all around. There's a reason that prepending/appending to Lists is "strange" in Scala. This is why map and flatMap are so great, because they take care of a lot of that heavy lifting for you (eg the matcher on None/Some -- this is what map is made for!).

There is no performance difference here, map etc. are producing the same garbage. Scala isn't Haskell. Also note that there is a HUGE performance difference between appending and prepeding to a list. :-)

If you need to append, use a Vector instead.

> Also note that there is a HUGE performance difference between appending and prepeding to a list. :-)

If you're going to do a lot of appending, might I suggest a ListBuffer or a Vector?

I don't think that's right.

TraversableLike, and FilterMonadic will both size up the resulting return value based upon the length of what's passed to it. You'll get a List of N items, and the call to flatMap will also traverse the list to remove/flatten the Options. Items will then get dropped in the List. You're looking at one or two collectable objects every time you run through that method, as opposed to bin.items.length collectable objects in your original code.

Look at it this way-- what happens if bin.items is a List() of 10M objects? completed_items can be replaced up to 10M times. The .flatMap creates one collection of 10M length, removes the None objects, and returns the resulting List.

If you like loops, here it is with a for-comprehension:

  def complete_items(completed_binindex: Int, bin: ItemBin, nonterminal: Nonterminal, value: Value): MoreItems = {
    for {
      (item, v) <- bin.items
      _ <- expectedSymbol(item)
      nextValue <- grammar.nextValue(document, item.origin, bin.binindex, completed_binindex,
        nonterminal,item.ruleindex, item.dot, v, value)
    } yield {
      item.inc -> nextvalue
    }

Reply on news.ycombinator.com