スカラの戻り値が期待通りではない

Question

Scalaを学んで、リスト内のすべての括弧を一致させバランスを取るために、括弧の数をカウントする関数（再帰的）を作成しています。の文字。かっこが均衡している場合は0を返します。

私は（上で何が起こっているのかを理解するために、多数のprint文で）それを思い付いた：

def countPar(charList: List[Char], count: Int): Int = { 

    if (count < 0) { 
    println("negative count, returning", count) 
    count 
    } 
    else if (charList.isEmpty) { 
    println("empty list, returning", count) 
    count 
    } 
    else if (charList.head.equals('(')) { 
    println("head is ", charList.head, " count + 1:", count + 1) 
    count + countPar(charList.tail, count + 1) 
    } 
    else if (charList.head.equals(')')) { 
    println("head is ", charList.head, " count - 1:", count - 1) 
    count + countPar(charList.tail, count - 1) 
    } 
    else { 
    println("head is ", charList.head, " count:", count) 
    countPar(charList.tail, count) 
    } 
} 

val parCount = countPar("(a(b)c)".toList, 0) 

println(parCount) 

print文ははロジックが動作していることを確認するように見える、まだ最終的な戻り値が間違っていますか：

(head is ,(, count + 1:,1) 
(head is ,a, count:,1) 
(head is ,(, count + 1:,2) 
(head is ,b, count:,2) 
(head is ,), count - 1:,1) 
(head is ,c, count:,1) 
(head is ,), count - 1:,0) 
(empty list, returning,0) 
parCount: Int = 4 

私は何が欠けていますか？

Answer 1

countPar(charList.tail, count + 1)の代わりにcount + countPar(charList.tail, count + 1)を返すだけです（閉じ括弧も同様です）。

再帰関数のポイントは、先頭の値に従ってカウントを更新し、それをテール値に基づいて更新する再帰呼び出しに渡すことです（再帰呼び出しは同じことを行います。尾は空です）。つまり、再帰呼び出しは正しい結果を返します。何も追加する必要はありません。

編集：あなたは現在コーディングしている

def countPar(charList: List[Char], count: Int): Int = { 
    if (count < 0) { 
    println("negative count, returning", count) 
    count 
    } else if (charList.isEmpty) { 
    println("empty list, returning", count) 
    count 
    } else { 
    val updatedCount = 
     if (charList.head.equals('(')) 
     count + 1 
     else if (charList.head.equals(')')) 
     count - 1 
     else 
     count 
    println(s"head is ${charList.head}, count: ${updatedCount}") 
    // We see here that the reursive call is the same in the 3 cases: the 
    // only difference is how we update the count 
    countPar(charList.tail, updatedCount) 
    } 
} 

Answer 2

：私はそうのようにリファクタリングたら、それはまた明確になると思います （重要な部分は、コメント付き1は、私がそうでなければ、あなたのアプローチを変えないようにした場合）非常に不可欠な/オブジェクト指向のスタイルです。しかし、これは機能的、再帰的なアプローチを求めて：私たちの外側の関数はそれの署名との質問に答えている

def isBalanced(string: List[Char], count: Int=0): Boolean = { 
    if (count < 0) { false } // We can only be balanced if (precedes) 
    else { 
    string match { 
     case Nil => count == 0 // Is the count 0? If so, however we got here was balanced! 
     case '('::tail => isBalanced(tail, count + 1) // (prepended to some list 
     case ')'::tail => isBalanced(tail, count - 1) //) prepended to some list 
     case _::tail => isBalanced(tail, count) 
    } 
    } 
} 

注：任意の文字のリストを与え、そのリストをバランスさ？ （ 'yesまたはno'はブール値を意味します：整数を使用すると、この関数のユーザにとっては複雑なものになります）。すべての再帰関数と同様に、関数は質問を自明に解決できるかどうかを調べ、再帰呼び出しの結果を単純に返します。

まず、のベースケースを定義します。つまり、リストが空であれば、カウントが0であるかどうかを返します。そうであれば、括弧がバランスされていることがわかります。

次に、の再帰的ケースを定義します。ここでは、isBalancedが正しい結果を返し、異なる増分のみを処理すると信じています。これら2つの行は次のように処理されます。

case '('::tail => isBalanced(tail, count + 1) 
case ')'::tail => isBalanced(tail, count - 1) 

それぞれで、それに応じてカウントが増減します。最後の行（case _::tail）は他のすべてのケースを処理しますが、最終結果には影響しません。

Scalaの強力なケースマッチング機能（match）を使用すると、これは非常に簡単です。試合の前に簡単なガードを置くことで、バランシングがマイナスになったときに早く終了するようにすることができます。それは文字列入力に対してパターンマッピングの問題です。これはfarです。無限のif-else節を使用するよりも明確です。

また、デフォルトのパラメータ値を作成するためには、0を渡す必要はありません。これにより、インタフェースを明確にしながら、関数を再利用できるようになります。印刷ログライン上

isBalanced("((()))".toList) // true 
isBalanced(")))(((".toList) // false 
isBalanced("(()())".toList) // true 
isBalanced("((()())".toList) // false 
isBalanced("Foo() bar()".toList) // true 

注：あなたはケースマッピングが起こっているか追跡するためにこれを行う、またはケース句内の任意の体操を行う必要がある場合、あなたはこれを行うことができ正しさを証明するために

：

def isBalanced(string: List[Char], count: Int=0): Boolean = { 
    if (count < 0) { false } 
    else { 
    string match { 
     case Nil => count == 0 
     case '('::tail => { 
     println("Found an open paren") 
     isBalanced(tail, count + 1) 
     } 
     case ')'::tail => { 
     println("Found a close paren") 
     isBalanced(tail, count - 1) 
     } 
     case _::tail => isBalanced(tail, count) 
    } 
    } 
}