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