使用尾遞歸計算字符串中字符的出現

Question

我不知道如何使用scala中的尾遞歸來計算字符串中字符的出現次數。

我需要與輸入

times(explanation) 

運行程序並輸出結果是：

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

我試圖運行RLE，但迄今爲止尾遞歸的話題是新的給我，所以一些這樣做的步驟/算法將是完美的

Answer 1

可能的解決方案：

A字符串是一個字符列表。 按身份（x => x）對它們進行分組，然後對它們進行計數。 通常groupBy返回一個Map，它可以通過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))