5

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 } } }
Improve this question

6 Answers 6

Reset to default
11

Nicer solution:

inputMap.toList.filter(_._2 != 'z').map(_._2).distinct.zipWithIndex.toMap
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

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.)
9

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)
Improve this answer

1 Comment

Very nice. Particularly appreciate the comments in the second snippet.
5

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.

Improve this answer

Comments

3

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.

Improve this answer

Comments

2

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
Improve this answer

5 Comments

The OP didn't ask for a run-length encoding. Reread the problem (or the code).
True enough - read it too fast - edited. New solution looks a lot like all the others as would be expected. Cheers!
As Rex pointed out in his own answer, toSet doesn't meet the requirements because it's not order-preserving.
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').
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.
-2

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.

Improve this answer

4 Comments

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.
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.
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).
The desired functionality is as you say, except the first time, not the last, and "time" is just a counter up from 0.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.