Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » [OCAML] Minimun element in a list

Credits go to kazzmir, nonnus29, and Peter Wang for helping out!
This thread is locked; no one can reply to it. rss feed Print
[OCAML] Minimun element in a list
FMC
Member #4,431
March 2004
avatar

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?

[FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites]
Written laws are like spiders' webs, and will, like them, only entangle and hold the poor and weak, while the rich and powerful will easily break through them. -Anacharsis
Twenty years from now you will be more disappointed by the things that you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover. -Mark Twain

nonnus29
Member #2,606
August 2002
avatar

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.

kazzmir
Member #1,786
December 2001
avatar

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

1let rec least lst =
2 match lst with
3 | [] -> 0
4 | x :: [] -> x
5 | x :: xs ->
6 let v = least xs in
7 if x < v then
8 x
9 else
10 v
11;;
12 
13Printf.printf "least is %d\n" (least [1;2;3;4;5]);
14Printf.printf "least is %d\n" (least [5;4;3;2;1]);
15Printf.printf "least is %d\n" (least [5;4;1;2;3]);
16Printf.printf "least is %d\n" (least [-5;-4;-1;-2;-3]);;
17 
18let least2 lst =
19 List.fold_left
20 (fun a b ->
21 if a < b then
22 a
23 else
24 b)
25 (List.hd lst)
26 lst
27;;
28 
29Printf.printf "least is %d\n" (least2 [1;2;3;4;5]);
30Printf.printf "least is %d\n" (least2 [5;4;3;2;1]);
31Printf.printf "least is %d\n" (least2 [5;4;1;2;3]);
32Printf.printf "least is %d\n" (least2 [-5;-4;-1;-2;-3]);
33 
34$ ocaml x.ml
35least is 1
36least is 1
37least is 1
38least is -5
39least is 1
40least is 1
41least is 1
42least is -5

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

Don Freeman
Member #5,110
October 2004
avatar

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

8-)

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

--
"Everyone tells me I should forget about you, you don’t deserve me. They’re right, you don’t deserve me, but I deserve you."
"It’s so simple to be wise. Just think of something stupid to say and then don’t say it."

OnlineCop
Member #7,919
October 2006
avatar

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

FMC said:

Currently i'm trying to figure out a way to extract the smallest element from a list of integers.

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:

Don Freeman said:

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

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++ )

Peter Wang
Member #23
April 2000

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.

Edgar Reynaldo
Member #8,592
May 2007
avatar

Quote:

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.

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.

Jonatan Hedborg
Member #4,886
July 2004
avatar

Quote:

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.

That will never be a bottleneck, don't be so dramatic :D 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 8-)

-------
Sweden: Free from the shackles of Democracy since 2008-06-18!

Edgar Reynaldo
Member #8,592
May 2007
avatar

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

SiegeLord
Member #7,827
October 2006
avatar

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.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Jonatan Hedborg
Member #4,886
July 2004
avatar

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 :-X

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++ :D

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.

-------
Sweden: Free from the shackles of Democracy since 2008-06-18!

FMC
Member #4,431
March 2004
avatar

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 :P) 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 :)

[FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites]
Written laws are like spiders' webs, and will, like them, only entangle and hold the poor and weak, while the rich and powerful will easily break through them. -Anacharsis
Twenty years from now you will be more disappointed by the things that you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover. -Mark Twain

Go to: