Question About lists
gilesb@cpsc.ucalgary.ca
gilesb@cpsc.ucalgary.ca
Mon, 30 Dec 2002 11:43:31 -0700 (MST)
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:
> <html><div style=3D'background-color:'><DIV>
> <P>Hello! I'm Working with Lists in Haskell, I=B4m a Beginner in Function=
al Programming and I would like to know if there is a way to write a m=
ore efficient function that return the length of a list, I wrote this one:<=
/P>
> <P>long :: [a]->Int<BR=
>long p =3D longitud p 0<BR>  =
; &n=
bsp; where<BR> &=
nbsp; longitud []&nbs=
p; s=3Ds<BR> &nb=
sp; =
longitud (x:xs) s=3Dlongitud xs (s+1)</P>
> <P>but I think that it have a lineal grow O(n).</P>
> <P>thanks!</P>
> <P> </P>
> <P> </P>
> <P> </P>
> <P> <BR><BR></P></DIV></div><br clear=3Dall><hr>Add photos to your e=
-mail with MSN 8. <a href=3D"http://g.msn.com/8HMEEN/2021">Get 3 months FR=
EE*.</a> </html>
> _______________________________________________
> 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