Re: [Haskell-cafe] ANNOUNCE: The Haskell Platform 2009.2.0.2
Don Stewart wrote: We're pleased to announce the third release of the Haskell Platform: a single, standard Haskell distribution for everyone. The specification, along with installers (including Windows and Unix installers for a full Haskell environment) are available. Download the Haskell Platform 2009.2.0.2: http://hackage.haskell.org/platform/ Maybe I'm being dense... Is there somewhere which lists what's changed from the last release? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] ANNOUNCE: OpenGL 2.3.0.0
Rafael Gustavo da Cunha Pereira Pinto wrote: Sorry for all this annoyance, but I was starting to study those libraries (OpenGL, GLUT and GLFW) using Haskell and the update broke some of my code. Here is a patch that makes it compile, but then it breaks all code developed for GLFW-0.3, as all Floats need to be changed to CFloat. --- GLFW-0.3/Graphics/UI/GLFW.hs 2008-01-15 20:23:18.0 -0200 +++ GLFW.hs 2009-07-30 21:09:55.0 -0300 @@ -517,11 +517,11 @@ _GLFW_INFINITY = 10.0 :: Double -- Callback function type -type GLFWwindowsizefun = Int32 - Int32 - IO () +type GLFWwindowsizefun = CInt - CInt - IO () [snip] You should use the type aliases GLint, GLfloat, etc. HTH, Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
2009/7/31 Paul Moore p.f.mo...@gmail.com: 2009/7/31 Gregory Collins g...@gregorycollins.net: Paul Moore p.f.mo...@gmail.com writes: How would I efficiently write a function in Haskell to count occurrences of unique elements in a (potentially very large) list? For example, given the list [1,2,3,4,5,3,4,2,4] I would like the output [[1,1], [2,2], [3,2], [4,3], [5,1]] (or some equivalent representation). import qualified Data.Map as Map import Data.Map (Map) histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m Right. I see how that works, and can work out how to think about this sort of thing from your example. Thanks very much. BTW, I did know that Haskell had an efficient map implementation, I just wasn't sure how to use it functionally - I probably should have searched a bit harder for examples before posting. Thanks for the help in any case. Hmm, I'm obviously still mucking up the performance somehow. My full program (still a toy, but a step on the way to what I'm aiming at) is as follows. It's rolling 3 6-sided dice 10 times, and printing a summary of the results. import System.Random import qualified Data.Map as Map import Data.Map (Map) import Data.List dice :: Int - Int - IO Int dice 0 n = return 0 dice m n = do total - dice (m - 1) n roll - randomRIO (1, n) return (total + roll) simulate count m n = do mapM (dice m) (replicate count n) histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m simulation = do lst - simulate 10 3 6 return (histogram lst) main = do s - simulation putStrLn (show s) When compiled, this takes over twice as long as a naively implemented Python program. What am I doing wrong here? I'd have expected compiled Haskell to be faster than interpreted Python, so obviously my approach is wrong. I'm expecting the answer to be that I've got unnecessary laziness - which is fine, but ultimately my interest is in ease of expression and performance combined, so I'm looking for beginner-level improvements rather than subtle advanced techniques like unboxing. Thanks, Paul. PS I know my code is probably fairly clumsy - I'd appreciate style suggestions, but my main interest here is whether a beginner, with a broad programming background, a basic understanding of Haskell, and access to Google, put together a clear, efficient, program (ie, the case where my usual scripting language is too slow and I want to knock something up quickly in a high-level, high-performance language). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
On Sat, Aug 1, 2009 at 4:44 PM, Paul Moorep.f.mo...@gmail.com wrote: PS I know my code is probably fairly clumsy - I'd appreciate style suggestions, but my main interest here is whether a beginner, with a broad programming background, a basic understanding of Haskell, and access to Google, put together a clear, efficient, program (ie, the case where my usual scripting language is too slow and I want to knock something up quickly in a high-level, high-performance language). Here is one way to rewrite your program. It improved the speed somewhat for me. I timed both programs on my computer. I suppose one could try using an array for calculating the histogram as well, but I only tried the simples thing here. I hope someone can weigh in with a more thorough analysis. Please note how I've avoided including the IO Monad in some type signatures by extracting the data from it locally (with -). It is quite possible to apply the histogram function to the data before going through the IO Monad as well, but it doesn't appear to change the execution speed much here. Caveat: My testing wasn't extensive. I just compiled with -O and timed the programs a couple of times. import System.Random import qualified Data.Map as Map import Data.Map (Map) import Data.List diceRolls :: Int - IO [Int] diceRolls highVal = do generator - getStdGen return (randomRs (1, highVal) generator) groupDice :: Int - [Int] - [[Int]] groupDice chunk rolls = map (take chunk) $ iterate (drop chunk) rolls simulate :: Int - Int - Int - IO [Int] simulate count m n = do rolls - diceRolls n let sums = map sum $ groupDice m rolls return (take count sums) histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m simulation = do lst - simulate 10 3 6 return (histogram $ lst) main = do s - simulation putStrLn (show s) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Possible bug in Data.IP (network-data package)
Hi
The network-data (version 0.0.2) [1] contains the module Data.IP. This
modules encapsulates IPv4 headers. The Data.IP modules contains the type
IPv4Header:
data IPv4Header =
IPv4Hdr { hdrLength :: Int
, version :: Int
, tos :: Int
, payloadLength :: Int
...
The code to turn IPv4 packages into IPv4Heder looks like [2]:
instance Binary IPv4Header where
put (IPv4Hdr ihl ver tos len id flags off ttl prot csum src dst) = do
pW8 $ (ihl .. 0xF) .|. (ver `shiftL` 4 .. 0xF0)
pW8 tos
pW16 len
pW16 id
let offFlags = (off .. 0x1FFF) .|. fromIntegral (fromEnum flags
`shiftL` 13)
pW16 offFlags
pW8 ttl
pW8 prot
put csum
put src
put dst
That is, the payload length is the 16-31'th bit of the IPv4 header. This
field is according to [3] and [4] referred to as total length - not
payload length. The total length include both the length of the data
and the header. When I read the term payload length I first thought it
referred to the length of the package excluding the header.
So I am right to see this as a bug in network-data ?
Regards,
Mads Lindstrøm
[1] http://hackage.haskell.org/package/network-data
[2]
http://hackage.haskell.org/packages/archive/network-data/0.0.2/doc/html/src/Data-IP.html
[3] http://tools.ietf.org/html/rfc791
[4] http://en.wikipedia.org/wiki/IPv4#Header
signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Strange memory usage problem
John Lato jwl...@gmail.com writes:
I can confirm this behavior on GHC 6.10.4 on OSX 10.5.7.
Great, thanks!
Try adding
{-# INLINE getRB #-}
above the getRB definition. That fixes it for me.
And I especially appreciate this, of course. It appears to do the
trick here, too.
I think that when the rest of the code is commented out, getRB is only
called in one location, so GHC inlines it automatically. Since getRB
is also called in the commented-out code, it probably isn't
automatically inlined when that code is available. I suspect that the
inlining allows GHC to infer some strictness property it otherwise
can't.
Sounds reasonable. The getRB function 'get's a couple of bytestrings
and lazy bytestrings from the input - apparently these aren't fully
evaluated by the Get monad? I thought it might be the lazy ones, but
I replaced them with strict bytestrings with no noticable success.
I'm not entirely happy with the inline pragma as a solution, since it
indicates that I'm depending on the optimizing-fu of GHC to make my
program work, and this seems fragile. So far, it appears to be the
best solution.
-k
--
If I haven't seen further, it is by standing in the footprints of giants
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
Paul Moore p.f.mo...@gmail.com writes: What am I doing wrong here? I'd have expected compiled Haskell to be faster than interpreted Python, so obviously my approach is wrong. Two things from my experience: Python associative arrays are fast, and Haskell random numbers are slow. So by building a map from random numbers, you are likely doing a fairly pessimal comparison. Did you profile to see where the time is spent? I'm expecting the answer to be that I've got unnecessary laziness IME, laziness usually affects space, but not so much time performance. Although 'insertWith (+)' looks like it would build unevaluated thunks for the sums. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
2009/8/1 Ketil Malde ke...@malde.org: Paul Moore p.f.mo...@gmail.com writes: What am I doing wrong here? I'd have expected compiled Haskell to be faster than interpreted Python, so obviously my approach is wrong. Two things from my experience: Python associative arrays are fast, and Haskell random numbers are slow. So by building a map from random numbers, you are likely doing a fairly pessimal comparison. Hmm, I think you're saying that for this problem, Haskell is likely to be worse than Python. Interesting. I guess I'd assumed that something CPU-intensive like this would benefit from a compiled language. Just goes to show that intuition about performance is usually wrong (something I really should know by now :-)) Is the issue with random numbers just the implementation, or is it something inherent in the non-pure nature of a random number generator that makes it hard for Haskell to implement efficiently? If the latter, that probably makes Haskell a somewhat poor choice for simulation-type programs. Did you profile to see where the time is spent? Not until you suggested it :-) I was pleasantly surprised by how easy it was to do. The results bear out what you were saying, the bottleneck is entirely in the dice function. I'm expecting the answer to be that I've got unnecessary laziness IME, laziness usually affects space, but not so much time performance. Although 'insertWith (+)' looks like it would build unevaluated thunks for the sums. That'll teach me to bandy about technical terms as if I understand them :-) Thanks for the comments, Paul. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Retrieving inner state from outside the transformer
Thanks very much for both replies.
I think I get this now.
Simply, my choice of evaluation functions (evalStateT, execStateT and
execState) ensured that the states are not returned. It was obvious.
I can get this working, but I have one more more question to make sure
I actually understand this.
Below is a very simple and pointless example I wrote to grasp the
concept. This returns ((1,23),21) which is clear to me.
import Control.Monad.State
myOuter :: StateT Int (State Int) Int
myOuter = StateT $ \s - do p - get
return (s,p+s+1)
main :: IO()
main = do let innerMonad = runStateT myOuter 1
y = runState innerMonad 21
print y
Thus we are saying that a=(1,23) and s=21 for the state monad, and
that a=1 and s=23 for the state transformer. That is the return value
of the state monad is the (a,s) tuple of the transformer and it's own
state is of course 21.
This got me thinking - the return value's type of the state monad is
dictated by the evaluation function used on the state transformer - it
could be a, s, or (a,s) depending which function is used. Thus if I
edit the code to to:
do let innerMonad = evalStateT myOuter 1
I get back (1,21) - which is the problem I had - we've lost the
transformer's state.
Look at the Haskell docs I get:
evalStateT :: Monad m = StateT s m a - s - m a
runStateT :: s - m (a, s)
So the transformer valuation functions are returning a State monad
initialized with either a or (a,s).
Now I know from messing around with this that the initialization is
the return value, from the constructor:
newtype State s a = State {
runState :: s - (a, s)
}
Am I right in assuming that I can read this as:
m (a,s_outer) returned from runStateT is equivalent to calling the
constructor as (State s_inner) (a,s_outer)
This makes sense because in the definition of myOuter we don't specify
the return value type of the inner monad:
myOuter :: StateT Int (State Int) Int
The problem is whilst I can see that we've defined the inner monad's
return value to equal the *type* of the transformer's evaluation
function, I'm loosing the plot trying to see how the *values* returned
by the transformer are ending up there. We haven't specified what the
state monad actually does?
If I look at a very simple example:
simple :: State Int Int
simple = State $ \s - (s,s+1)
This is blindly obvious, is I call 'runState simple 8', I will get
back (8,9). Because I've specified that the return value is just the
state.
In the more original example, I can see that the 'return (s,p+s+1)'
must produce a state monad where a=(1,23), and the state of this monad
is just hardcoded in the code = 21.
I guess what I'm trying to say is - where is the plumbing that ensures
that this returned value in the state/transformer stack is just the
(a,s) of the transformer?
I have a terrible feeling this is a blindly obvious question -
apologies if it is!
Thanks again!
Phil.
On 31 Jul 2009, at 04:39, Ryan Ingram wrote:
StateT is really simple, so you should be able to figure it out:
runStateT :: StateT s m a - s - m (a,s)
runState :: State s a - s - (a,s)
So if you have
m :: StateT s1 (StateT s2 (State s3)) a
runStateT m :: s1 - StateT s2 (State s3) (a,s)
\s1 s2 s3 - runState (runStateT (runStateT m s1) s2) s3)
:: s1 - s2 - s3 - (((a,s1), s2), s3)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
I'm expecting the answer to be that I've got unnecessary laziness - which is fine, but ultimately my interest is in ease of expression and performance combined, so I'm looking for beginner-level improvements rather than subtle advanced techniques like unboxing. You're right, it is too lazy. Here are a couple of strictifications that should help: histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m Turn foldl into foldl' (from Data.List) and Map.insertWith into Map.insertWith'. The strict versions simply force the intermediate structures to be evaluated, rather than hanging around as large accumulations of closures. Regards, Malcolm ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
Am Samstag 01 August 2009 15:44:39 schrieb Paul Moore: 2009/7/31 Paul Moore p.f.mo...@gmail.com: 2009/7/31 Gregory Collins g...@gregorycollins.net: Hmm, I'm obviously still mucking up the performance somehow. My full program (still a toy, but a step on the way to what I'm aiming at) is as follows. It's rolling 3 6-sided dice 10 times, and printing a summary of the results. import System.Random import qualified Data.Map as Map import Data.Map (Map) import Data.List dice :: Int - Int - IO Int dice 0 n = return 0 dice m n = do total - dice (m - 1) n roll - randomRIO (1, n) return (total + roll) Don't do too much in IO, it's better to separate the pure parts from the IO. IMO, this would better have signature dice :: RandomGen g = Int - Int - g - (Int,g) dice 0 _ g = (0,g) dice m n g = case dice (m-1) n g of (total,g1) - case randomR (1,n) g1 of (roll,g2) - (total+roll,g2) or, better still be in a State monad or the Random monad ( http://hackage.haskell.org/package/MonadRandom ) die :: RandomGen g = Int - State g Int die n = State $ randomR (1,n) dice :: RandomGen g = Int - Int - State g Int dice m n = liftM sum $ replicateM m (die n) -- the do is superfluous simulate count m n = do mapM (dice m) (replicate count n) Ouch, that hurts (not yet so incredibly much for 10 rolls, but if you try 100, it'll really hurt). Since you're doing it in IO, the whole list must be built before any further processing can begin, so you're building up a largish list, only to destroy it immediately afterwards, much work for the garbage collector. If you can accumulate the scores as they come, the intermediate list can be fused away and the garbage collector is kept idle. If you absolutely have to do it in IO, use import System.IO.Unsafe simulate 0 _ _ = return [] simulate count m n = unsafeInterleaveIO $ do val - dice m n rst - simulate (count-1) m n return (val:rst) to avoid building a large list. If you use the (lazy) State monad, that's automatically done :). simulate count m n = replicateM count (dice m n) -- now in State histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m -- simulation :: RandomGen g = State g [(Int,Int)] simulation = do lst - simulate 100 3 6 return (histogram lst) main = do sg - getStdGen print $ evalState simulation sg much faster, still not very fast, since StdGen isn't a particularly fast PRNG. Another method is to create an infinite list of random numbers and use it as needed: --- module Main (main) where import System.Random import Data.Array.Unboxed import Data.List import System.Environment (getArgs) dice :: RandomGen g = g - Int - [Int] dice g mx = randomRs (1,mx) g splits :: Int - [a] - [[a]] splits l = unfoldr f where f xs = case splitAt l xs of r@(h,t) | null t- Nothing | otherwise - Just r simulation :: RandomGen g = g - Int - Int - Int - UArray Int Int simulation g rep dn df = accumArray (+) 0 (dn,dn*df) lst where rls = dice g df scs = splits dn rls lst = take rep [(sum rll,1) | rll - scs] main :: IO () main = do (rp:dn:df:_) - getArgs sg - getStdGen print $ assocs $ simulation sg (read rp) (read dn) (read df) - Using an unboxed array instead of a Map gives a little extra speed, but not much. histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl f Map.empty where f m k = Map.insertWith (+) k 1 m For some reason it doesn't make much difference here, but it should be the strict versions, foldl' and insertWith' in general. simulation = do lst - simulate 10 3 6 return (histogram lst) main = do s - simulation putStrLn (show s) When compiled, this takes over twice as long as a naively implemented Python program. What am I doing wrong here? I'd have expected compiled Haskell to be faster than interpreted Python, so obviously my approach is wrong. I'm expecting the answer to be that I've got unnecessary laziness Quite on the contrary, it's unnecessary strictness here :D - which is fine, but ultimately my interest is in ease of expression and performance combined, so I'm looking for beginner-level improvements rather than subtle advanced techniques like unboxing. Nothing advanced with using unboxed arrays. Thanks, Paul. PS I know my code is probably fairly clumsy Actually, the style is rather good, I think (mine's worse, usually). You shouldn't use IO so much, though, and your code betrays a certain level of unfamiliarity with strictness/performance characteristics of the libraries. But that's natural. - I'd appreciate style suggestions, but my main interest here is whether a beginner, with a broad
Re: [Haskell-cafe] ANN: atom 0.1.0
Note too that there's an example Atom program included with the source: http://hackage.haskell.org/packages/archive/atom/0.1.0/doc/html/Language-Atom-Example.html Lee dons wrote: We've had a few people playing with Atom to program the Arduino, and John van Enk's been hacking too, Atom Arduino :: Some Hacking (pt. 1) http://blog.sw17ch.com/wordpress/?p=84 An Atomic Fibonacci Server: Exploring the Atom (Haskell) DSL http://leepike.wordpress.com/2009/05/05/an-atomic-fibonacci-server-exploring-the-atom-haskell-dsl/ Galois will prob. have a tech talk soon. -- Don thomas.dubuisson: Tom, I was asking earlier about any good sources of information for atom. It seems the once-good wiki is gone - are there tutorials for Atom hiding in forgotten corners? Thomas On Fri, Jul 31, 2009 at 1:49 PM, Tom Hawkinstomahawk...@gmail.com wrote: Atom is a Haskell DSL for hard realtime applications. This release includes support for assertions and functional coverage to aid simulation and testing. The rev of the minor version indicates a bit of library stability. This is the version we're using for our application, which officially went into production and hit the road last month -- literally. http://hackage.haskell.org/package/atom -Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient functional idiom for histogram
On Aug 1, 2009, at 2:06 PM, Paul Moore wrote: Is the issue with random numbers just the implementation, or is it something inherent in the non-pure nature of a random number generator that makes it hard for Haskell to implement efficiently? If the latter, that probably makes Haskell a somewhat poor choice for simulation-type programs. Well, I'm not sure of the details, but in your original implementation, you're performing IO to pull the seed out of a ref at every iteration. Pekka Karjalainen's doesn't do that, which probably helps with the speedup. Along with that, Haskell has a fairly slow random implementation. As I recall however, this is partially because it hasn't received a great deal of optimization, but mainly because the algorithm itself fulfills some rather strong properties -- in particular it must be fairly statistically robust, and it must provide a split function which produces generators that are independently robust [1]. This limits algorithm choice quite a bit. For other random numbers, with different properties (faster, but with tradeoffs in robustness, or ability to split, or both), you can check hackage for at least mersenne-random and gsl-random. There may be others that I don't recall. Cheers, Sterl. [1] http://www.haskell.org/onlinereport/random.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Retrieving inner state from outside the transformer
I am not sure I entirely understand your question; it sounds like you
are confused and thus your question is a bit confused. So instead,
I'll explain in a bit more detail.
A common pattern in Haskell is that you have a type that you want to
perform some operations on, and then afterwards you observe the type
to convert it to some simpler type that no longer has those
operations.
To see why the observation is important, consider this type:
newtype StupidT s m a = StupidT ()
Would you believe that StupidT is a state monad transformer?
instance Monad StupidT s m where
return _ = StupidT ()
StupidT () = f = StupidT ()
instance MonadState s (StupidT s m) where
get = StupidT ()
put _ = StupidT ()
instance MonadTrans (StupidT s) where
lift _ = StupidT ()
StupidT follows all the laws for these typeclasses, because they all
have to do with observational equality of different sets of
operations. Since all operations are equal, the laws all trivially
hold. For example:
Proof: get = put = return () (this is one of the laws every
MonadState needs to fulfill)
get = put
apply (=)
= StupidT ()
unapply return
= return ()
All of the other laws are proved similarily.
Obviously, you can't do much with StupidT; the thing that makes StateT
useful is its observation function runStateT
runStateT :: StateT s m a - (s - m (a,s))
which converts from (StateT s m a), into (s - m (a,s)).
You'll often find that the most elegant implementation of a type in
Haskell is to use the observation function's return type as the
representation type of the object! So since we want runStateT with
this particular type, we just make StateT hold that type:
newtype StateT s m a = StateT { runStateT :: s - m (a,s) }
Now, of course, we have to implement all the operations we care about
(return, (=), get, put, lift), such that they obey the laws those
operations are supposed to fulfill, but implementing the observation
function is trivial!
So, how does the plumbing convert the s you give it into a m (a,s)
result? Simple, there is no plumbing. You just call the function!
Of course, there is some plumbing in the implementation of the
operations on the transformer:
instance Monad m = Monad (StateT s m) where
return a = StateT $ \s - return (a,s)
m = f = StateT $ \s0 - do
(a, s1) - runStateT m s0
(b, s2) - runStateT (f a) s1
return (b,s2)
instance Monad m = MonadState s (StateT s m) where
get = StateT $ \s - return (s,s)
put s = StateT $ \_ - return ((), s)
instance MonadTrans (StateT s) where
lift m = StateT $ \s - do
a - m
return (a,s)
You should notice that all this makes runStateT just work; there's
no need to call additional code to get the (s - m (a,s)) back out of
the StateT. You should also notice that these are the *only*
type-correct, non-_|_-using implementations for most of the functions;
the only places where we could make a semantic error that wasn't also
a type error are putting the wrong states through (put) and (=). By
choosing a representation that matches the observable value we want,
implementing the operations becomes much simpler!
-- ryan
On Sat, Aug 1, 2009 at 11:06 AM, p...@beadling.co.uk wrote:
Thanks very much for both replies.
I think I get this now.
Simply, my choice of evaluation functions (evalStateT, execStateT and
execState) ensured that the states are not returned. It was obvious.
I can get this working, but I have one more more question to make sure I
actually understand this.
Below is a very simple and pointless example I wrote to grasp the
concept. This returns ((1,23),21) which is clear to me.
import Control.Monad.State
myOuter :: StateT Int (State Int) Int
myOuter = StateT $ \s - do p - get
return (s,p+s+1)
main :: IO()
main = do let innerMonad = runStateT myOuter 1
y = runState innerMonad 21
print y
Thus we are saying that a=(1,23) and s=21 for the state monad, and that a=1
and s=23 for the state
transformer. That is the return value of the state monad is the (a,s) tuple of the transformer and it's own state is of course 21.
This got me thinking - the return value's type of the state monad is dictated by the evaluation function used
on the state transformer - it could be a, s, or (a,s) depending which function is used. Thus if I edit the code to to:
do let innerMonad = evalStateT myOuter 1
I get back (1,21) - which is the problem I had - we've lost the
transformer's state.
Look at the Haskell docs I get:
evalStateT :: Monad m = StateT s m a - s - m a
runStateT :: s - m (a, s)
So the transformer valuation functions are returning a State monad
initialized with either a or (a,s).
Now I know from messing around with this that the initialization is the
return value, from the constructor:
newtype State s a = State {
runState :: s - (a, s)
}
Am I right in assuming that I
Re: [Haskell-cafe] Efficient functional idiom for histogram
Am Samstag 01 August 2009 20:50:10 schrieb Sterling Clover: On Aug 1, 2009, at 2:06 PM, Paul Moore wrote: Is the issue with random numbers just the implementation, or is it something inherent in the non-pure nature of a random number generator that makes it hard for Haskell to implement efficiently? If the latter, that probably makes Haskell a somewhat poor choice for simulation-type programs. If you view a PRNG as a function from the seed to the sequence of generated numbers or as a function state - (bitpattern, newstate), PRNGs are pure (at least, I know no counterexample), so it's not inherently inefficient in Haskell, though it's probably still faster in C. One thing that makes StdGen slow is splittability, as Sterling points out below. For a simulation programme where you don't need splittability, choose a different PRNG. Well, I'm not sure of the details, but in your original implementation, you're performing IO to pull the seed out of a ref at every iteration. Pekka Karjalainen's doesn't do that, which probably helps with the speedup. Along with that, Haskell has a fairly slow random implementation. As I recall however, this is partially because it hasn't received a great deal of optimization, but mainly because the algorithm itself fulfills some rather strong properties -- in particular it must be fairly statistically robust, and it must provide a split function which produces generators that are independently robust [1]. This limits algorithm choice quite a bit. For other random numbers, with different properties (faster, but with tradeoffs in robustness, or ability to split, or both), you can check hackage for at least mersenne-random and gsl-random. I didn't get much speedup with System.Random.Mersenne.Pure64 (might be because I have a 32-bit system and Word64 goes through foreign calls, if that is still the case), but GSL.Random.Gen reduced the time by a factor of over 5. It forces you back into IO and is a little less convenient, but if speed is a concern, it's a price worth to pay. --- module Main (main) where import GSL.Random.Gen import qualified Data.Map as Map import Data.Map (Map) import Data.List import System.IO.Unsafe import System.Time import Data.Word dice :: RNG - Int - Int - IO Int dice _ 0 n = return 0 dice rng m n = do total - dice rng (m - 1) n roll - fmap (+1) $ getUniformInt rng n return (total + roll) simulate _ 0 _ _ = return [] simulate rng count m n = unsafeInterleaveIO $ do val - dice rng m n tl - simulate rng (count-1) m n return (val:tl) histogram :: Ord a = [a] - [(a,Int)] histogram = Map.assocs . foldl' f Map.empty where f m k = Map.insertWith' (+) k 1 m simulation rng = do lst - simulate rng 100 3 6 return (histogram lst) main = do rng - newRNG mt19937 sd - getTimeSeed setSeed rng sd -- omit seeding for reproducible results s - simulation rng putStrLn (show s) getTimeSeed :: IO Word64 getTimeSeed = do TOD a b - getClockTime return . fromInteger $ 10^6*a + b `quot` (10^6) -- There may be others that I don't recall. Cheers, Sterl. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Proposal: TypeDirectedNameResolution
One issue I have which I haven't seen anyone mention is that it's not useful with qualified names, by which I mean always importing qualified. Of course if you have no problem always using qualified names, the problem this extension is solving doesn't exist. Though I do like short names I'm not terribly bothered by writing Map.map and List.map. Most calls in a module are within the module after all, which is as it should be in most cases. So this extension would do nothing for me. I like the explicitness of qualified names, and I find it hard to read someone's module when they call some function that comes somewhere out of a list of 15 imports at the top, and this extension would make it even harder to find the definition of the function... though tags would narrow down the search a lot. But with modules, often the prepended module name is all the information I need at the moment. On the other hand, I do acknowledge that I'm pretty used to seeing x.y in an OO language and often don't mind that I need to know the type of 'x' and maybe even find the constructor call to know where to look for 'y'. So maybe it's not that big of a deal. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Possible bug in Data.IP (network-data package)
So I am right to see this as a bug in network-data ? Yes, the payloadLength field was poorly (read: incorrectly) named perhaps due to having recently read IPv6 specs. This will be corrected in version 0.1.0 which I plan on uploading soon (tonight). Thanks! Thomas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Cyclic data declarations
I'm in the process of writing a toy compiler but I'm having some trouble trying to make my datatypes general. For example, using parsec I parse statements as: data Stmt = SIf Test [Stmt] [Stmt] | ... However, when it's time to create a control flow graph it would be nice to represent statements as (the Int's signify the node id's for either case of the if statement): data Stmt = SIf Test Int Int | ... So, in a eureka moment I decided that this should be allowable with the following declaration: data Stmt link = SIf Test link link | ... Ofcourse, the problem is trying to declare the resulting type for parsing: parse - Stmt [Stmt [Stmt ]]. Any hints on whether there is a way to accomplish what I'm trying to do or do I have to bite the bullet and declare two seperate datatypes? I tried being clever and declaring a 'helper' type as type StmtRec = Stmt [StmtRec] but to no avail... GHC won't let it slide: Cycle in type synonym declarations! Cheers, Michal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic data declarations
Hello Michal, Sunday, August 2, 2009, 9:25:40 AM, you wrote: data Stmt = SIf Test [Stmt] [Stmt] | ... data Stmt = SIf Test Int Int | ... data Stmt a = SIf Test [Stmt a] [Stmt a] | ... where a will represent type of your statement. this may be read as IF statement with a left and right parts consisting of sequence of statements returning a, have type a btw, you may need to use GADTs to implement more complex statement types machinery, this is rather popular example in various GADT papers, f.e. http://www.iai.uni-bonn.de/~ralf/publications/With.pdf -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cyclic data declarations
On Sat, Aug 1, 2009 at 10:25 PM, Michal D. michal.dobrog...@gmail.comwrote: I'm in the process of writing a toy compiler but I'm having some trouble trying to make my datatypes general. For example, using parsec I parse statements as: data Stmt = SIf Test [Stmt] [Stmt] | ... One of your types could be: newtype Block = Block [Stmt] Then you could have: data Stmt = SIf Test Block Block | ... However, when it's time to create a control flow graph it would be nice to represent statements as (the Int's signify the node id's for either case of the if statement): data Stmt = SIf Test Int Int | ... Depending on the amount of code duplication, I think I'd actually make two separate data types. data GStmt = GIf Test Int Int | ... And have a function: toFlowGraph :: Stmt - GStmt So, in a eureka moment I decided that this should be allowable with the following declaration: data Stmt link = SIf Test link link | ... Clever, but I don't think I would do it this way. Ofcourse, the problem is trying to declare the resulting type for parsing: parse - Stmt [Stmt [Stmt ]]. Any hints on whether there is a way to accomplish what I'm trying to do or do I have to bite the bullet and declare two seperate datatypes? I tried being clever and declaring a 'helper' type as type StmtRec = Stmt [StmtRec] but to no avail... GHC won't let it slide: Cycle in type synonym declarations! I'd have to see your parser, but it shouldn't be too hard to work around this depending on how you want to solve it. By the way, for your StmtRec you probably want a newtype instead of a type. Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
