Re: [Caml-list] Simple question

[Eric Merritt <cyberlync@yahoo.com>]

> Actually, it's O(n) because it's straightforward and
> doesn't cause
> side-effects.  The O(n^2) is when it is used n
> times.  Here's an
> implementation that works similarly:
> 
> let rec append a b = match (a,b) with
>   | [], _ -> b
>   | h::t, _ -> h :: append t b
> 
> If you keep appending one element onto the end of a
> list, you can see
> that append has to run down the entire first list
> each time to build a
> new list with your new value at the end.  If you
> append one item at
> the beginning each time, it behaves substatntially
> like :: does.
> 
> So (@) is O(n) with n being the size of the first
> argument.

This actually makes allot of sense. I am very new to
the functional world (basically Ocaml and Erlang are
my current learning projects) so many of things that
might be obvious to a more experienced functional
programmer I do not see. This is slowly changing as I
write more code, of course ;). 

In allot of ways this strugle reminds me of my initial
attempts to learn the Object Oriented Paradigm, only
this is a little more foriegn. In any case, I thank
you all for your help and I hope to be joining your
ranks as a decent functional programmer one day.


__________________________________________________
Do You Yahoo!?
Yahoo! Tax Center - online filing with TurboTax
http://taxes.yahoo.com/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners