Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## Re: [Ocaml-lib-devel] About iterators and enums

 Re: [Ocaml-lib-devel] About iterators and enums From: Bardur Arantsson - 2004-04-30 08:21:23 ```On Fri, Apr 30, 2004 at 04:14:48PM +0800, Martin Jambon wrote: > On Thu, 29 Apr 2004, Nicolas Cannasse wrote: > [--snip--] > > > Please give us some examples. > > > > The rational of Enums is the following : > > - we have increasing numbers of containers (list, arrays, dynarrays, > > hashtbl, pmap, .... ) > > - all theses containers need to implement all the functionnal ops : map, > > iter, fold... > > - conversions between each of the containers is a O(n^2). > > Usually it is O(n) or O(n log n). I think he meant the *number* of conversion functions is O(n^2), not that their complexity is O(n^2). > > > - enums are here to provide an easy way to convert between different > > containers, and to abstract them at the same time when using functionnal > > ops. > > There is nice side effects about their lazyness : > > - you never need to allocate intermediate data structure when filtering / > > mapping > > - you can work with a large collection of elements without any problem. > > > > For example, let's take a 1 M elements list. > > Each map will duplicate it into a brand new 1 M elements list. > > With enums you can stack several maps and filters, and then at the end, when > > you iter or fold, each readed element will go through your functionnal > > stack, be mapped or filtered by it, and eventually reach the output. > > Here is a simple example: > > let l2 = List.map f1 l1 in > let l3 = List.filter f2 l2 in > let l4 = List.map f3 l3 in > ... > > You can replace it by: > > let l4 = List.fold_left (fun accu x -> > let y = f1 x in > if f2 y then f3 y :: accu > else accu) l1 in > ... > > In both cases, the memory is kept constant (2 * n) during the process but > in the second version, less memory is allocated/deallocated. > Of course List may be replaced by any other module. > > If you don't want to iterate until the end, just raise an exception: > > let fold_while f test s init = > let result = ref init in > try > fold > (fun accu x -> > if test x then f x accu > else (result := accu; > raise Exit)) > [] s > with Exit -> !result > Well, duh! "Anything written in OCaml can be replaced with other OCaml code which does the same thing! News at 11". The point is that with Enums that code is written for you and automagically works with any data structure which can be enum'd. -- Bardur Arantsson - Me? The 13th Duke of Wimbourne? In a student nurse's hall of residence at three in the morning? With my reputation? ... Bingo! The 13th Duke of Wimbourne | The Fast Show ```