Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Memory leak after going from type Integer to Int (Andreas Lemke)
2. Errors and the compiler (Christopher Howard)
3. Re: Errors and the compiler (Michael Orlitzky)
4. Re: Errors and the compiler (Kim-Ee Yeoh)
5. import checking and filtering (Christopher Howard)
----------------------------------------------------------------------
Message: 1
Date: Thu, 11 Oct 2012 19:33:23 +0200
From: "Andreas Lemke" <[email protected]>
Subject: [Haskell-beginners] Memory leak after going from type Integer
to Int
To: <[email protected]>
Message-ID: <349F454BBFC645548B57B7432DB20CFC@Pablo>
Content-Type: text/plain; format=flowed; charset="iso-8859-1";
reply-type=original
Hi everyone,
I wrote a simple program that returns the n-th prime number when given n as
its command-line argument:
import System.Environment
isPrime n | n < 2 = False
| n == 2 = True
| otherwise = not $ any (`divides` n) dividerList
where a `divides` b = b `mod` a == 0
dividerList = 2:[3, 5 .. floor $ sqrt $ fromIntegral n]
primes = filter isPrime [1 ..]
main = do
[arg] <- getArgs
print $ primes !! (read arg)
I compiled it with "ghc -O2". As expected, it runs in constant space, i. e.
space complexity O(1). Then, I added the declaration: "primes :: [Int]",
expecting a performance improvement. Runtime was indeed reduced by about
50%. However, it no longer runs in constant space. Memory usage rises
significantly for arguments > 1e5.
I tried all sorts of strictness annotations, which did not help. Turning on
profiling with "ghc -O2 -prof -auto-all" made the problem disappear, so I
could not analyze the memory leak using the profiler. Only if I remove the
cases "n < 2" and "n == 2" from the definition of isPrime, does the program
run in constant space with type Int. If I replace the guards by an if
statement or pattern matching, the problem remains.
I have no idea how to continue from here. Can anyone explain why going from
type Integer to Int causes a different space complexity? How would I have to
change the program to get it to run in constant space with type Int?
I used ghc 7.4.1.
Regards,
Andreas
------------------------------
Message: 2
Date: Thu, 11 Oct 2012 12:48:56 -0800
From: Christopher Howard <[email protected]>
Subject: [Haskell-beginners] Errors and the compiler
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Point of curiosity: Does an error in a Haskell program have a negative
impact on the compilers reasoning about or optimization of the code,
even if said error is never reached in the control flow? For example,
both of the following would have the same result:
code:
--------
case mExp of
Nothing -> expr
Just x -> f x
-- or...
if isNothing mExp
then expr
else f (fromJust mExp)
--------
In my naive reasoning, I would think that in the latter case the use of
fromJust introduces, from the compilers perspective, an additional
possible outcome (an error being thrown). This presumably would
complicate the compilers reasoning about the code, unless of course the
compiler is smart enough to figure out that the error will never be reached.
--
frigidcode.com
indicium.us
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 551 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121011/76e2eb12/attachment-0001.pgp>
------------------------------
Message: 3
Date: Thu, 11 Oct 2012 19:48:09 -0400
From: Michael Orlitzky <[email protected]>
Subject: Re: [Haskell-beginners] Errors and the compiler
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On 10/11/2012 04:48 PM, Christopher Howard wrote:
> Point of curiosity: Does an error in a Haskell program have a negative
> impact on the compilers reasoning about or optimization of the code,
> even if said error is never reached in the control flow? For example,
> both of the following would have the same result:
>
> code:
> --------
> case mExp of
> Nothing -> expr
> Just x -> f x
>
> -- or...
>
> if isNothing mExp
> then expr
> else f (fromJust mExp)
> --------
>
> In my naive reasoning, I would think that in the latter case the use of
> fromJust introduces, from the compilers perspective, an additional
> possible outcome (an error being thrown). This presumably would
> complicate the compilers reasoning about the code, unless of course the
> compiler is smart enough to figure out that the error will never be reached.
Once upon a time, Ben Lippmeier showed me that,
foo | something_always_true = bar
| otherwise = error "this is impossible"
is slower than,
foo | something_always_true = bar
so I am pessimistic about your example. I would presume GHC does better
on the first one.
------------------------------
Message: 4
Date: Fri, 12 Oct 2012 09:27:32 +0700
From: Kim-Ee Yeoh <[email protected]>
Subject: Re: [Haskell-beginners] Errors and the compiler
To: Christopher Howard <[email protected]>
Cc: Haskell Beginners <[email protected]>
Message-ID:
<CAPY+ZdS4dq+PPjtHy34=m9862s6mezer6jn-+3gkh-up-hc...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
The bigger issue here is one's own reasoning about the code, never mind the
compiler's. Bob Harper writes eloquently on this topic:
http://existentialtype.wordpress.com/2011/03/15/*boolean*-blindness/
As for optimality issues, a naive compiler would wastefully examine the tag
twice in the else clause of:
if isNothing mExp
then expr
else f (fromJust mExp)
-- Kim-Ee
On Fri, Oct 12, 2012 at 3:48 AM, Christopher Howard <
[email protected]> wrote:
> Point of curiosity: Does an error in a Haskell program have a negative
> impact on the compilers reasoning about or optimization of the code,
> even if said error is never reached in the control flow? For example,
> both of the following would have the same result:
>
> code:
> --------
> case mExp of
> Nothing -> expr
> Just x -> f x
>
> -- or...
>
> if isNothing mExp
> then expr
> else f (fromJust mExp)
> --------
>
> In my naive reasoning, I would think that in the latter case the use of
> fromJust introduces, from the compilers perspective, an additional
> possible outcome (an error being thrown). This presumably would
> complicate the compilers reasoning about the code, unless of course the
> compiler is smart enough to figure out that the error will never be
> reached.
>
> --
> frigidcode.com
> indicium.us
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121012/a8f10de5/attachment-0001.htm>
------------------------------
Message: 5
Date: Thu, 11 Oct 2012 20:29:11 -0800
From: Christopher Howard <[email protected]>
Subject: [Haskell-beginners] import checking and filtering
To: Haskell Beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Maybe I'm losing it, but I seem to remember, when I first started out
with Haskell, using some program which would check the import list in
each of my source files, and then it would output a new import list that
only imported exactly those functions that my program actually used. At
the time I didn't think that was important, but now I really want it,
yet I can't remember which utility it was that did this. Does anyone
happen to know which utility it is I'm thinking of?
--
frigidcode.com
indicium.us
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 551 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20121011/b73b1f12/attachment-0001.pgp>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 52, Issue 14
*****************************************
