Indexable data structures behind Scala's for comprehension

Question

I've just finished watching Week 6 of Martin Odersky's lectures about Scala on Coursera. In Lecture 5 he says that

"...the translation of for is not limited to lists or sequences, or even collections;

It is based solely on the presence of the methods map, flatMap and withFilter.

This lets you use the for syntax for your own types as well – you must only define map, flatMap and withFilter for these types."

The problem I'm trying to solve is that we have a batch process that loads data from a couple of databases, combines the data and exports the results in some way. The data is small enough to fit in memory (a couple of 100,000 records from each source system), but large enough that it is important to think about performance.

I could use a traditional in-memory database (like H2) and access it via ScalaQuery or something similar, but what I really need is just a way to be able to search and join data from the different source systems efficiently - equal to SQL's indexes and JOINs. It feels really awkward to use a full-blown relational database + a Scala ORM for something that could be solved easily and efficiently by some data structure that is native to Scala.

My first naive approach would be a Vector data structure (for fast direct access) combined with one or more "indexes" (which could be implemented as B-Trees just like in database systems). The map, flatMap, withFilter methods of this combined data structure could be intelligent enough to use an index if they have one for the queried field(s) - or they could have a "hint" to use one.

I was just wondering if such data structures already exist and are available, or do I need to implement them myself? Is there a library or a collection framework for Scala that solves this problem?

Answer 1

Not in the standard library (except for Vector, of course), and I don't know of any non-standard library providing them.