netzwerg - 1 year ago 67
Scala Question

# Looking for an FP ranking implementation which handles ties (i.e. equal values)

Starting from a sorted sequence of values, my goal is to assign a rank to each value, using identical ranks for equal values (aka ties):

Input:

`Vector(1, 1, 3, 3, 3, 5, 6)`

Output:
`Vector((0,1), (0,1), (1,3), (1,3), (1,3), (2,5), (3,6))`

A few type aliases for readability:

``````type Rank = Int
type Value = Int
type RankValuePair = (Rank, Value)
``````

An imperative implementation using a mutable
`rank`
variable could look like this:

``````var rank = 0
val ranked1: Vector[RankValuePair] = for ((value, index) <- values.zipWithIndex) yield {
if ((index > 0) && (values(index - 1) != value)) rank += 1
(rank, value)
}

// ranked1: Vector((0,1), (0,1), (1,3), (1,3), (1,3), (2,5), (3,6))
``````

To hone my FP skills, I was trying to come up with a functional implementation:

``````val ranked2: Vector[RankValuePair] = values.sliding(2).foldLeft((0 , Vector.empty[RankValuePair])) {
case ((rank: Rank, rankedValues: Vector[RankValuePair]), Vector(currentValue, nextValue)) =>
val newRank = if (nextValue > currentValue) rank + 1 else rank
val newRankedValues =  rankedValues :+ (rank, currentValue)
(newRank, newRankedValues)
}._2

// ranked2: Vector((0,1), (0,1), (1,3), (1,3), (1,3), (2,5))
``````

It is less readable, and – more importantly – is missing the last value (due to using
`sliding(2)`
on an odd number of values).

How could this be fixed and improved?

This works well for me:

``````// scala
val vs = Vector(1, 1, 3, 3, 3, 5, 6)
val rank = vs.distinct.zipWithIndex.toMap
val result = vs.map(i => (rank(i), i))
``````

The same in Java 8 using Javaslang:

``````// java(slang)
Vector<Integer>                  vs = Vector(1, 1, 3, 3, 3, 5, 6);
Function<Integer, Integer>       rank = vs.distinct().zipWithIndex().toMap(t -> t);
Vector<Tuple2<Integer, Integer>> result = vs.map(i -> Tuple(rank.apply(i), i));
``````

The output of both variants is

``````Vector((0, 1), (0, 1), (1, 3), (1, 3), (1, 3), (2, 5), (3, 6))
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download