[Haskell-cafe] Re: appending an element to a list
Tillmann Rendel [EMAIL PROTECTED] writes:
Hi! (Cool, another guy from DAIMI on haskell-cafe!)
Another (n - 1) reduction steps for the second ++ to go away.
last (o ++ l)
A) ~ last ('o' : ++ l))
L) ~ last ( ++ l)
A) ~ last (l)
L) ~ 'l'
And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
steps. Counting together, we had to use
n + (n - 1) + (n - 2) + ... = n!
reduction steps to get rid of the n calls to ++, which lies in O(n^2).
Thats what we expected of course, since we know that each of the ++
would need O(n) steps.
I really liked the excellent and very clear analysis! But the last
formula should be:
n + (n - 1) + (n - 2) + ... = n * (n+1) / 2
which is still of order n^2.
--
Martin Geisler
VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
pgpxgbfpNjJtq.pgp
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Write Haskell as fast as C.
Andrew Coppin [EMAIL PROTECTED] writes: Look closer: it's hardER to read. mean xs = sum xs / fromIntegral (length xs) mean = go 0 0 n where go s l x | x m = s / fromIntegra l | otherwise = go (s+x) (l+1) (x+1 One version makes it instantly clear, at a glance, what is happening. The other requires you to mentally walk round a look, imperative style, to figure out what's happening. It's not a *big* deal, but it's unfortunate. I am new to Haskell and when I first saw the two versions side by side I too was disappointed with the second version. But after reading the great blog post by Don, I realized that the whole problem comes from the fact that lists in Haskell are not like arrays or vectors in other languages: you don't know how long they are before you have found the end. In other words: they behave like a linked lists -- lists that are generated lazily on demand. Because they are generated on demand you *cannot* really know the length beforehand, and thus you *must* traverse the list to its end to count the length. When the list is too big to fit in memory then it's clear that the code *must* let go of the beginning to allow the garbage collector to do its job. You wouldn't be able to work with a 7.5 GiB linked list otherwise. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. pgpgElb902o1M.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: More accessible papers
Peter Verswyvelen [EMAIL PROTECTED] writes: Jeremy Shaw wrote: I would be especially neat if there was some way to embed the .tex source in the .pdf, [...] Yes, but why don't researchers just publish their TEX file? You can regard that as the source code for generating PDF/PS whatever no? I believe it is normal that the publisher requires you to give away your copyright for them to publish your article. You then no longer own the .pdf or the .tex file. For example, the Springer copyright form[1] for their Lecture Notes in Computer Science says: [...] The copyright transfer covers the sole right to print, publish, distribute and sell throughout the world the said Contribution and parts thereof, including all revisions or versions and future editions thereof and in any medium, such as in its electronic form (offline, online), [...] They do allow you to keep a copy of the .pdf file on your own website for archiving purposes, but republishing the article with a single column doesn't seem to be allowed. [1]: The copyright form can be downloaded here: http://www.springer.com/east/home/computer/lncs?SGWID=5-164-7-72376-0 -- Martin Geisler Do your secure multi-party computations (SMPC) with VIFF, the Virtual Ideal Functionality Framework. Download at http://viff.dk/ pgppdKzAaheD7.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
