Scala, make my loop more functional

Question

I'm trying to reduce the extent to which I write Scala (2.8) like Java. Here's a simplification of a problem I came across. Can you suggest improvements on my solutions that are "more functional"?

Transform the map

val inputMap = mutable.LinkedHashMap(1->'a',2->'a',3->'b',4->'z',5->'c')

by discarding any entries with value 'z' and indexing the characters as they are encountered

First try

var outputMap = new mutable.HashMap[Char,Int]()
var counter = 0
for(kvp <- inputMap){
  val character = kvp._2
  if(character !='z' && !outputMap.contains(character)){
    outputMap += (character -> counter)
    counter += 1
  }
}

Second try (not much better, but uses an immutable map and a 'foreach')

var outputMap = new immutable.HashMap[Char,Int]()
var counter = 0
inputMap.foreach{
  case(number,character) => {
    if(character !='z' && !outputMap.contains(character)){
      outputMap2 += (character -> counter)
      counter += 1
    }
  }
}

Jessiajessica

Answer 1

Nicer solution:

inputMap.toList.filter(_._2 != 'z').map(_._2).distinct.zipWithIndex.toMap

Demmer

The nicer solution is nice! Fulfills all requirements in a compact and comprehensible way. (Personally, I'd map before filtering, but that's a nearly-trivial detail.) – Palliative

Answer 2

I find this solution slightly simpler than arjan's:

inputMap.values.filter(_ != 'z').toSeq.distinct.zipWithIndex.toMap

The individual steps:

inputMap.values       // Iterable[Char]   = MapLike(a, a, b, z, c)
   .filter(_ != 'z')  // Iterable[Char]   = List(a, a, b, c)
   .toSeq.distinct    // Seq[Char]        = List(a, b, c)
   .zipWithIndex      // Seq[(Char, Int)] = List((a,0), (b,1), (c,2))
   .toMap             // Map[Char, Int]   = Map((a,0), (b,1), (c,2))

Note that your problem doesn't inherently involve a map as input, since you're just discarding the keys. If I were coding this, I'd probably write a function like

def buildIndex[T](s: Seq[T]): Map[T, Int] = s.distinct.zipWithIndex.toMap

and invoke it as

buildIndex(inputMap.values.filter(_ != 'z').toSeq)

Biblioclast

Very nice. Particularly appreciate the comments in the second snippet. – Jessiajessica

Answer 3

First, if you're doing this functionally, you should use an immutable map.

Then, to get rid of something, you use the filter method:

inputMap.filter(_._2 != 'z')

and finally, to do the remapping, you can just use the values (but as a set) withzipWithIndex, which will count up from zero, and then convert back to a map:

inputMap.filter(_._2 != 'z').values.toSet.zipWithIndex.toMap

Since the order of values isn't going to be preserved anyway*, presumably it doesn't matter that the order may have been shuffled yet again with the set transformation.

Edit: There's a better solution in a similar vein; see Arjan's. Assumption (*) is wrong, since it was a LinkedHashMap. So you do need to preserve order, which Arjan's solution does.

Palliative

Answer 4

i would create some "pipeline" like this, but this has a lot of operations and could be probably shortened. These two List.map's could be put in one, but I think you've got a general idea.

inputMap
.toList // List((5,c), (1,a), (2,a), (3,b), (4,z))
.sorted // List((1,a), (2,a), (3,b), (4,z), (5,c))
.filterNot((x) => {x._2 == 'z'}) // List((1,a), (2,a), (3,b), (5,c))
.map(_._2) // List(a, a, b, c)
.zipWithIndex // List((a,0), (a,1), (b,2), (c,3))
.map((x)=>{(x._2+1 -> x._1)}) // List((1,a), (2,a), (3,b), (4,c))
.toMap // Map((1,a), (2,a), (3,b), (4,c))

performing these operation on lists keeps ordering of elements.

Vacuous

Answer 5

EDIT: I misread the OP question - thought you wanted run length encoding. Here's my take on your actual question:

val values = inputMap.values.filterNot(_ == 'z').toSet.zipWithIndex.toMap

EDIT 2: As noted in the comments, use toSeq.distinct or similar if preserving order is important.

val values = inputMap.values.filterNot(_ == 'z').toSeq.distinct.zipWithIndex.toMap

Jaclyn

The OP didn't ask for a run-length encoding. Reread the problem (or the code). – Palliative

True enough - read it too fast - edited. New solution looks a lot like all the others as would be expected. Cheers! – Jaclyn

As Rex pointed out in his own answer, toSet doesn't meet the requirements because it's not order-preserving. – Biblioclast

Ouch. I'm not sure the preserved ordering was a part of the requirement, but fair enough. I still like filterNot more than filter(_ != 'z'). – Jaclyn

Agreed, filterNot is more appropriate for this use case since the emphasis is on the elements to remove rather than the elements to retain. Personally, I tend to avoid filterNot just because I find that I have to mentally translate 'filterNot' to 'filter out' in order to make sense of it. – Biblioclast

Answer 6

In my experience I have found that maps and functional languages do not play nice. You'll note that all answers so far in one way or another in involve turning the map into a list, filtering the list, and then turning the list back into a map.

I think this is due to maps being mutable data structures by nature. Consider that when building a list, that the underlying structure of the list does not change when you append a new element and if a true list then an append is a constant O(1) operation. Whereas for a map the internal structure of a map can vastly change when a new element is added ie. when the load factor becomes too high and the add algorithm resizes the map. In this way a functional language cannot just create a series of a values and pop them into a map as it goes along due to the possible side effects of introducing a new key/value pair.

That said, I still think there should be better support for filtering, mapping and folding/reducing maps. Since we start with a map, we know the maximum size of the map and it should be easy to create a new one.

If you're wanting to get to grips with functional programming then I'd recommending steering clear of maps to start with. Stick with the things that functional languages were designed for -- list manipulation.

Command

Scala provides very nice immutable maps. The fact that many of the solutions convert to a list (note that Rex's does not, though) is more a consequence of the problem than any limitations involving maps. The OP doesn't seem to care about the original keys, so the input data structure might as well be a list. – Biblioclast

This comment doesn't answer the question and is factually incorrect (e.g. with a tree all but O(log(n)) of the tree stays intact when you update it). Besides, the OP's question is asking to apply an algorithm that is not inherently a mapping operation since the map is just to an index (which can be inferred from the order of appearance). So, of course, many solutions do not use maps. – Palliative

Ugh, my mistake. I only thought of hashmaps when looking at the question. I think also, I was unaware of the behaviour of a linkedhashmap (iterating by order of insertion). I think for my sanity. I'd like this question answered. Is the desired functionality to produce a map with keys/value mappings where by each key is not 'z' and whose value is the last time/index it was inserted into the map (excepting 'z' character inserts). – Command

The desired functionality is as you say, except the first time, not the last, and "time" is just a counter up from 0. – Palliative