CODEWITHSUNDEEP
listfunctionrecursionocamlminimum
deko
deko

Reputation: 495

How does this ocaml recursive function work?

I'm pretty new to ocaml and I'm having a hard time with this func

I know what it does but not HOW! With a given list, it returns the minimum value of the list and the rest of the list as a pair.

sepmin [2;1;3;4] == (1,[2;3;4])

val sepmin : 'a list -> 'a * 'a list

# let rec sepmin = function
[h] -> h, []
|h::t -> let h1, t1 = sepmin t in
    min h h1, (max h h1)::t1;;

Could you guys help me out with the recursive part t.t

Upvotes: 1

Views: 193

Answers (2)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66808

A good way to think about recursion is to take it in two pieces. First, what does the function do when the input is trivial? Second (this is the tricky part), assuming the function works for small inputs, how does it transform a bigger intput into a smaller one and use the answer for the smaller case to calculate the correct result for the bigger case.

The trivial case for this function is a list of one element. The answer is obvious in that case.

For a longer list, you can use your recursive power to get the correct answer for the tail of the list (which is a shorter list, hence the recursion will work by assumption). Once you know the answer for the tail of the list, you can construct the correct answer for the full list: the max of the head of the list and the answer for the tail is the overall maximum. You need to add the smaller of these two values back to the list.

Upvotes: 0

bipll
bipll

Reputation: 11940

First, it is applied to the list's tail recursively. Say, it returns h1 and t1 that are the minimum of the tail and all the other elements of the tail. Next, this element, h, is compared against h1. If it is less than h1, then the pair (h, h1::t1) returned; otherwise the pair (h1, h::t1) is returned. Since the function is called recursively, then probably one of these pairs is returned to the previous recursion point (and its first element is again compared against that point's list head). As far as I can see, the function does not care much about the original order of the elements, i.e. for the list [1; 4; 2; 5; 6] it should return (1, [2; 4; 5; 6]), 2 and 4 are reordered in the result.

Upvotes: 1

Related Questions