ネストされたパターンマッチング - 例を介したステップ実行と非常に混乱している

Question

パターンマッチングと再帰、およびプログラムの実行方法を理解しようとしています。

単純なケースで

：私は上記のsum_list_num [1,2,3,4,5];に復帰されるようSOME yでy1は、基本的にはアキュムレータとして機能していることを確認でき

fun sum_list_num xs = 
    case xs of 
     [] => NONE 
    | x::xs' => case (sum_list_num xs') of 
        NONE => (print "x: "; print (Int.toString x); 
          print "\n"; SOME x) 
        | SOME y => (print "x: "; print (Int.toString x); 
           print " y: "; print (Int.toString y); print"\n"; 
           SOME (x+y)) 

：

x: 5 
x: 4 y: 5 
x: 3 y: 9 
x: 2 y: 12 
x: 1 y: 14 
val it = SOME 15 : int option 

私は右にアムそれを考えているのか、私はそのマークを見逃したのでしょうか？。

もっと進んだ例として、私はパターンマッチングの周りを頭で覆いたいと思っています。this postに出くわしましたが、頭や尾を作ることはできません。

fun smatch (str, in_stringlist) = 
    case in_stringlist of 
     [] => NONE 
    | x::x' => case(same_string(x, str), smatch (str, x')) of 
        (true, _) => (print "MATCH CASE x: "; print x; 
            print " x': "; print(gather(x')); 
           print "\n"; SOME x') 
       | (false, NONE) => (print "NONE CASE x: ";print x; 
            print "\n"; NONE) 
       | (false, SOME z) => (print "SOME Z CASE x: "; print x; 
             print " z: ";print(gather(z)); 
             print " x': ";print(gather(x'));print "\n"; 
             SOME (x :: z)) 

私は迷ってしまいましたsmatch("this", ["1", "2", "this", "4", "5", "6"])

NONE CASE x: 6 
NONE CASE x: 5 
NONE CASE x: 4 
MATCH CASE x: this x': 4 5 6 
SOME Z CASE x: 2 z: 4 5 6 x': this 4 5 6 
SOME Z CASE x: 1 z: 2 4 5 6 x': 2 this 4 5 6 
val it = SOME ["1","2","4","5","6"] : string list option 

を使用して呼び出されたときに、私は全く期待していなかった出力：私は、各「一致」で何が起こっているのかプリントアウトする機能を変更した

• なぜ大文字小文字の区別でx'が返されますか？
• 私が探している文字列がNONEの場合に評価された後に、リストのすべてが表示されるのはなぜですか？
• 私はここに座っていて、多くの編集をしてきました。再帰呼び出しを積み重ねて評価する方法で正確に何が起こっているのか厳しい時間がありました。

助けていただければ幸いです。 SMLガイドを読んで一日中パターンマッチングを行っても、これは明確になりませんでした。

注：2番目の例はCourseraクラスの宿題です（ネストされたcase文ではなくリストを構築するlet関数を使って答えました。 SMLと私の頭を1日中包むようにしている）。

FYI集まるので、私は、文字列のリストの内容をプリントアウトすることができますちょうどヘルパー関数です：

fun gather xs = 
    foldl (fn (x,acc) => 
      acc^" "^x) (hd xs) (tl xs) 

Answer 1

私はSOME yでy1は、基本的には、アキュムレータ

として機能していることがわかります

私はそれを考えているか、マークを逃したのですか？

はい、あなたは正しいです。

関数sum_list_numは、自身を再帰的に呼び出して、累積結果を自身に返します。結果はSOME/NONEにラップされているので、パターンマッチングを使用して結果を解凍し、再びにパックし直します。例えば。 SOME yはSOME (x+y)になります。空のリストの合計が明確に定義されているので

戻るint型のオプションは、少し余計ようだ：

fun sum_list_num [] = 0 
    | sum_list_num (x::xs) = x + sum_list_num xs 

それとも

fun sum_list_num xs = foldl op+ 0 xs 

しかし、いくつかの問題のためにあなたががしたいですか

結果としてSOME/NONEのパターンマッチを行い、その結果をパックし直します。そのような場合は、ライブラリ関数の使用を検討することもできますOption.mapおよびOption.getOpt。たとえば、次のように

fun maximum [] = NONE 
    | maximum [x] = SOME x 
    | maximum (x::xs) = Option.map (fn y => Int.max (x, y)) (maximum xs) 

は、なぜ私は試合のケースでx'を返しています、

fun smatch (str, in_stringlist) = 
    case in_stringlist of 
     [] => NONE 
    | x::x' => case(same_string(x, str), smatch (str, x')) of 
        (true, _) => (print "MATCH CASE x: "; print x; 
            print " x': "; print(gather(x')); 
           print "\n"; SOME x') 
       | (false, NONE) => (print "NONE CASE x: ";print x; 
            print "\n"; NONE) 
       | (false, SOME z) => (print "SOME Z CASE x: "; print x; 
             print " z: ";print(gather(z)); 
             print " x': ";print(gather(x'));print "\n"; 
             SOME (x :: z)) 

を上に移動？

この機能は何をしていますか？それ以来、その回答の一部は "..."となり、残りのリスト（x'）を返します。 "読むのが難しいこのコードの一部は、それぞれのループでsmatch (str, x')が評価されていると思います反復は、戻り値が使用されるかどうかに関係なく、ケース本体の前に置かれます。

入力リストの末尾を最初に処理することにより、それは後方に（設計上または事故によって）処理されます。

私が探している文字列の後のリストのすべてがNONEに評価されているのはなぜですか？

これは、おそらく、小さな入力に対して手作業で関数を評価することによって最もよく示されます。私は~>を書くたびに、私は次の用語（そのすべての入力が評価された場合、それが実行される前関数への入力、または関数呼び出しを評価したきた最初のいくつかの用語の書き換えは以下の通りです。

smatch ("2", ["1", "2", "3"]) ~> 
    case (same_string("2", "1"), smatch ("2", ["2", "3"])) of ... ~> 
    case (false, smatch ("2", ["2", "3"])) of ... ~> 
    case (false, case (same_string("2", "2"), smatch ("2", ["3"])) of ...) of ... ~> 
    case (false, case (true, case (same_string ("2", "3"), smatch ("2", [])) of ...) of ...) of ... ~> 
    case (false, case (true, case (false, smatch ("2", [])) of ...) of ...) of ... ~> 
    case (false, case (true, case (false, NONE) of ...) of ...) of ... 

でこの点はリストが完全に横断されており、最後の要素は"2"ではないと判断され、一致するペア（(false, NONE)）が実際に比較されているcase-ofステートメントの最初のケース...

case (false, case (true, (print "NONE CASE x: ";print x; print "\n"; NONE)) of ...) of ... ~> 
    case (false, case (true, NONE) of ...) of ... ~> 
    case (false, (print "MATCH CASE x: "; print x; print " x': "; print(gather(x')); print "\n"; SOME ["3"])) of ... ~> 
    case (false, SOME ["3"]) of ... ~> 

この時点で、(false, NONE)パターンの場合が最初に一致しましたが、その後、(true, _)パターン、そして最終的に(false, SOME z)パターン：私は紙と多くの編集のパッドでここに座ってきたと私は正確で何が起こっている「次」タフな時間を過ごしてい

(print "SOME Z CASE x: "; print x; print " z: "; print(gather(z)); print " x': "; print(gather(x')); print "\n"; SOME ("1" :: "3")) ~> 
SOME ["1", "3"] 

どのように再帰呼び出しがスタックされ、評価されているかを示します。

あなたの関数を手で評価するだけではなく（あなたの用語書き換えが大規模なケースでは困難です）、あなたのコードを別に構造化することができます。実際の要素実際にネストされたパターンマッチングの必要性はないようです。この機能は本当にただstrの最初のインスタンスをフィルタリングするため、そして、なぜそれが好きで書かないで：

は

fun smatch (str, []) = [] 
    | smatch (str, str2::strs) = 
    if str = str2 
    then strs 
    else str2::smatch(str, strs) 

この機能は、手で評価する方がはるかに簡単です：ところで

smatch ("2", ["1", "2", "3"]) ~> 
    if "2" = "1" then ... else "1"::smatch("2", ["2", "3"]) ~> 
    "1"::smatch("2", ["2", "3"]) ~> 
    "1"::(if "2" = "2" then ["3"] else ...) ~> 
    "1"::["3"] 
    ["1", "3"] 

、あなたの収集関数は既に標準ライブラリにString.concatWith " "として存在します。