A more idiomatic (Kotlin) way of creating an inverted index

[Junilu Lacar]

I've been working on one of the Kotlin projects at hyperskill.org, Simple Search Engine, and the second to last stage has a bit of a challenging requirement to create an inverted index. Here's what that's about:

Given a list of strings that represent entries in a phone book (one entry per line)

val entries: List<String> = 
   """|Dwight Joseph [e-mail]
      |Rene Webb [e-mail]
      |Katie Jacobs	
      |Erick Harrington [e-mail]
      |Myrtle Medina	
      |Erick Burgess""".trimMargin()
  .split("\n").toList()

You're supposed to create an inverted index, basically a Map<String, List<Int>> where the key are tokens extracted from the entries, i.e. each first name, last name, and email is a separate token, and the values are lists of indices of entries that contain that token.

Here's an example of my program running with the above input:

=== Menu ===
1. Find a person
2. Print all people
3. Print index
0. Exit
2

=== 6 people indexed ===
Dwight Joseph [e-mail]
Rene Webb [e-mail]
Katie Jacobs
Erick Harrington [e-mail]
Myrtle Medina
Erick Burgess

=== Menu ===
1. Find a person
2. Print all people
3. Print index
0. Exit
3
dwight=[0]
joseph=[0]
[e-mail]=[0]
rene=[1]
webb=[1]
[e-mail]=[1]
katie=[2]
jacobs=[2]
erick=[3, 5]
harrington=[3]
[e-mail]=[3]
myrtle=[4]
medina=[4]
burgess=[5]


(continued...)

[Junilu Lacar]

Here's the code I came up with to create the inverted index:

private fun index(people: List<String>): Map<String, List<Int>> {
    val invertedIndex = mutableMapOf<String, MutableList<Int>>()
    people.forEachIndexed { index, line ->
        line.split(" ").forEach { word ->
            invertedIndex.getOrPut(word.trim().toLowerCase()) { mutableListOf<Int>() }.add(index)
        }
    }
    return invertedIndex
}

This works and it's about as clean as I can get it with what I know (or can remember) for now. I'm just wondering if there's a better and maybe more idiomatic way to build the inverted index. I'm looking at some of the suggestions on SO (https://stackoverflow.com/questions/54232530/merge-values-in-map-kotlin) and a few look promising but right now I'm leaning towards taking a swing at this with groupingBy() and fold().

Would love to see what others might come up with.

[Mike Simmons]

Here's mine:

fun index(lines: List<String>): Map<String, List<Int>> = lines.withIndex()
        .flatMap { indexedLine -> indexedLine.value.trim().toLowerCase()
                .split(" ")
                .map { word -> IndexedValue(indexedLine.index, word) }
        }
        .groupBy({ it.value }, { it.index })

[Junilu Lacar]

Here's the incantation I came up with after quite a bit of fiddling around and Googling:

private fun index(people: List<String>): Map<String, List<Int>> =
    people.mapIndexed { index, entry -> entry.toLowerCase().split(" ")
        .associateWithTo(mutableMapOf<String, Int>()) { index }
    }.asSequence()
    .flatMap { it.asSequence() }.groupBy({ it.key }, { it.value })

The above works (at least it passes the tests and as far as I can tell, it generates the correct index)

Mike, your solution works, too, according to the tests.  

Got a few things to digest and fully understand. One thing that's kind of driving me nuts right now is figuring out how to format these darn chains.

Keep 'em coming, please!

[Junilu Lacar]

Here's my refactoring of Mike's code (just renamed and reindented):

private fun index(people: List<String>): Map<String, List<Int>> =
    people.withIndex().flatMap { person ->
        person.value.trim().toLowerCase().split(" ").map {
            word -> IndexedValue(person.index, word)
        }
    }.groupBy({ it.value }, { it.index })

Here's another refactoring using destructuring of IndexedValue

private fun index(people: List<String>): Map<String, List<Int>> =
    people.withIndex().flatMap { (index, person) ->
        person.trim().toLowerCase().split(" ").map {
            word -> IndexedValue(index, word)
        }
    }.groupBy({ it.value }, { it.index })

and actually, for consistency... (trying to put method to the madness)

private fun index(people: List<String>): Map<String, List<Int>> =
    people.withIndex().flatMap { (index, person) ->
        person.trim().toLowerCase().split(" ").map { word -> 
            IndexedValue(index, word)
        }
    }.groupBy({ it.value }, { it.index })

[Junilu Lacar]

It seems to me that Mike's and my versions vary only in some details (such as using vs not using Sequence). The verbs may be different but are essentially just different ways of saying the same thing. In the end, the results are the same. I'm kind of liking how Mike's version reads though.

[Mike Simmons]

Yeah, I've reformatted a bunch of different ways, and haven't settled on the "right" style really.  But in functional and stream-oriented programming I tend to favor formatting long method chains like this:

val x = something
    .someMethod()
    .someOtherMethod()
    .yetAnotherMethod()
    .areWeDoneYet()
    .nowWeAre()

It's weird at first, but quickly becomes very readable, I think.  Of course, once those method calls then require multiline blocks in their argument lists, well then there are many more formatting questions to resolve.

Your destructuring of the IndexedValues is a nice improvement - I'd forgotten about that.

[Junilu Lacar]

Here's what I guess I'm starting to settle on around formatting and indentation:

private fun index(people: List<String>): Map<String, List<Int>> =
    people.withIndex().flatMap { (index, person) ->               
        person.trim().toLowerCase().split(" ").map { word -> 
            IndexedValue(index, word)
        }
    }.groupBy({ it.value }, { it.index })

Starting at line 2, people.withIndex().flatMap is the top level structure, kind of like an outer for-loop. The iteration parameters, (index, person) are placed on the same line.

Lines 3-5 are indented one level because it's essentially the body of the "for-loop"

Line 3 has a nested structure, person.trim().toLowerCase().split(" ") and the .map starts another iteration. Again, the iteration parameter, word is placed on the same line.

Line 4 is indented another level because it's the "body" of the "nested loop" or iteration that starts on line 3.

On line 6, I keep the final operations that apply to the result of the "outer loop" started on line 2 on the same line as the close } -- I might drop it down to the next line if there are more operations in the chain and format those as Mike showed.

