From c_minoli@hotmail.com Mon Dec 30 12:38:15 2002 From: Cesar Augusto Acosta Minoli To: haskell@haskell.org Subject: Question About lists Date: Mon, 30 Dec 2002 17:38:13 +0000 Message-ID: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============0816823130508896658==" --===============0816823130508896658== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit --===============0816823130508896658== Content-Type: text/html Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="attachment.html" MIME-Version: 1.0 PGh0bWw+PGRpdiBzdHlsZT0nYmFja2dyb3VuZC1jb2xvcjonPjxESVY+CjxQPkhlbGxvISBJJ20g V29ya2luZyB3aXRoIExpc3RzIGluIEhhc2tlbGwsIEnvv71tIGEgQmVnaW5uZXIgaW4gRnVuY3Rp b25hbCBQcm9ncmFtbWluZyBhbmQgSSB3b3VsZCBsaWtlIHRvIGtub3cgaWYgdGhlcmUgaXMmbmJz cDthIHdheSB0byB3cml0ZSBhIG1vcmUgZWZmaWNpZW50IGZ1bmN0aW9uIHRoYXQgcmV0dXJuIHRo ZSBsZW5ndGggb2YgYSBsaXN0LCBJIHdyb3RlIHRoaXMgb25lOjwvUD4KPFA+bG9uZyZuYnNwOyZu YnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyA6OiZuYnNwOyBbYV0tJmd0O0ludDxC Uj5sb25nIHAmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgPSZuYnNwOyBsb25naXR1ZCBwIDA8QlI+ Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5i c3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IHdoZXJl PEJSPiZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNw OyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyBs b25naXR1ZCBbXSZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyBzPXM8QlI+Jm5i c3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7 Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IGxvbmdpdHVk ICh4OnhzKSBzPWxvbmdpdHVkIHhzIChzKzEpPC9QPgo8UD5idXQgSSB0aGluayB0aGF0IGl0IGhh dmUgYSBsaW5lYWwgZ3JvdyBPKG4pLjwvUD4KPFA+dGhhbmtzITwvUD4KPFA+Jm5ic3A7PC9QPgo8 UD4mbmJzcDs8L1A+CjxQPiZuYnNwOzwvUD4KPFA+Jm5ic3A7PEJSPjxCUj48L1A+PC9ESVY+PC9k aXY+PGJyIGNsZWFyPWFsbD48aHI+QWRkIHBob3RvcyB0byB5b3VyIGUtbWFpbCB3aXRoIE1TTiA4 LiAgPGEgaHJlZj0iaHR0cDovL2cubXNuLmNvbS84SE1FRU4vMjAyMSI+R2V0IDMgbW9udGhzIEZS RUUqLjwvYT4gPC9odG1sPgo= --===============0816823130508896658==-- From gilesb@cpsc.ucalgary.ca Mon Dec 30 13:43:42 2002 From: gilesb@cpsc.ucalgary.ca To: haskell@haskell.org Subject: Re: Question About lists Date: Mon, 30 Dec 2002 11:43:31 -0700 Message-ID: In-Reply-To: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============2888881341190964181==" --===============2888881341190964181== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Hi Cesar If you check the prelude, you will find the definition (something like): length::[a]->Int length =3D foldl' (\n _ -> n + 1) 0 and the definition of foldl' foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] =3D a foldl' f a (x:xs) =3D (foldl' f $! f a x) xs Which also gives a linear complexity (O(n)) to length. Unless your representation of lists stores the length, you will pretty much always need linear time to find out the length as you have to count how many items there are. =20 Alternatively, if getting the length is something you need to do a lot, consider creating your own datatype and corresponding class for inserts etc. that keeps the length on hand. This could allow O(1) length queries. On 30 Dec, Cesar Augusto Acosta Minoli wrote: >
>

Hello! I'm Working with Lists in Haskell, I=C2=B4m a Beginner in Functio= nal Programming and I would like to know if there is a way to write a mo= re efficient function that return the length of a list, I wrote this one:

>

long        ::  [a]->Int
l= ong p     =3D  longitud p 0
   &nb= sp;            &n= bsp;  where
         &nb= sp;         longitud []  &n= bsp;    s=3Ds
       &nb= sp;           longitud (x:x= s) s=3Dlongitud xs (s+1)

>

but I think that it have a lineal grow O(n).

>

thanks!

>

 

>

 

>

 

>

 


