From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA28523; Mon, 15 Apr 2002 22:08:57 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA13719 for ; Mon, 15 Apr 2002 22:08:57 +0200 (MET DST) Received: from web13005.mail.yahoo.com (web13005.mail.yahoo.com [216.136.174.15]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id g3FK8tD23276 for ; Mon, 15 Apr 2002 22:08:55 +0200 (MET DST) Message-ID: <20020415200854.17570.qmail@web13005.mail.yahoo.com> Received: from [4.18.166.227] by web13005.mail.yahoo.com via HTTP; Mon, 15 Apr 2002 13:08:54 PDT Date: Mon, 15 Apr 2002 13:08:54 -0700 (PDT) From: Eric Merritt Subject: Re: [Caml-list] Simple question To: caml-list@inria.fr In-Reply-To: <86it6wlmi8.fsf@laurelin.dementia.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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