Given that there's a bit of a paradigm shift in going from imperative to functional, I don't know if the above indentation approach is helpful in making that shift or if in fact it's keeping me in a weird no-man's-land between the two paradigms. I know it helps me understand what's going on better for now because my brain still works very much in terms of for-loops and if-then-else statements. Forcing your brain to think differently is fun but challenging as well.

[Mike Simmons]

I feel like there's no need to hold on to the old notion of what a "loop" looks like, especially given that lambdas can often be replaced my method references - if

stream.map { x ->
    foo()
}.bar()

can be replaced with

stream.map(::foo).bar()

I'm not going to make that

stream.map(
    ::foo
).bar()

and, given the above, I see nothing at all wrong with this either:

stream.map{x -> foo()}.bar()

Though I haven't really decided how much space, if any, I need around curly braces.  Depends on my mood.


Here's another formatting of the code that I like:

fun index(lines: List<String>): Map<String, List<Int>> = lines
        .withIndex()
        .flatMap(::indexWordsInLine)
        .groupBy({word ->  word.value }, { word -> word.index })

private fun indexWordsInLine(line: IndexedValue<String>): List<IndexedValue<String>> =
        line.value.trim()
                .toLowerCase()
                .split(" ")
                .map { word -> IndexedValue(line.index, word) }

Yes, this approach to method chain formatting may seem a bit extreme - but I find it very clean and consistent.  Code takes up more lines, but less width, which is neither here nor there.   And extracting a method is a nice way to introduce a method name to summarize what's going on in an important intermediate step.

[Piet Souris]

My style is like loopings indeed. I don't speak Kotlin (never will, I'd rather learn a completely different language like Cobol). Taking into account that java lacks these 'indexed' things, I got this:

var result = IntStream.rangeClosed(1, persons.size())
    .boxed()
    .flatMap(i -> persons.get(i - 1)
                  .parts()
                  .map(s -> new Pair<>(s, i))
            )
    .collect(groupingBy(p -> p.getKey(),
                        mapping (p -> p.getValue(), toList())
                       )
    )
;

where my Person class has the method

public Stream<String> parts() {
    return Stream.of(firstname, secondname, telnr);
}

and Pair is the JavaFX Pair class.

[Mike Simmons]

For what it's worth, those IndexedValue classes are just another type of Pair, where the members are called index and value.

[Piet Souris]

Thanks for the info.

[Stephan van Hulst]

I prefer to put each chained method call on a separate line when writing functional code in Java. This is hard to marry with the use of lambda expressions, because their syntax kind of messes up the formatting. This is how I'd format your code Junilu.

