Hi Cesar If you check the prelude, you will find the definition (something like): length::[a]->Int length = foldl' (\n _ -> n + 1) 0 and the definition of foldl' foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f a [] = a foldl' f a (x:xs) = (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. 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='background-color:'><DIV> <P>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:</P> <P>long :: [a]->Int<BR>long p = longitud p 0<BR> where<BR> longitud [] s=s<BR> longitud (x:xs) s=longitud 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=all><hr>Add photos to your e-mail with MSN 8. <a href="http://g.msn.com/8HMEEN/2021">Get 3 months FREE*.</a> </html> _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- 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
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
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*. <http://g.msn.com/8HMEEN/2021> _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Artie Gold -- Austin, Texas
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
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
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.
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
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 = <whatever> 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/
participants (8)
-
Alastair Reid -
Andrew J Bromage -
Artie Gold -
Cesar Augusto Acosta Minoli -
gilesb＠cpsc.ucalgary.ca -
Mark Carroll -
Shlomi Fish -
William Lee Irwin III