I've recently started studying this language for a university course; after many years of C\C++ coding i'm having a hard time getting used to this new way of doing things.

Currently i'm trying to figure out a way to extract the smallest element from a list of integers, but have no idea where to start.
Any help?

Think about what the recursive function in C/C++ would be:

int least(int* mylist) {
  if(!mylist) return 0;
  int a = mylist[0];
  //this will segfault, but it's just for demonstration purposes.  You get the idea.
  int b = least(mylist++);
  if(a < b) return a;
  else return b;
}

Then do it in Ocaml:

let rec least mylist = function
  | [] -> 0
  | a :: tail ->
    let b = least(tail) in
      if(a < b) a
      else b

I have no idea if that will compile or not.

Edit; Sorry, that doesn't work because for positive integers it will always return zero, oops.

Here are two ways, one using direct recursion and another that uses fold_left.

The first one doesn't use tail-recursion so it wastes stack space. fold_left will use tail-recursion so its a little better.

I don't know if this helps:

std::vector<int> numList;
// Insert numbers into numList
unsigned int min, max;
min = max = 0;
for ( unsigned int num = 0; num <= numList.size(); num++ )
{
  if ( numList[num] < min )
    min = numList[num];
  if ( numList[num] > max )
    max = numList[num];
}
// Now min is the lowest number
// and max is the greatest number

Also, why is the code highlighter retared? Shouldn't the > be red as well???? It is in the for (...) loop, but not for std::vector<int>:o

FMC: Your question can be answered in two ways, depending on what you want.

If you are given an unsorted list (this is assumed), you are either looking to sort this list, and then return the first element of the sorted list (which would be the smallest element). Or, you assume that the "smallest" number in an unsorted list is a VERY large number (the biggest that you can use, like 0xFFFFFFFF). Then for each integer in the array, you test to see if the next number is smaller than that big number. If it is, you set the smallest number to THAT number, and go to the next element.

The reason you start with the LARGEST number you can find, is that if you start with 0, but the smallest number in the array is actually 5 or something LARGER than 0, you'll get invalid results. However, if you start with 999, and the smallest is 5, 5 < 999, and therefore, you smallest number will correctly be "5".

EDIT:

Oh, and you NEVER want to do this (test numList.size() within the for..loop expression). If numList never changes, you're going to be re-calling size() for no reason, making this VERY slow. Move it out of the loop to speed it up The only time you WOULD do this is if the size of numList changes within this for..loop.

   int numListSize = numList.size();
   for ( unsigned int num = 0; num <= numListSize; num++ )

The way to think about any recursive problem is to consider the base case, and the recursive case.

1. What is the minimum element of an empty list? Answer: doesn't apply. Throw an exception or let the compiler throw one for you.

2. What is the minimum element of a single element list? Trivial. This is the base case.

3. What is the minimum element of a list with the first element H and the rest of the list T? Answer: the smaller of H and minimum(T). This is the recursive case.

Then you just translate that directly to code. [This gives you the direct recursion solution. The "accumulator recursion" solution is analogous to what you'd write in C, and is probably more efficient. The thinking is not much different.] Pretty soon it becomes second nature.

Just assign the starting value the value of the first element. There's no need to assign it to the largest possible number.

Besides, I don't think he needed help with the logic of finding/sorting a list of numbers, just how to do it in OCAML.

That will never be a bottleneck, don't be so dramatic The number of elements in an STL container is most probably (and absolutely in the case of a vector) stored. It probably looks something like:

int size() {
  return size;
}

I have nothing to add on the actual topic. Sorry

He is right about it though, it calls size() on every iteration. No need to call it repeatedly if it doesn't change.

Not necessarily. The size() function is defined in a header, and thus is liable to be inlined. I don't think there is any performance difference. I take my size out first, but only for readability's sake.

But during the entire life of an application, that optimization would probably not save more time than it took to write that extra line of code

And besides, if you alter your app so that it needs to change the size inside the loop, you have to remember that you did that. Sure, it's not a big deal, but I like to keep it simple whenever possible.

Also, I'm a fan of clean, nice (and still fast enough) one-liners. Which is also why I try to stay away from horrible languages like C/C++

EDIT: Anyway, I don't want to start a flame war. I just reacted to the wording "NEVER want to do this" and "VERY slow" which is just silly.

kazzmir: thanks!
I understood your code (thanks also to Peter's post) on the direct recursion, but i have a little question on the fold_left approach: AFAIK (which isn't alot in ocaml ) fold_left takes three arguments, the operation to do with the elements, a value to return in case the list is empty and the list to apply it to.
But you pass as second argument (List.hd lst) which should mean "the first element in the list", but how is this possible if the list is empty?

Peter: thanks for the insight.

nonnus29: nearly there, thanks.

The others: thanks but i had problems with the (recursive) implementation in OCaml, not the C way.

P.S. Yay for smileys