I am trying to understand the recursive calls of a function in SML which purpose is to find the highest integer value in a list. This function is bad for educational reasons.
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)
I know the function above provides the correct result in a really slow manner due to the duplicate recursive calls.
What I do not understand is how exactly the last else if and the final else happen.
I really miss a tool like trace in order to see function arguments changing in recursive calls. Apparently, Standard ML does not have a tool for that.
I would like to understand what exactly happens after the call on:
bad_max([1,7,3,4])
The result is 7 which is correct.
Nonetheless, how exactly does that happen?
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])
Sorry if my doubt is not clear. It is hard to express it with text. I tried to make the identation above to be expressive about my doubts on the semantics of the recursive calls.
I was really looking for something like the library trace that exists in the programming language 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
I even tried to adapt the SML code to Racket just to use the Trace library and clear out my doubt. My racket skills are rusty but, apparently, is not possible to reproduce the same behavior of the SML code in Racket. The following code throws an error:
#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))
The funny thing about this doubt is the fact that the bad solution on the maximum value of a list is harder for me to understand than the correct way of doing it.
====
Update:
Thanks to Sorawee comment I was able to fix the racket code above:
#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))
If you feel the need to trace, do one "level" at a time and use the substitution method.
(And remember that there is nothing special about recursive functions - they work exactly like non-recursive functions.)
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]
Now it's clear that bad_max [3,4] is 4, so you can go back and substitute:
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
On a side note, it is usually easier to reason about patterns than about predicates and selectors:
fun bad_max [] = 0
| bad_max [x] = x
| bad_max (x::xs) = if x > bad_max xs
then x
else bad_max xs