Add photos to your e-m= ail with MSN 8. Get 3 months FREE*.= > _______________________________________________ > Haskell mailing list > Haskell@haskell.org > http://www.haskell.org/mailman/listinfo/haskell --=20 Brett G. Giles Grad Student, University of Calgary Formal Methods, Category Theory, Semantics of Programming http://www.cpsc.ucalgary.ca/~gilesb mailto:gilesb@cpsc.ucalgary.ca --===============2888881341190964181==-- From mark@chaos.x-philes.com Mon Dec 30 13:59:10 2002 From: Mark Carroll To: haskell@haskell.org Subject: Re: Question About lists Date: Mon, 30 Dec 2002 13:59:08 -0500 Message-ID: In-Reply-To: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============9130496761316209782==" --===============9130496761316209782== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit On Mon, 30 Dec 2002, Cesar Augusto Acosta Minoli wrote: > Hello! I'm Working with Lists in Haskell, I´m a Beginner in Functional > Programming and I would like to know if there is a way to write a more > efficient function that return the length of a list, I wrote this one: > > long        ::  [a]->Int > long p     =  longitud p 0 >                    where >                    longitud []       s=s >                    longitud (x:xs) s=longitud xs (s+1) > > but I think that it have a lineal grow O(n). Yes, it's O(n), but you can't do any better for calculating the length of a list. Your second parameter seems to be an accumulator which is the sort of thing you'd make explicit in an imperative approach but can often be eliminated in functional code - e.g., long [] = 0 long (x:xs) = 1 + long xs A decent optimizing compiler will probably turn that code into something that uses an accumulator. This code probably isn't any more efficient than yours, it's just shorter. -- Mark --===============9130496761316209782==-- From agold@bga.com Mon Dec 30 15:09:13 2002 From: Artie Gold To: haskell@haskell.org Subject: Re: Question About lists Date: Mon, 30 Dec 2002 13:47:37 -0600 Message-ID: <3E10A2D9.20101@bga.com> In-Reply-To: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============2044349599683893845==" --===============2044349599683893845== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit Cesar Augusto Acosta Minoli wrote: > Hello! I'm Working with Lists in Haskell, I´m a Beginner in Functional > Programming and I would like to know if there is a way to write a more > efficient function that return the length of a list, I wrote this one: > > long :: [a]->Int > long p = longitud p 0 > where > longitud [] s=s > longitud (x:xs) s=longitud xs (s+1) > > but I think that it have a lineal grow O(n). Sure. The only way to count the elements in a list is to, well, count the elements; it's an inherently linear operation. One suggestion, though is that you're working too hard; there's really no reason to define a locally defined function. The much simpler: long [] = 0 long (x:xs) = 1 + long xs will do quite nicely. HTH, --ag > > thanks! > > > > > > > > > > > ------------------------------------------------------------------------ > Add photos to your e-mail with MSN 8. Get 3 months FREE*. > > _______________________________________________ Haskell mailing list > Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell -- Artie Gold -- Austin, Texas --===============2044349599683893845==-- From wli@holomorphy.com Mon Dec 30 15:19:00 2002 From: William Lee Irwin III To: haskell@haskell.org Subject: Re: Question About lists Date: Mon, 30 Dec 2002 12:17:35 -0800 Message-ID: <20021230201735.GO29422@holomorphy.com> In-Reply-To: <3E10A2D9.20101@bga.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============4857333086268942131==" --===============4857333086268942131== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit On Mon, Dec 30, 2002 at 01:47:37PM -0600, Artie Gold wrote: > One suggestion, though is that you're working too hard; there's really > no reason to define a locally defined function. The much simpler: > long [] = 0 > long (x:xs) = 1 + long xs > will do quite nicely. > HTH, > --ag There is already a length function in List and/or the Prelude. Bill --===============4857333086268942131==-- From ajb@spamcop.net Tue Dec 31 21:26:46 2002 From: Andrew J Bromage To: haskell@haskell.org Subject: Re: Question About lists Date: Wed, 01 Jan 2003 13:26:40 +1100 Message-ID: <20030101022640.GB5436@smtp.alicorna.com> In-Reply-To: <3E10A2D9.20101@bga.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============5069920734633676529==" --===============5069920734633676529== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit G'day all. On Mon, Dec 30, 2002 at 01:47:37PM -0600, Artie Gold wrote: > One suggestion, though is that you're working too hard; there's really > no reason to define a locally defined function. The much simpler: > > long [] = 0 > long (x:xs) = 1 + long xs > > will do quite nicely. It has quite different performance characteristics, though. In particular, this uses O(n) stack space whereas the accumulator one uses O(1) stack space. Cheers, Andrew Bromage --===============5069920734633676529==-- From shlomif@vipe.technion.ac.il Wed Jan 1 05:17:14 2003 From: Shlomi Fish To: haskell@haskell.org Subject: Re: Question About lists Date: Wed, 01 Jan 2003 12:17:10 +0200 Message-ID: In-Reply-To: <20030101022640.GB5436@smtp.alicorna.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============7432030251261528099==" --===============7432030251261528099== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit On Wed, 1 Jan 2003, Andrew J Bromage wrote: > G'day all. > > On Mon, Dec 30, 2002 at 01:47:37PM -0600, Artie Gold wrote: > > > One suggestion, though is that you're working too hard; there's really > > no reason to define a locally defined function. The much simpler: > > > > long [] = 0 > > long (x:xs) = 1 + long xs > > > > will do quite nicely. > > It has quite different performance characteristics, though. In > particular, this uses O(n) stack space whereas the accumulator one > uses O(1) stack space. > This is assuming Haskell is properly tail-recursive. However, as far as I was told due to the lazy evaluation that is not the case for such functions. Regards, Shlomi Fish > Cheers, > Andrew Bromage > _______________________________________________ > Haskell mailing list > Haskell@haskell.org > http://www.haskell.org/mailman/listinfo/haskell > ---------------------------------------------------------------------- Shlomi Fish shlomif@vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ He who re-invents the wheel, understands much better how a wheel works. --===============7432030251261528099==-- From ajb@spamcop.net Wed Jan 1 19:57:48 2003 From: Andrew J Bromage To: haskell@haskell.org Subject: Re: Question About lists Date: Thu, 02 Jan 2003 11:57:45 +1100 Message-ID: <20030102005745.GA13871@smtp.alicorna.com> In-Reply-To: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============5317037333895993805==" --===============5317037333895993805== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit G'day all. On Wed, 1 Jan 2003, Andrew J Bromage wrote: > > It has quite different performance characteristics, though. In > > particular, this uses O(n) stack space whereas the accumulator one > > uses O(1) stack space. On Wed, Jan 01, 2003 at 12:17:10PM +0200, Shlomi Fish wrote: > This is assuming Haskell is properly tail-recursive. However, as far as I > was told due to the lazy evaluation that is not the case for such > functions. There are two issues here: 1. Haskell 98 does not explicitly mandate tail recursion optimisation. (In particular, Hugs doesn't support it fully, as we have seen recently.) 2. Due to lazy evaluation, your accumulator may end up as a "thunk" and thus require stack/heap space to evaluate when you eventually get to the end. There's not a lot you can do about the first issue. The next version of Haskell should make tail recursion optimisation a language requirement, IMO. As to the second point, there are several possible solutions. Strictness analysis can help, but relying on this is a bad idea. Consider this code: rec1 [] acc = acc rec1 (x:xs) acc = rec1 xs (x `op` acc) If `op` is known to be strict in both its arguments, any decent strictness analyser will be able to strictly evaluate the accumulator here. On the other hand, modifying it slightly: rec2 [] acc = acc rec2 (x:xs) acc | sanityCheck x = rec2 xs (x `op` acc) | otherwise = error "sanity check failed" Now the strictness analyser will not be able to evaluate the accumulator eagerly, because in general it would be incorrect to do so. Another option is to use seq, ($!), foldl' or some other method to guarantee evaluation order. Cheers, Andrew Bromage --===============5317037333895993805==-- From alastair@reid-consulting-uk.ltd.uk Thu Jan 2 03:39:19 2003 From: Alastair Reid To: haskell@haskell.org Subject: Re: Question About lists Date: Thu, 02 Jan 2003 08:39:18 +0000 Message-ID: In-Reply-To: <20030102005745.GA13871@smtp.alicorna.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============2810837951997274632==" --===============2810837951997274632== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit > 1. Haskell 98 does not explicitly mandate tail recursion optimisation. However, in practice Haskell compilers must provide this since it is impossible to write a loop without using recursion and if your loops don't use constant stack space, you're not going to run for very long. > (In particular, Hugs doesn't support it fully, as we have seen recently.) Please note that this is NOT TRUE! Hugs provides tail recursion just as fully as GHC. What Hugs does not do is garbage collect unreachable CAFs. This affects top level definitions of the form: foo = which is the form of all the examples recently discussed. -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/ --===============2810837951997274632==-- From ajb@spamcop.net Thu Jan 2 18:13:17 2003 From: Andrew J Bromage To: haskell@haskell.org Subject: Re: Question About lists Date: Fri, 03 Jan 2003 10:13:15 +1100 Message-ID: <20030102231315.GB24187@smtp.alicorna.com> In-Reply-To: MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============5867479643493136060==" --===============5867479643493136060== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit G'day all. On Thu, Jan 02, 2003 at 08:39:18AM +0000, Alastair Reid wrote: > Please note that this is NOT TRUE! Whoops, you're right. Sorry, my mistake. Cheers, Andrew Bromage --===============5867479643493136060==--