Подсчет вхождения символов в строке с использованием хвостовой рекурсии

Question

У меня нет понятия, как подсчитывать вхождения символов в строке, используя хвостовую рекурсию в scala.

мне нужно запустить программу с входом

times(explanation) 

и выход:

List((e,1), (x,1), (p,1), (l,1), (a,2), (n,2), (t,1), (i,1), (o,1)) 

Я попытался запустить РЛЭ до сих пор, но тема хвостовой рекурсии ново для меня, так что некоторые шаги/алгоритм для этого был бы идеальным

Answer 1

Возможные решения:

Строка - это список символов. Группируйте их по идентификатору, который является (x => x), а затем подсчитайте их. Обычно groupBy возвращает карту, которая может быть преобразована в список кортежей toList.

код/​​не изобретать колесо

def times(s: String) = s.groupBy(identity).mapValues(_.size).toList 
times: (s: String)List[(Char, Int)] 

Пример

times("explanation") 
res1: List[(Char, Int)] = List((e,1), (x,1), (n,2), (t,1), (a,2), (i,1), (l,1), (p,1), (o,1)) 

код с хвостовой рекурсией/изобретает колесо /, пожалуйста, используйте не обмануть в Coursera Scala Курс

import scala.annotation.tailrec 

def myTimes(s: String) : List[(Char,Int)] = { 

    @tailrec // comiler cheks if really tailrecursive 
    def timesTail(chars: List[Char], res: List[(Char,Int)]) : List[(Char,Int)] = 
    chars match { 
     case Nil => res  // we are done when there are no characters left 
     case char :: rest => { 
      // otherwise 
      val newCharCount = 
      res. 
       find (_._1 == char). //check if we already have seen the character 
       map{ case (c,count) => (c,count + 1) }. // if yes, we raise take the old count and raise it by one 
       getOrElse((char,1)) // otherwise we count one occurrence 
      // here it gets recursive 
      timesTail(
       rest, // remaining Characters 
       newCharCount :: res.filterNot(_._1 == char) // add the new count to list, remove old if present 
     ) 
     } 
    } 
    // initial call with empty lsit to start the helper function 
    timesTail(s.toList,List()) 

} 

Answer 2

Эффективный, это не так. Но он является хвостовым рекурсивным, и результат находится в том же порядке, что и в вопросе, в случае, если это имеет значение. Если это не задание, то лучшим решением будет решение от Andreas groupBy.

def times(s: String) = { 
    def timesRecurse(s: String, result: List[(Char, Int)]): List[(Char, Int)] = { 
     if (s.isEmpty) 
     result 
     else { 
     val c = s.head 
     val i = result.indexWhere(_._1 == c) 
     timesRecurse(s.tail, 
      if (i == -1) 
       (c, 1) :: result 
      else 
      result updated (i, (c, result(i)._2 + 1))) 
     } 

    } 
    timesRecurse(s, List[(Char, Int)]()).reverse 
    } 

    times("explanation") 
    //> res0: List[(Char, Int)] = 
    // List((e,1), (x,1), (p,1), (l,1), (a,2), (n,2), (t, 1), (i,1), (o,1))