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

Credits go to kazzmir, nonnus29, and Peter Wang for helping out!
 [OCAML] Minimun element in a list
 FMC Member #4,431 March 2004 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. -AnacharsisTwenty 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 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

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

 1 let 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 13 Printf.printf "least is %d\n" (least [1;2;3;4;5]); 14 Printf.printf "least is %d\n" (least [5;4;3;2;1]); 15 Printf.printf "least is %d\n" (least [5;4;1;2;3]); 16 Printf.printf "least is %d\n" (least [-5;-4;-1;-2;-3]);; 17 18 let 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 29 Printf.printf "least is %d\n" (least2 [1;2;3;4;5]); 30 Printf.printf "least is %d\n" (least2 [5;4;3;2;1]); 31 Printf.printf "least is %d\n" (least2 [5;4;1;2;3]); 32 Printf.printf "least is %d\n" (least2 [-5;-4;-1;-2;-3]); 33 34 \$ ocaml x.ml 35 least is 1 36 least is 1 37 least is 1 38 least is -5 39 least is 1 40 least is 1 41 least is 1 42 least 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 I don't know if this helps: ```std::vector 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: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 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 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. Elizabeth Warren for President 2020! | Modern Allegro 4 and 5 binaries | Allegro 5 compile guideKing Piccolo will make it so
 Jonatan Hedborg Member #4,886 July 2004 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 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 -------Sweden: Free from the shackles of Democracy since 2008-06-18!
 Edgar Reynaldo Member #8,592 May 2007 He is right about it though, it calls size() on every iteration. No need to call it repeatedly if it doesn't change. Elizabeth Warren for President 2020! | Modern Allegro 4 and 5 binaries | Allegro 5 compile guideKing Piccolo will make it so
 SiegeLord Member #7,827 October 2006 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 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. -------Sweden: Free from the shackles of Democracy since 2008-06-18!
 FMC Member #4,431 March 2004 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 [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. -AnacharsisTwenty 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: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads