嵌套模式匹配 - SML - 单步执行示例并且非常困惑

Question

我正在尝试了解模式匹配和递归以及程序的执行方式。

在一个简单的例子中：

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))

我可以看到 SOME y 中的 y1 基本上充当累加器，因为上面在 sum_list_num [1,2,3,4,5]; 中返回：

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 但我无法弄清楚它是如何工作的。我修改了函数以打印出每个 'match':

发生的事情

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 大小写？
我一直坐在这里拿着一叠纸和许多编辑，我很难过 'following'递归调用的叠加和评估到底发生了什么。

如有任何帮助，我们将不胜感激。整天阅读有关模式匹配的 SML 指南并没有使这一点变得更清楚！

注意：第二个例子是 Coursera class 的家庭作业问题（我使用 let 函数回答它，该函数使用累加器而不是嵌套的 case 语句来构建列表，我遇到了在谷歌搜索模式匹配 SML 时在上面，我整天都在努力思考它。

FYI gather 只是一个辅助函数，因此我可以打印出字符串列表的内容：

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

Answer 1

I can see that the y1 in SOME y is basically acting as an accumulator

Am I right to be thinking that or have I missed the mark?

是的，你是对的。

sum_list_num 函数递归调用自身，return 将累加结果传给自身。由于结果被包裹在 SOME/NONE 中，模式匹配用于解包结果并再次将其打包回 SOME。例如。 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)

继续前进，

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))

Why am I returning x' in the match case?

一个更好的问题可能是：这个函数在做什么？从那时起，该答案的一部分可能是“...和return列表的其余部分（x'）。”此代码的一部分使得我认为难以阅读的是 smatch (str, x') 在每个循环迭代中，在案例主体之前进行评估，无论是否使用其 return 值。

通过首先处理输入列表的尾部，它被向后处理（有意或无意）。

Why is everything in the list after the string I'm looking for evaluate to the NONE case?

这可能最好通过手动评估小输入的函数来显示。每次我写一个 ~> 时，我都会评估下一个术语（一个函数在它运行之前的输入，或者一个函数调用，如果它的所有输入都被评估的话。前几个术语重写是：

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"，case-of语句的第一个case匹配的是((false, NONE)) 实际上是在比较。我们继续...

  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"]

I've been sitting here with a pad of paper and many edits and I'm having a tough time 'following' what exactly is happening in how the recursive calls are being stacked up and evaluated.

除了手动评估您的函数（当您的术语重写导致大量案例时这很困难），您可以以不同的方式构建您的代码，以便在您评估列表的尾部之前更加明显实际要素。似乎也不需要嵌套模式匹配。而且既然这个函数真的只是过滤掉了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"]

顺便说一下，您的 gather 函数已经作为 String.concatWith " ".

存在于标准库中

嵌套模式匹配 - SML - 单步执行示例并且非常困惑

Nested Pattern Matching - SML - Stepping Through an Example and Very Confused

functional-programming

sml