Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/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. Updates in the ST monad, seems slow ([email protected])
2. Streams (mike h)
3. Re: Streams (Francesco Ariis)
4. Re: Updates in the ST monad, seems slow (Sylvain Henry)
----------------------------------------------------------------------
Message: 1
Date: Thu, 27 Jul 2017 08:44:19 +0200
From: [email protected]
To: [email protected]
Subject: [Haskell-beginners] Updates in the ST monad, seems slow
Message-ID: <20170727064419.GR2658@keysersoze>
Content-Type: text/plain; charset=us-ascii
Hi all. I'm a Haskell beginner looking for valuable inputs, I don't expect my
program to magically fix itself.
I've implemented a maximum matching graph algorithm in Haskell. The
implementation specification uses some state, some arrays that are indexed and
updated throughout the algorithm.
At first, I implemented the state using HashMaps. This went well, but the
runtime wasn't close to my professors corresponding C program. I profiled my
program and found out that adjusting the maps were taking alot of time.
Then, I had a look at Data.HashTable.ST.Basic. I thought, getting average
constant time lookup and insert would surely fix the problem with the slow
state updates. I reimplemented the algorithm using HashTables and ran the
program.
As it turned out, the runtime didn't decrease using the ST monad, rather
increase. And heavily. A program instance that took 100 seconds using maps now
took 400 seconds. Looking at a profiling sample, it shows that HashTable lookup
and other various procedures related to HashTables are the big time consumers.
How can this be possible? Any ideas?
The code is available under https://github.com/lsund/edmonds-matching/ where:
The 'main' branch is the map implementation, and 'hashtable' branch is the
hashtable implementation.
The code is quite messy, and since I'm a beginner, probably inefficient. It is
the first time I implemented anything using the ST monad. So I'm afraid that I
don't understand it perfectly, and made some serious implementation flaw.
Best Regards,
Ludvig
------------------------------
Message: 2
Date: Thu, 27 Jul 2017 09:33:33 +0100
From: mike h <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Streams
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hi,
I'm looking at this:
data Stream a = Cons a (Stream a)
and with
streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f a = Cons a (streamFromSeed f (f a))
I can do, for example,
evens :: Stream Integer
evens = streamFromSeed (+2) 0
what I'd like to do is take one item at a time from the stream. My first shot
was
next :: (Stream a) -> (Stream a, a)
but that means I need to keep a ref to the stream that is returned in the tuple
which makes for messy code
for subsequent calls to next. I sense that the State monad needs to be involved
but I'm not sure exactly how as
my experiments with State still required I keep a ref to the 'new' stream.
Conceptually I see this as a 'global' state
and next is just
next :: a
but that's 30 years of imperative programming speaking and is, I think, wrong!
Any help would be really appreciated.
Thanks
Mike
------------------------------
Message: 3
Date: Thu, 27 Jul 2017 12:08:03 +0200
From: Francesco Ariis <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Streams
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Thu, Jul 27, 2017 at 09:33:33AM +0100, mike h wrote:
> What I'd like to do is take one item at a time from the stream. My first
> shot was
>
> next :: (Stream a) -> (Stream a, a)
>
> but that means I need to keep a ref to the stream that is returned in the
> tuple which makes for messy code
> for subsequent calls to next. I sense that the State monad needs to be
> involved but I'm not sure exactly how as
> my experiments with State still required I keep a ref to the 'new' stream.
> Conceptually I see this as a 'global' state
> and next is just
>
> next :: a
>
> but that's 30 years of imperative programming speaking and is, I think,
> wrong!
Hello Mike,
I see nothing wrong with a State monad (you signature looks really like
the one inside a State monad, after all)
next :: Stream a -> (a, Stream a)
next' :: s -> (a, s )
Many many many other ways of dealing elegantly with streams have been
proposed; check for example this article [1], which starts exactly
from your example, e.g.
data Stream b = SCons (b, Stream b)
And then, if you are sold to the idea, exploring the various libraries
on hackage is the other half of the fun :P
-F
[1] https://blog.jle.im/entry/intro-to-machines-arrows-part-1-stream-and
------------------------------
Message: 4
Date: Thu, 27 Jul 2017 13:08:43 +0200
From: Sylvain Henry <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Updates in the ST monad, seems slow
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8; format=flowed
I don't know why it is slower but since you're using ST you could try
with (unboxed) arrays instead of hashmaps:
https://hackage.haskell.org/package/array-0.5.1.0/docs/Data-Array-ST.html
On 27/07/2017 08:44, [email protected] wrote:
> Hi all. I'm a Haskell beginner looking for valuable inputs, I don't expect my
> program to magically fix itself.
>
> I've implemented a maximum matching graph algorithm in Haskell. The
> implementation specification uses some state, some arrays that are indexed
> and updated throughout the algorithm.
>
> At first, I implemented the state using HashMaps. This went well, but the
> runtime wasn't close to my professors corresponding C program. I profiled my
> program and found out that adjusting the maps were taking alot of time.
>
> Then, I had a look at Data.HashTable.ST.Basic. I thought, getting average
> constant time lookup and insert would surely fix the problem with the slow
> state updates. I reimplemented the algorithm using HashTables and ran the
> program.
>
> As it turned out, the runtime didn't decrease using the ST monad, rather
> increase. And heavily. A program instance that took 100 seconds using maps
> now took 400 seconds. Looking at a profiling sample, it shows that HashTable
> lookup and other various procedures related to HashTables are the big time
> consumers.
>
> How can this be possible? Any ideas?
>
> The code is available under https://github.com/lsund/edmonds-matching/
> where:
> The 'main' branch is the map implementation, and 'hashtable' branch is the
> hashtable implementation.
>
> The code is quite messy, and since I'm a beginner, probably inefficient. It
> is the first time I implemented anything using the ST monad. So I'm afraid
> that I don't understand it perfectly, and made some serious implementation
> flaw.
>
> Best Regards,
> Ludvig
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 109, Issue 20
******************************************
