您将如何在 SML 中手动跟踪此功能？

Question

我试图理解 SML 中函数的递归调用，其目的是在列表中找到最大的整数值。出于教育原因，此功能不好。

fun bad_max(xs: int list) = 
        if null xs (*if the list is empty, returns 0 which is bad style*)
        then 0
        else if null (tl xs)  (*if the list has only one element this is the max*)
        then hd xs 
        else if hd xs > bad_max(tl xs) (*not clear how this happens*)
        then hd xs
        else bad_max( tl xs)

我知道由于重复的递归调用，上面的函数以非常慢的方式提供了正确的结果。

我不明白最后的 else if 和最后的 else 到底是怎么发生的。

我真的很想念像 trace 这样的工具来查看函数参数在递归调用中的变化。显然，标准 ML does not 有一个工具。

我想了解调用后到底发生了什么：

bad_max([1,7,3,4])

结果为 7，正确。

尽管如此，这究竟是如何发生的？

1 > bad_max([7,3,4])
       7 > bad_max([3,4])
                3 > bad_max([4])
                3 > 4
           (*which is false*)
           (*what is the next step? Does the function come back to the int of 7?*)

       7 >      3 (*which is true!*)

                  (*or does the program go to the ELSE recursive call and restart the process such as?*)

7 > bad_max([3,4])

抱歉，如果我的疑问不清楚。很难用文字来表达。我试图使上面的标识表达我对递归调用语义的怀疑。

我真的在寻找编程语言 Racket 中存在的库跟踪之类的东西。

> (define (f x) (if (zero? x) 0 (add1 (f (sub1 x)))))
> (trace f)
> (f 10)

>(f 10)

> (f 9)

> >(f 8)

> > (f 7)

> > >(f 6)

> > > (f 5)

> > > >(f 4)

> > > > (f 3)

> > > > >(f 2)

> > > > > (f 1)

> > > >[10] (f 0)

< < < <[10] 0

< < < < < 1

< < < < <2

< < < < 3

< < < <4

< < < 5

< < <6

< < 7

< <8

< 9

<10

10

我什至尝试将 SML 代码改编为 Racket 只是以使用 Trace 库并消除我的疑虑。我的球拍技巧生锈了，但显然不可能在球拍中重现 SML 代码的相同行为。以下代码会引发错误：

#lang racket

(require racket/trace rackunit)

(define (bad_max lista)
 (cond ((empty? lista) 0)
       ((empty? (cdr lista)) car lista)
       ((> (car lista)  (bad_max  (cdr lista))) (car lista))  
       (else (bad_max (cdr lista)))))

(bad_max '(1 7 3 4))

这个疑问的有趣之处在于，列表最大值的错误解决方案比正确的解决方法更难理解。

====

更新：

感谢 Sorawee 的评论，我得以修复上面的球拍代码：

#lang racket

(require racket/trace rackunit)

(define (bad_max lista)
 (cond ((empty? lista) 0)
       ((empty? (cdr lista)) (car lista))
       ((> (car lista)  (bad_max  (cdr lista))) (car lista))  
       (else (bad_max (cdr lista)))))

(trace bad_max)
(bad_max '(1 7 3 4))

Answer 1

如果你觉得需要追踪，一次做一个“级别”并使用替换法。
（请记住，递归函数没有什么特别之处 - 它们的工作方式与非递归函数完全相同。）

bad_max [1,7,3,4]:

...
else if 1 > bad_max [7,3,4]
     then 1
     else bad_max [7,3,4]

bad_max [7,3,4]:

...
else if 7 > bad_max [3,4]
     then 7
     else bad_max [3,4]

bad_max [3,4]:

...
else if 3 > bad_max [4]
     then 3
     else bad_max [4]

现在很明显bad_max [3,4]是4了，可以回去代入：

bad_max [7,3,4]:

...
else if 7 > 4
     then 7
     else 4

bad_max [1,7,3,4]:

...
else if 1 > 7
     then 1
     else 7

附带说明一下，推理模式通常比推理谓词和选择器更容易：

fun bad_max [] = 0
  | bad_max [x] = x
  | bad_max (x::xs) = if x > bad_max xs
                      then x
                      else bad_max xs

您将如何在 SML 中手动跟踪此功能？

How would you manually trace this function in SML?

debugging

recursion

trace

sml

racket