2

How can I recurse through a Map?

I'm looking for something similar to list recursion, shown below.

def count(list: List[Int]): Int = { 
   def go(list: List[Int], acc: Int)) = {
      case x :: xs => go(xs, x + sum)
      case Nil => sum
   }
   go(list, 0)
}

Please ignore the fact that fold or reduce could be used here. I'm mentioning this tail-recursive function as a sample as to what I'd like for recursing through a map. I want to be able to append to an accumulator argument when recursing through a map.

4
  • 2
    You can call .toList on your map, yielding a list of (key, value) Pairs, then recursing through the list. Convert back to a map at the end. Oct 14, 2013 at 21:37
  • 1
    Map.keys() is an Iterable, so you can use it in the same way you use your list parameter.
    – Ashalynd
    Oct 14, 2013 at 22:40
  • 1
    I'd recommend calling .toStream on the map since Streams are lazy. That way you don't have the overhead of creating a whole list up-front, especially if you're not going to traverse the whole thing in your recursive function.
    – DaoWen
    Oct 14, 2013 at 23:01
  • fold is actually usually quite good when you want to use an accumulator. can you explain more why fold doesn't fit your use case?
    – nnythm
    Oct 15, 2013 at 8:27

1 Answer 1

0

You can turn the Map into a Seq with .toSeq or .toList or similar, or you can define your own Map extractor, but the easiest is to just use head and tail directly.

def recursive[A, B](map: Map[A, B]): Int = 
  if (map.isEmpty) 0 else helper(map)

def helper[A, B](map: Map[A, B]): Int = (map.head, map.tail) match {
  case ((a, b), xs) if xs.isEmpty => 1
  case ((a, b), xs) => 1 + helper(xs)
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.