private fun index(names: List<String>): Map<String, List<Int>> =
  names.withIndex()
       .flatMap { (index, name) ->
         name.trim()
             .toLowerCase()
             .split(" ")
             .map { IndexedValue(index, it) } }
       .groupBy( { it.value }, { it.index } )

There is no hard and fast rule to the formatting. I use something different every time I write a piece of functional code. It depends on what looks good for that particular code snippet.

Lambdas are the culprit. Thankfully, Kotlin has local functions. Use lambdas only for one-liners. If your expressions become more complex, use a local function:

private fun index(names: List<String>): Map<String, List<Int>> {
  fun associateNamePartsWithIndex(index: Int, name: String): Iterable<IndexedValue<String>> =
    name.trim()
        .toLowerCase()
        .split(" ")
        .map { IndexedValue(index, it) }

  names.withIndex()
       .flatMap(::associateNamePartsWithIndex)
       .groupBy( { it.value }, { it.index } )
}

Disclaimer: I don't know Kotlin. The code above might contain syntax errors.

[Junilu Lacar]

I have to admit that I've gotten a little bit Perl-ish with Kotlin, wanting to keep the code down to the fewest possible lines and still have the clarity of expression the functional-style is supposed to give. There are just so many ways to do the same thing though and I'm still trying to figure out what's idiomatic. Then again, there may not be one idiomatic way and maybe that's the point, too. Take the operator overload function for matrix multiplication below. Matrix is a class I've defined; this function overloads the * operator for it so I can just write simpler high-level code:

operator fun times(other: Matrix): Matrix? {
   if (this.cols != other.rows) return null
   val product = Matrix(this.rows, other.cols)
   val otherColumns = other.transpose()
   for (row in 0 until this.rows) {
      for (col in 0 until other.cols) {
         product[row][col] = product(values[row], otherColumns[col])
      }
   }
   return product
}

// Usage:
val (matrixA, matrixB) = Pair(readMatrix(), readMatrix())
val matrixAB = matrixA * matrixB

// times() also overloaded to allow scalar multiplication
val λ = readDouble()
val matrixAλ = matrixA * λ

// and an extension function for Double.times() to make it commutative
val matrixλA = λ * matrixA
println(matrixλA == matrixAλ) // true

The nested for-loop on lines 5-9 can be rewritten in at least two ways:
(0 until this.rows).forEach { row ->   (0 until this.cols).forEach { col ->       product[row][col] = product(values[row], otherColumns[col])   } }
and
repeat(this.rows) { row ->   repeat(this.cols) { col ->       product[row][col] = product(values[row], otherColumns[col])   } }
That's just the imperative style way of doing it. I'm sure there's a more functional way but I just haven't found the right incantation yet.

Line 14 shows another trick I've found to cut down one line of code using destructuring. If you use a Triple() this way, you can reduce 3 lines down to one. Then there's Line 2, which is the guard clause. If this were Java code, I'd normally make that take up 3 lines, like so:
if (this.cols != other.rows) {   return null }
But then this slowly building Perl-ish desire for brevity pushes me into making it a one-liner in Kotlin.

[Stephan van Hulst]

Junilu, if you really want to challenge yourself to write purely functional, you must keep the following rule in mind: You may only use the assignment operator when declaring a variable. Statements like the one on line 7 are out of the question.

[Junilu Lacar]

Stephan van Hulst wrote:You may only use the assignment operator when declaring a variable. Statements like the one on line 7 are out of the question.

Thanks, Stephan. It feels a bit uncomfortable though, the thought of replicating an entire matrix just to change one element. Thoughts of premature optimization probably but the feeling is undeniable and hard not to listen to. I'm sure it's just a phase that I'll (hopefully) get past.

[Mike Simmons]

Hm, I feel like a matrix is a really good example where insisting on immutability everywhere is likely to lead to very very bad performance, for precisely the reason you cite, Junilu.  Which may make it an interesting exercise as a learning challenge, but let's not be surprised too much if it doesn't work well.    That said though, it may work better if you focus on bulk operations, e.g. adding and multiplying entire matrices, rather than a new matrix every time you set one single element.  Or even, is there a way to build a list of such operations, and then process them all one after another?  Similarly to how we build Streams that don't execute anything until a terminal operation is called.

[Mike Simmons]

And now I see that's the direction you seem to be heading in this thread: https://coderanch.com/t/729490/languages/Designing-immutability-Matrix-class-Kotlin

Cool.