Simple Function Explanation

let rec func = (fun x -> match x with
| [] -> []
| hd::tl -> func tl@[hd]);;

This function reverses a list. My question is, if the last expression becomes the return value, why isn’t the result [ ]? When list x is exhausted, doesn’t x now match with [] and return []? Thank you!

Perhaps you meant to write (func tl)@[hd] . In which case, except for func [], there will always be stuff that happens after a recursive invocation of func returns, yes?

yes, I meant (func tl)@[hd]

So,e…g, func [a::b::[]] ->
(func [b::[]]) @ [a] ->
((func []) @ [b]) @ [a] ->
([] @ [b]) @ [a] ->
etc etc, yes?
[hope I got the parens right]

OH right, I forgot that it’s prepended to the rest, not returned. Thanks!

well, it returns [ ] for when the argument is [ ], but doesn’t overall return [ ] for the list we originally called the function on

No worries, starting out, it’s tough to understand FP. I don’t know if you’re interested in FP more generally, but if you are, here are some books that might help … (ahem) “indoctrinate you into the FP nature” (ha!)

  1. Functional Programming by Peter Henderson. An oldie, don’t try to buy it – it’ll cost a bomb. But your library might have it.
  2. The Little Schemer by Felleisen and Friedman (also The Little MLer).

I read and implemented the Henderson book cover-to-cover in … (uh) … 1986. It was revelatory. And Matthias (Felleisen), well, he’s an amazing teacher, and has taught generations of teachers how to teach FP, as well as personally generating generations of excellent students.

There’s a style, an ethos to FP that is independent of language, and can be practiced in an FP language and to some extent even in C/C++. That style, is the “FP nature”, and I think it’s really worth understanding well. Again, independently of the particular language, which is why only one of the books above is about ML, and the first book is about … well, it’s about some notional FP language that might be related to Scheme, but really isn’t.

1 Like

aren’t (func tl)@[hd] and func tl@[hd] equivalent? I thought function application had higher precedence than any operator.

1 Like

Yes indeed. I meant only that, by not making the parentheses explicit, it was possible to mistake func tl@[hd] for a tail-call (viz. func (tl@[hd])) and hence not realizing that upon return from func there was still code to execute (viz. (*)@[hd]).

That’s all.

1 Like

Of course refman has the answer, but it would be instructive to have a contextual feedback about operators precedence (as for types with ocp-index or merlin). When learning,and also when doubting!

I wonder how this could be simply achieved, perhaps by tweaking merlin? (as it continuously compiles, it knows operators precedence).

btw, what is also interesting with that simple function is that both functions compile:

(func tl) @ [hd]    (* returns reversed list *)
 func (tl @ [hd])   (*never ends *)

Putting parens around the list stuff makes visible that function nbr 2 may turn around endlessly because func is applied to a list of a same length, so case [] is never reached (not decreasing).

In addition, if you perform a simple unit test, you will see the function nbr 2 hasn’t the expected result. It seems a minimum test, complementary to type checking.

1 Like

PS: sure. In case that interests you: have you measured the time func takes to compute Vs. List.rev?

let l0 = List.init 100_000 (fun x -> x) 
List.rev l0;;  (* returns instantly in Toplevel *)
func l0;;      (* this one did not complete while I was writing this message... *) 

Moreover, append is not tail-recursive, which is risky:

refman List:
val append : 'a list → 'a list → 'a list
Concatenate two lists. Same as the infix operator @. Not tail-recursive (length of the first argument).


Btw, it was a real question!
Does anybody knows the simplest way to tweak merlin to make it display operators’ precedence locally?

I don’t know if this is exactly what you are asking for, but I sometimes use :MerlinTypeOf and :MerlinGrowEnclosing (these are the vim names, but the emacs names should be similar). With these I can select an expression, show its type, and then enlarge the selection – the enlargement will respect operator precedence.