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. Re: MonadPlus (Johann Bach)
2. Print Unicode in String (dan portin)
3. Re: Print Unicode in String (Daniel Fischer)
4. Why is this function that slow? (Andreas Flierl)
5. Re: Why is this function that slow? (Daniel Fischer)
6. Re: Why is this function that slow? (Bryce Verdier)
7. Re: Why is this function that slow? (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Wed, 28 Jul 2010 12:56:58 -0700
From: Johann Bach <[email protected]>
Subject: Re: [Haskell-beginners] MonadPlus
To: Brent Yorgey <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
On Wed, Jul 28, 2010 at 3:51 AM, Brent Yorgey <[email protected]> wrote:
> On Wed, Jul 28, 2010 at 03:03:01AM -0700, Johann Bach wrote:
>> I'm looking at Douglas Auclair's MonadPlus article, here
>> http://www.haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf
>>
>> So consider an example like
>>
>> t2 = do
>> x <- [1,2,3]
>> y <- [1,2]
>> guard $ x+y > 2
>> return (x,y)
>>
>> This uses the list instance of MonadPlus.
>>
>> Now, Douglas is talking about his own code, not the above example, but
>> his own code is similar. And he says "the entire computation is
>> chained by mplus". I'm confused because I thought it was chained by
>> >>=. In fact, I can't see where the above code makes use of mplus. The
>> definition of "guard" uses mzero.
>
> You are correct. That sentence is an error. Indeed, it ought to say
> "since the entire computation is chained with (>>=), a failure of one
> test voids the entire branch". This is because of the required law
Brent -- also, in his example (similar to my example above) it looks
like the only benefit of the list instance of MonadPlus in this case
is to use the pre-existing definition of guard. Is that true? His
example is indeed more complex... it's in TMR issue 11.
-Johann
------------------------------
Message: 2
Date: Wed, 28 Jul 2010 14:43:01 -0700
From: dan portin <[email protected]>
Subject: [Haskell-beginners] Print Unicode in String
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Hi,
Perhaps I'm missing something, but I haven't found an answer to this
question in the textbook I have been using (Thompson) or through
Google/Hoogle: can a String include Unicode characters? For instance, if I
am defining an instance of Show Expr, where Expr models simple arithmetic
expressions (or Show Seq, where Seq models a sequent calculus, and so
forth), could I define a function *show Pi* = U+03C0 or *show Delta* =
U+0395? Perhaps the answer is obvious, but I haven't been able to find it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100728/4a63ef80/attachment-0001.html
------------------------------
Message: 3
Date: Thu, 29 Jul 2010 00:11:30 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Print Unicode in String
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Wednesday 28 July 2010 23:43:01, dan portin wrote:
> Hi,
>
> Perhaps I'm missing something, but I haven't found an answer to this
> question in the textbook I have been using (Thompson) or through
> Google/Hoogle: can a String include Unicode characters?
Yes. A Char is a unicode code-point.
> For instance, if
> I am defining an instance of Show Expr, where Expr models simple
> arithmetic expressions (or Show Seq, where Seq models a sequent
Don't call it Seq, that's already used for sequences in Data.Sequence.
> calculus, and so forth), could I define a function *show Pi* = U+03C0 or
You need a different syntax, show Pi = "\x03C0"
> *show Delta* = U+0395?
show Delta = "\x0394"
> Perhaps the answer is obvious, but I haven't been able to find it.
However, if your locale is not utf-8 or you're using a pre-6.12 GHC, output
might be garbled, then you'd have to use System.IO.UTF8.putStrLn to print.
------------------------------
Message: 4
Date: Thu, 29 Jul 2010 00:29:56 +0200
From: Andreas Flierl <[email protected]>
Subject: [Haskell-beginners] Why is this function that slow?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hello everyone,
I am a newbie to Haskell coming from a Java/Scala/Ruby background. As first few
exercises, I was trying to translate my Scala solutions for some Project Euler
[1] problems to Haskell. The function that solves problem 4 turns out to be
quite slow (6s in Haskell as opposed to 400ms in Scala) and I cannot understand
why. Here's the function:
euler4 = solve 100 999
where solve min max = maximum palindromes
where palindromes = [n | a <- range, b <- range, let n = a * b,
isPalindrome n]
range = [max, max - 1 .. min]
isPalindrome n = (n :: Int) == (read $ reverse $ show n)
Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems rather
high to me. My guess would be that this is somehow related to lazy evaluation
but all in all, I've got no real clue and would be thankful for any advice.
Thank you
Andreas
[1] http://www.projecteuler.net
------------------------------
Message: 5
Date: Thu, 29 Jul 2010 01:33:34 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Why is this function that slow?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Thursday 29 July 2010 00:29:56, Andreas Flierl wrote:
> Hello everyone,
>
> I am a newbie to Haskell coming from a Java/Scala/Ruby background. As
> first few exercises, I was trying to translate my Scala solutions for
> some Project Euler [1] problems to Haskell. The function that solves
> problem 4 turns out to be quite slow (6s in Haskell as opposed to 400ms
> in Scala) and I cannot understand why. Here's the function:
>
> euler4 = solve 100 999
> where solve min max = maximum palindromes
> where palindromes = [n | a <- range, b <- range, let n = a
> * b, isPalindrome n] range = [max, max - 1 .. min]
> isPalindrome n = (n :: Int) == (read $ reverse $ show n)
Try
isPalindrome n = let s = show n in s == reverse s
`read' is slow, though I didn't expect it to be that slow, to be honest.
The above change brought time down from ~5.1 secs to 0.22 secs here.
You can make it still faster if you make an arithmetic palindrome check
instead of converting to String (0.1 secs).
With algorithmic improvements more can be gained.
>
> Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems
> rather high to me. My guess would be that this is somehow related to
> lazy evaluation but all in all, I've got no real clue and would be
> thankful for any advice.
The problem (part of it at least) is that the Read instances for number
types has been written more with elegance in mind than efficiency,
apparently.
Thus when you want to read an Int, first a generic number, possibly
including a fractional part and an exponent or represented in base 8 or 16
is tried to be read.
That number is read as an Integer or a Rational (depending on the presence
of a fractional part and an exponent [and its value]).
If the read produced an Integer, that is then converted to the appropriate
number type [Int in this case].
That gives very elegant, but not very fast code.
>
> Thank you
> Andreas
>
Cheers,
Daniel
------------------------------
Message: 6
Date: Wed, 28 Jul 2010 17:02:04 -0700
From: Bryce Verdier <[email protected]>
Subject: Re: [Haskell-beginners] Why is this function that slow?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
<Shameful
plug>http://scrollingtext.org/project-euler-problem-4</Shameful plug>
to get the numeric check I had to do change the number to a list (to
reverse it).
module Main where
import Data.List
--Stole numberToList code from:
--http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list-haskell.html
numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let
(a,b) = x `quotRem` 10 in Just (b,a))
is_palimdrome number = num_list == reverse num_list
where
num_list = numberToList number
main :: IO ()
main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome
(x * y)]
where nums = [1000,999..100]
on my quadcore box w/ 3G of Ram the compiled code runs in .6 ms.
I'm posting this to share my answer, but also to get any feed back on
how I could make this code better.
Bryce
On 07/28/2010 04:33 PM, Daniel Fischer wrote:
> On Thursday 29 July 2010 00:29:56, Andreas Flierl wrote:
>
>> Hello everyone,
>>
>> I am a newbie to Haskell coming from a Java/Scala/Ruby background. As
>> first few exercises, I was trying to translate my Scala solutions for
>> some Project Euler [1] problems to Haskell. The function that solves
>> problem 4 turns out to be quite slow (6s in Haskell as opposed to 400ms
>> in Scala) and I cannot understand why. Here's the function:
>>
>> euler4 = solve 100 999
>> where solve min max = maximum palindromes
>> where palindromes = [n | a<- range, b<- range, let n = a
>> * b, isPalindrome n] range = [max, max - 1 .. min]
>> isPalindrome n = (n :: Int) == (read $ reverse $ show n)
>>
> Try
>
> isPalindrome n = let s = show n in s == reverse s
>
> `read' is slow, though I didn't expect it to be that slow, to be honest.
> The above change brought time down from ~5.1 secs to 0.22 secs here.
>
> You can make it still faster if you make an arithmetic palindrome check
> instead of converting to String (0.1 secs).
>
> With algorithmic improvements more can be gained.
>
>
>> Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems
>> rather high to me. My guess would be that this is somehow related to
>> lazy evaluation but all in all, I've got no real clue and would be
>> thankful for any advice.
>>
> The problem (part of it at least) is that the Read instances for number
> types has been written more with elegance in mind than efficiency,
> apparently.
> Thus when you want to read an Int, first a generic number, possibly
> including a fractional part and an exponent or represented in base 8 or 16
> is tried to be read.
> That number is read as an Integer or a Rational (depending on the presence
> of a fractional part and an exponent [and its value]).
> If the read produced an Integer, that is then converted to the appropriate
> number type [Int in this case].
>
> That gives very elegant, but not very fast code.
>
>
>> Thank you
>> Andreas
>>
>>
> Cheers,
> Daniel
>
> _______________________________________________
> 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/20100728/8df2ebc8/attachment-0001.html
------------------------------
Message: 7
Date: Thu, 29 Jul 2010 03:21:46 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Why is this function that slow?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Thursday 29 July 2010 02:02:04, Bryce Verdier wrote:
> <Shameful plug>http://scrollingtext.org/project-euler-problem-4</Shameful
plug>
You wrote there:
"If anyone knows of a way to run haskell interpretively, and without using
ghci, please let me know."
a) what's wrong with ghci?
b) hugs [that is an interpreter only, no attached compiler]
>
> to get the numeric check I had to do change the number to a list (to
> reverse it).
>
> module Main where
>
> import Data.List
>
> --Stole numberToList code from:
> --http://www.rhinocerus.net/forum/lang-functional/95473-converting-numbe
>r-list-haskell.html numberToList = reverse . unfoldr (\x -> if x == 0
> then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a))
Here you're only interested in whether it's a palindrome, so the `reverse'
is an unnecessary waste of time.
Removing it doesn't gain much time, though.
>
> is_palimdrome number = num_list == reverse num_list
> where
> num_list = numberToList number
>
> main :: IO ()
> main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome
> (x * y)]
> where nums = [1000,999..100]
>
> on my quadcore box w/ 3G of Ram the compiled code runs in .6 ms.
I hope that is a typo, it takes approximately 0.6 seconds here.
>
> I'm posting this to share my answer, but also to get any feed back on
> how I could make this code better.
Without type signatures, the types default to Integer.
Everything comfortably fits in an Int, so specifying the type as Int gives
a small speedup (it's small because GHC special-cases small Integers and
uses Int-arithmetic throughout here, but it must do some checks to see
whether a large Integer is necessary, which can be avoided by using Int).
Here at least, using let s = show n in s == reverse s is the much faster
palindrome test.
You can halve the running time by using the property
x * y == y * x
of multiplication.
You can chop a further 10% off by eliminating multiples of 10 (which never
give palindromes).
You can make it much faster by considering only pairs which have a larger
product than the largest palindrome found so far (that means you can't use
such a simple list-comprehension, so if better code means shorter code,
that won't be better).
You can further speed it up by using a little math to find necessary
conditions for x * y to be a (six-digit) palindrome.
Alternatively, you can bring the runtime down by reversing your approach,
instead of checking whether the product is a palindrome, check whether a
palindrome can be written as a product of two three-digit numbers.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 25, Issue 55
*****************************************
