Question About lists

[Mark Carroll]

On Mon, 30 Dec 2002, Cesar Augusto Acosta Minoli wrote:

> Hello! I'm Working with Lists in Haskell, I=B4m a Beginner in Functional
> Programming and I would like to know if there is=A0a way to write a more
> efficient function that return the length of a list, I wrote this one:
>
> long=A0=A0=A0=A0=A0=A0=A0 ::=A0 [a]->Int
> long p=A0=A0=A0=A0 =3D=A0 longitud p 0
> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 where
> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 longitud []=A0=A0=
=A0=A0=A0=A0 s=3Ds
> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 longitud (x:xs) s=
=3Dlongitud 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.,

=09long []     =3D 0
=09long (x:xs) =3D 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