Re: [Haskell-cafe] Why doesn't laziness save the day here?
On Mon, Jan 4, 2010 at 6:31 PM, Dale Jordan da...@alum.mit.edu wrote: Can anyone explain why this is looping or point out a better way to generate an arbitrary-length random list while still being able to reuse the generator? (I'd rather not use split since this generator doesn't support it and its of dubious soundness.) Well there is more than one way to split. You don't have to split the generator -- if you act on a stream of random numbers, you can split the stream also: split :: [a] - ([a],[a]) split (x:xs) = (x:bs,as) where (as,bs) = split xs However too much splitting in this case causes a performance penalty, since you start discarding large portions of the stream. If you don't want to split the generator, this is the only way I can think of that is deterministic in the random seed. If determinism is not required, as many times it is not with *random* computations, you can use the value-supply package on hackage, which uses a bit of unsafePerformIO magic to turn a serial stream into a splittable stream. But you lose composable repeatability. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: lawless instances of Functor
On Mon, Jan 4, 2010 at 7:25 PM, Maciej Piechotka uzytkown...@gmail.com wrote: On Tue, 2010-01-05 at 08:01 +0900, Derek Elkins wrote: If h . p = q . g then fmap h . fmap p = fmap q . fmap g Setting p = id gives h . id = h = q . g fmap h . fmap id = fmap q . fmap g Using fmap id = id and h = q . g we get, fmap h . fmap id = fmap h . id = fmap h = fmap (q . g) = fmap q . fmap g Hmm. Not quite a proff as we want to use: For all f g fmap (f . g) = fmap f . fmap g. So we need to operate on arbitrary f and g. Also in first line conclusion is used - at this stage we don't know if h . p = p . q - fmap h . fmap p = fmap q . fmap g. No, the first line is the free theorem -- i.e. the parametericity theorem -- for the type. It holds for any Haskell value with this type, coming essentially from the fact that downcasts are not possible in Haskell. You can play with free theorems here: http://linux.tcs.inf.tu-dresden.de/~voigt/ft/. See Wadler's paper Theorem's for free! for more about them. Especially that (A-B) functions is |A|^|B| (and in haskell |A| = 1, | B| = 1). Now imagine that (in pseudocode[1]): rho :: (A - B) - A - B rho f | f is A - A = id | f is Integral - Integral = (+1) . fromIntegral | otherise = f Haskell's inability to write this function is exactly where free theorems come from. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why doesn't laziness save the day here?
2010/1/5 Dale Jordan da...@alum.mit.edu: The motivation for iterateR is to be able to have the ultimate consumer determine how many random values to force, but still have a single random generator used throughout the computation. Hi Dale If you want the producer and consumer to run at different speeds with something in-between to synchronize them (velomorphisms anyone?), you might want to look at Jeremy Gibbons's spigot algorithm for pi and also his metamorphisms paper. http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf http://www.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/metamorphisms-scp.pdf That said, I've personally found it hard to frame code in the spigot style so I couldn't readily offer any tips on the code you've presented. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: Am Montag 04 Januar 2010 16:30:18 schrieb Will Ness: For me, a real smart compiler is one that would take in e.g. (sum $ take n $ cycle $ [1..m]) and spill out a straight up math formula, inside a few ifs maybe (just an aside). Such things just aren't common enough. If you start letting the compiler look for patterns such as this which can be transformed into a simple formula, compile times would explode. I was thinking more along the lines of inferencing compiler, proving new theorems about the types and applying that knowledge in simplifying the expressions. This would take time, so it should be a part of some interactive system, maybe kind of like Lisp has. In such a setting, the underlying compiler could first produce quick-n-dirty version, and would continue working in the background whenever the system is not busy, trying to improve the executable. Such a system would probably have to distinguish, at the type level, between [1..m] ; cycle [1..m] ; take n [1..m] ; etc. These would all be not just fuctions, but parts of a type's (here list) behaviour with automatically deduced semantics. What would such a type system be called? The -fno-cse turns off Common Subexpression Elimination (rather sharing than elimination). That is, if you have f x = g (expensive x) y z (h (expensive x)) the compiler can see the common subexpression (expensive x) on the RHS and decide to share it, i.e. calculate it only once: f x = let e = expensive x in g e y z (h e) thanks for the in-depth explanation! :) Now if you have a list producer and a consumer, without fusion, it goes like Consumer: Gimme Producer: creates cons cell, puts value, next cons cell (how to produce more) Consumer: takes value, does something with it, gimme more. Stream fusion is about eliminating the cons cell creating and value passing, to fuse production and consumption into a nice loop. That is of course impossible if the produced list is shared between two (or more) consumers. I would imagine so. Do I get this fusion on lists for free from the compiler, or do I have to recode for that? (haven't yet time to look into the article mentioned). ___ Haskell-Cafe mailing list Haskell-Cafe at 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
[Haskell-cafe] Using Haskell to write dbus server
How to write (is it possible) a dbus server in Haskell? Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FASTER primes
Will Ness skrev: Emil Axelsson emax at chalmers.se writes: For me, a real smart compiler is one that would take in e.g. (sum $ take n $ cycle $ [1..m]) and spill out a straight up math formula, inside a few ifs maybe (just an aside). (Also an aside, I couldn't resist...) Then I'm sure you'd say that Feldspar [1] has a smart compiler :) but it didn't produce f n m = if n m then n*(n+1)/2 else let (q,r)=quotRem n m in q*(m*(m+1)/2) + r*(r+1)/2 :) Ah, I see... Yes, that would be a very smart compiler :) / Emil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: FASTER primes
Am Dienstag 05 Januar 2010 10:33:19 schrieb Will Ness: Such a system would probably have to distinguish, at the type level, between [1..m] ; cycle [1..m] ; take n [1..m] ; etc. These would all be not just fuctions, but parts of a type's (here list) behaviour with automatically deduced semantics. What would such a type system be called? Seriously complicated, I think. Don't get me wrong, a system with such capabilities would be A.W.E.S.O.M.E. I just can't see it happening anytime soon. I would imagine so. Do I get this fusion on lists for free from the compiler, or do I have to recode for that? (haven't yet time to look into the article mentioned). Without optimisations, hardly ever if at all (needs a compiler expert to know). With optimisations, sometimes. But it doesn't always see the possibility where it would with recoding in the right style (dons is expert in that). With stream fusion, more often. But I think it would again be not very hard to hide opportunities for fusion by your coding style. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Book reviews for the Journal of Functional Programming
If you would be interested in reviewing books for the journal of functional programming you can find a list of currently available books at http://www.cs.kent.ac.uk/people/staff/sjt/JFP/ Please let me know if you would be interested in taking on any of these reviewing assignments. Kind regards, Simon Thompson Book Reviews Editor Journal of Functional Programming ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why doesn't laziness save the day here?
Dale Jordan wrote: The motivation for iterateR is to be able to have the ultimate consumer determine how many random values to force, but still have a single random generator used throughout the computation. My intuition tells me that since the infinite list is produced in finite batches, ... Can anyone explain why this is looping or point out a better way to generate an arbitrary-length random list while still being able to reuse the generator? The others have already pointed out the problem with the imperative solution, which used the mutation of the global state with the new random seed. Imperative approach is indeed often a problem. There is a simple solution however. In fact, your message already described it. The key phrase is ``the infinite list is produced in finite batches.'' We merely need to define a list-like data structure that matches our intuitions. The complete code follows. All three run functions, run1 through run3, produce a finite result (shown in the comments after the definition). module RList where -- I don't have Mersenne Twistor installed; so I'll use the stdGen... import System.Random import Control.Monad.State data RList m a = RList [a] -- known finite prefix [m [a]] -- a stream of producing actions pullR :: Monad m = RList m a - m (RList m a) pullR (RList p (x:xs)) = x = \p' - return $ RList (p++p') xs headR :: Monad m = RList m a - m a headR (RList (x:_) _) = return x headR x = pullR x = headR tailR :: Monad m = RList m a - m (RList m a) tailR (RList (_:xs) ms) = return $ RList xs ms tailR x = pullR x = tailR -- appendR doesn't have to have the monadic type. We go for uniformity with -- the headR appendR :: Monad m = RList m a - RList m a - m (RList m a) appendR (RList p1 ms1) (RList p2 ms2) = return $ RList p1 (ms1 ++ (return p2):ms2) takeR :: Monad m = Int - RList m a - m (RList m a) takeR 0 l = return l takeR n (RList p ms) | length p = n = return $ RList (take n p) [] takeR n l = pullR l = takeR n -- quite inefficient, but short -- Other list library functions can be implemented in terms of head, tail -- the evaluator, so to speak. It is possibly strict, use it at the -- very end toList :: (Functor m, Monad m) = RList m a - m [a] toList (RList p []) = return p toList (RList p ms) = pullR (RList [] ms) = fmap (p ++) . toList -- Dale Jordan's library, slightly re-written -- Specialized iterator for running actions in Rand monad, to thread -- the generator. The idea is that the action returns a finite list -- of random values and iterateR lazily creates an infinite list of -- values. -- Again, the monadic type is unncessary; given for the sake of -- uniformity iterateR :: Monad m = m [a] - m (RList m a) iterateR act = return $ RList [] (repeat act) type Rand r a = State r a -- A simple example of a finite action something :: (RandomGen g) = Int - Int - Rand g [Int] something n m = sequence . replicate n . State $ randomR (m,m+9) run1 = evalState (toList = takeR 10 = (iterateR (something 2 0))) $ mkStdGen 42 -- [1,1,7,4,6,1,8,1,8,5] run2 = evalState (toList = takeR 10 = (iterateR (something 2 0) iterateR (something 3 10))) $ mkStdGen 42 -- [11,11,17,14,16,11,18,11,18,15] run3 = evalState (toList = (takeR 10 = (iterateR (something 2 0) = headR = iterateR . something 3))) $ mkStdGen 42 -- [8,5,7,2,9,2,9,6,6,10] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: Am Montag 04 Januar 2010 19:16:32 schrieb Will Ness: Daniel Fischer daniel.is.fischer at web.de writes: Am Montag 04 Januar 2010 13:25:47 schrieb Will Ness: Euler's sieve is sieve (p:ps) xs = h ++ sieve ps (t `minus` map (p*) [p,p+2..]) where (h,t) = span ( p*p) xs Not quite. That's a variant of the postponed filters, it crosses off e.g. 45 twice, once as 3*15 and once as 5*9 (okay, it has already been removed by the first, so let's say 45 appears in two lists of numbers to be removed if present). there won't be any such. whatever is removed first, is just skipped second (and third, etc). ((45:(offer 47 when demanded)) `minus` (45:(next will be 51 when demanded))) `minus` (45:(next will be 55 when demanded)) So there are two attempts to tell the generator to not output 45. To the second, it answers I already knew that, but the request is made nevertheless. yes, of course. ... There are two attempts to eliminate 45. I would say there are two requests to not have 45 in the output. I don't see any problem here. As Melissa (and yourself, I think) have shown, double hits on multiples are few and far between. It's not a problem, it just means it's not Euler's sieve, because that attempts to eliminate each composite exactly once. yes I see now. My bad. Wasn't reading that wikipedia page with enough attention to detail. It uses the modified (culled, so far) numbers to find out the next multiples to be eliminated, not just the prime itself like my code does. You solution is indeed, exponential: euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks) primes = 2:euler [3,5..] primes = 2:euler (a...@[3,5..]) 3:euler (bs@(tail as `minus` map (3*) as)) 5:euler (cs@(tail bs `minus` map (5*) bs)) There are two separate look-back pointers to /as/ in /bs/, and there are two such in /cs/, to /bs/. The book-keeping machinery explodes. Also, it uses no filters, i.e. no individual number divisibility testing. The filters refers first of all to testing an individual number to decide whether to keep it in or not. Umm, the postponed filters says keep everything until p^2, then eliminate (filter out, remove) multiples of p in the remainder, after that, pick next prime. That's precisely what the above does. It doesn't do the filtering out by divisibility testing but by minus (hence more efficiently). I would say that's a variant of the postponed filters. Filter is usually (as in Haskell's 'filter') is about testing individual elements by a predicate function. There is of course a filtering effect in two lists elts' comparison that 'minus' performs, so that's debatable. Even the PQ code performs filtering in this wider sense. Euler's sieve is never attempting to remove a number more than once, that's How's that possible? http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Euler.27s_Sieve C) The number after the previous prime is also a prime. *Multiply each number /that's left/ in the list starting from this prime by this prime and discard the products*. yes. Wasn't paying attention to that, more to the intent of it. There's of course enourmous vagueness in how exactly it is to be performed, in the unbounded case, which you uncovered here. It can't have foresight, right? But it has :) By only trying to eliminates products of the prime p currently under consideration *with numbers (= p) /which have not/ /yet been eliminated/ from the list*, it is known in advance that all these products are still in the list. missed that. When p is under consideration, the list contains (apart from the primes p) precisely the numbers whose smallest prime factor is = p. the outstanding feature of it. Unfortunately, that also makes it hard to implement efficiently. The problem is that you can't forget the primes between p and p^2, you must remember them for the removal of multiples of p later on. not just primes - all the composites not yet removed, too. So it can't even be implemented on shared mutable storage if we want to delay the removal (as we must, in unbounded case) - the composites will get removed so their multiples must actually all be produced first! The more pressing problem with that code is its linear structure of course which gets addressed by the tree-folding merge etc. Which unfortunately introduces its own space problem :( Try a different minus: xxs at (x:xs) `minus` yys at (y:ys) = case compare x y of LT - x : xs `minus` yys EQ - xs `minus` ys GT - error (trying to remove ++ show y ++ a second time) Your code is not. It is, however, much faster. I understand now. Thanks! Its performance is really horrible though. exponential, empyrically as well. It just occured to me that the accumulation list is just
Re: [Haskell-cafe] Re: FASTER primes
Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness: ... There are two attempts to eliminate 45. I would say there are two requests to not have 45 in the output. Thers are many possible ways to phrase it. I don't see any problem here. As Melissa (and yourself, I think) have shown, double hits on multiples are few and far between. It's not a problem, it just means it's not Euler's sieve, because that attempts to eliminate each composite exactly once. yes I see now. My bad. Wasn't reading that wikipedia page with enough attention to detail. It uses the modified (culled, so far) numbers to find out the next multiples to be eliminated, Minor factual error, no big deal. not just the prime itself like my code does. Which is operationally far better because it's much simpler :) You solution is indeed, exponential: euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks) primes = 2:euler [3,5..] primes = 2:euler (a...@[3,5..]) 3:euler (bs@(tail as `minus` map (3*) as)) 5:euler (cs@(tail bs `minus` map (5*) bs)) There are two separate look-back pointers to /as/ in /bs/, and there are two such in /cs/, to /bs/. The book-keeping machinery explodes. Also, it uses no filters, i.e. no individual number divisibility testing. The filters refers first of all to testing an individual number to decide whether to keep it in or not. Umm, the postponed filters says keep everything until p^2, then eliminate (filter out, remove) multiples of p in the remainder, after that, pick next prime. That's precisely what the above does. It doesn't do the filtering out by divisibility testing but by minus (hence more efficiently). I would say that's a variant of the postponed filters. Filter is usually (as in Haskell's 'filter') is about testing individual elements by a predicate function. There is of course a filtering effect in two lists elts' comparison that 'minus' performs, so that's debatable. Even the PQ code performs filtering in this wider sense. I understood the 'filters' in postponed filters in that wider sense. And I would also find it perfectly acceptable to say that the PQ code filters out the composites from the stream. Of course if you're used to using 'filter' only in the stricter sense, you wouldn't call the `minus` thing a variant of the postponed filters. not just primes - all the composites not yet removed, too. Between p and p^2, there are only primes left, fortunately. So it can't even be implemented on shared mutable storage if we want to delay the removal (as we must, in unbounded case) - Yes. And it's not nice in the bounded case either. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Re: Data.Ring -- Pre-announce
For those interested, the version of data-clist without Empty is here: http://github.com/sw17ch/data-clist/tree/noEmpty http://github.com/sw17ch/data-clist/tree/noEmpty On Tue, Jan 5, 2010 at 2:53 AM, Luke Palmer lrpal...@gmail.com wrote: On Mon, Jan 4, 2010 at 1:13 PM, Maciej Piechotka uzytkown...@gmail.com wrote: However then we lost the monoid (ok. I haven't send patch but please accept[1]) along with alternative/monad plus - which is much more popular, standard and useful then Copointed/Comonad. This point is a self-fulfilling prophecy. We don't have very much experience working with copointeds and comonads, but I don't think that makes them useless, just unfamiliar. One must never confuse what is natural with what is habitual. -- Mahatma Gandhi Luke ___ 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] lawless instances of Functor
Given fmap id = id, fmap (f . g) = fmap f . fmap g follows from the free theorem for fmap. This was published as an aside in a paper a long time back, but I forget where. -Edward Kmett On Mon, Jan 4, 2010 at 5:14 PM, Paul Brauner paul.brau...@loria.fr wrote: Hi, I'm trying to get a deep feeling of Functors (and then pointed Functors, Applicative Functors, etc.). To this end, I try to find lawless instances of Functor that satisfy one law but not the other. I've found one instance that satisfies fmap (f.g) = fmap f . fmap g but not fmap id = id: data Foo a = A | B instance Functor Foo where fmap f A = B fmap f B = B -- violates law 1 fmap id A = B -- respects law 2 fmap (f . g) A = (fmap f . fmap g) A = B fmap (f . g) B = (fmap f . fmap g) B = B But I can't come up with an example that satifies law 1 and not law 2. I'm beginning to think this isn't possible but I didn't read anything saying so, neither do I manage to prove it. I'm sure someone knows :) Paul ___ 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
[Haskell-cafe] Re: lawless instances of Functor
Dan Piponi wrote: Derek Elkins wrote: Yes, I have the same problem...Basically, I'm pretty sure the construction of that free theorem doesn't rely on any of the actual details... For a long time I've thought such a higher order free theorem must exist, and I've mentioned it to a few people, and searched hard for a paper on it, but I haven't seen an actual statement and proof. At this point, though, I haven't put much effort into proving that the free theorem holds uniformly Well I encourage you to as I've a hunch the correctly generalised theorem will be quite pretty. I'd have a go but the style of proof for these sorts of things is outside of my domain of confidence/experience. This looks relevant: Janis Voigtländer. Free Theorems Involving Type Constructor Classes. http://wwwtcs.inf.tu-dresden.de/~voigt/icfp09.pdf Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] 64-bit Bloom filters?
Hi, I've previously used Bloom filters on 32-bit Linux with some success. However, after upgrading to 64 bit, my Bloom filter applications crash or misbehave in random ways. So: is anybody successfully using Bloom filters on 64 bit computers? Although I'm not clear on why it would cause crashes (SEGV, infinite looping, etc), my prime suspect is the hashing function used. This is from C and returns a uint32, but it is imported to return a CInt, which I suspect is 64 bits. I'll look further into it, but I thought I'd check if anybody else has the same problem, and especially, a 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
[Haskell-cafe] Re: 64-bit Bloom filters?
On Tue, 2010-01-05 at 16:19 +0100, Ketil Malde wrote: Hi, I've previously used Bloom filters on 32-bit Linux with some success. However, after upgrading to 64 bit, my Bloom filter applications crash or misbehave in random ways. So: is anybody successfully using Bloom filters on 64 bit computers? Although I'm not clear on why it would cause crashes (SEGV, infinite looping, etc), my prime suspect is the hashing function used. This is from C and returns a uint32, but it is imported to return a CInt, which I suspect is 64 bits. On 64-bits Int can be either 32 or 64-bit. In theory it can be anything. It should use Data.Word.Word32 Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [Very long] (CHP?) Compressing, MD5 and big files
Hi, Sorry for the slightly delayed reply -- I didn't have time to look through all your code and understand it until just now. Your code has one (no doubt frustratingly!) small problem, which is in the deadlocking pipeline3: Maciej Piechotka wrote: pipeline3 :: CHP () pipeline3 = enrolling $ do file - oneToManyChannel' $ chanLabel File fileGZ - oneToOneChannel' $ chanLabel File GZ data_ - oneToManyChannel' $ chanLabel Data compressed - oneToManyChannel' $ chanLabel Data Compressed md5 - oneToOneChannel' $ chanLabel MD5 md5Compressed - oneToOneChannel' $ chanLabel MD5 Compressed fileGZ' - Enroll (reader file) fileData - Enroll (reader file) dataMD5 - Enroll (reader data_) dataCompress - Enroll (reader data_) compressedFile - Enroll (reader compressed) compressedMD5 - Enroll (reader compressed) liftCHP $ runParallel_ [getFiles (writer file), (forever $ readChannel fileGZ' = writeChannel (writer fileGZ) . (++.gz)) `onPoisonRethrow` (poison fileGZ' poison (writer fileGZ)), readFromFile fileData (writer data_), calculateMD5 dataMD5 (writer md5), compressCHP dataCompress (writer compressed), writeToFile (reader fileGZ) compressedFile, calculateMD5 compressedMD5 (writer md5Compressed), forever $ readChannel dataMD5 = liftIO . print readChannel compressedMD5 = liftIO . print] Problems: (CHP) Thread terminated with: thread blocked indefinitely in an STM transaction _b3, _b4, File GZ.test1.gz Where you have readChannel dataMD5 and readChannel compressedMD5 in the last few lines, you actually meant to have readChannel (reader md5) and readChannel (reader md5Compressed). Your mistake meant that the former two channels were being used more times in parallel than you had enrolled and that the latter two channels were being written to but not read from. Either of these mistakes could cause deadlock, so hence why you were getting a strange deadlock. Unfortunately, the type system didn't save you this time, because the channel types happened to be the same. It took me a while to find it, too! On a side note, it would be good to have a static check for these mistakes (using a channel in parallel unsafely, and only using one end of a channel), but the only way I found to use Haskell's type-system for this is a rather nasty type-indexed monad. I guess if you use newChannelRW and name both the results, you would get an unused variable warning if you didn't use either end of the channel. This would fix one issue, but not the other. Hope that helps, Neil. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lawless instances of Functor
On Mon, Jan 4, 2010 at 3:01 PM, Derek Elkins derek.a.elk...@gmail.com wrote: So without doing funky stuff involving bottoms and/or seq, I believe that fmap id = id implies the other functor law (in this case, not in the case of the general categorical notion of functor.) So lets play with bottoms and/or seq. data X a = X a instance Functor X where fmap f x = f `seq` case x of X a - f a fmap id x = id `seq` case x of X a - X (id a) = case x of X a - X a = id x fmap (const () . undefined) x = fmap (\a - const () (undefined a)) x = fmap (\a - ()) x = case x of X a - X () (fmap (const ()) . fmap undefined) x = fmap (const ()) (fmap undefined x) = const () `seq` case (fmap undefined x) of X a - X () = case (fmap undefined x) of X a - X ()) = case (undefined `seq` case x of X a - X (undefined a)) of X a - X () = case undefined of X a - X () = undefined ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] 64-bit Bloom filters?
On Tue, Jan 5, 2010 at 7:19 AM, Ketil Malde ketil+hask...@malde.orgketil%2bhask...@malde.org wrote: I've previously used Bloom filters on 32-bit Linux with some success. However, after upgrading to 64 bit, my Bloom filter applications crash or misbehave in random ways. I'll look into it. Do you have a simple repro? So: is anybody successfully using Bloom filters on 64 bit computers? I developed all that code on a 64-bit box, but I haven't had occasion to use it recently. Although I'm not clear on why it would cause crashes (SEGV, infinite looping, etc), my prime suspect is the hashing function used. This is from C and returns a uint32, but it is imported to return a CInt, which I suspect is 64 bits. A CInt is 32 bits on the only 64-bit architecture that anyone really uses (x86_64) :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] darcs 2.4 beta 1 release
Hi all, The darcs team would like to announce the immediate availability of darcs 2.4 beta 1. darcs 2.4 will contain many improvements and bugfixes compared to darcs 2.3.1. Highlights are the fast index-based diffing which is now used by all darcs commands, and the interactive hunk-splitting in darcs record. This beta is your chance to test-drive these improvements and make darcs even better. If you have installed the Haskell Platform or cabal-install, you can install this beta release by doing: $ cabal update $ cabal install --reinstall darcs-beta Alternatively, you can download the tarball from http://darcs.net/releases/darcs-2.3.98.1.tar.gz , and build it by hand as explained in the README file. A list of important changes since 2.3.1 is as follows (please let me know if there's something you miss!): * Use fast index-based diffing everywhere (Petr) * Interactive patch splitting (Ganesh) * An 'optimize --upgrade' option to convert to hashed format in-place (Eric) * Hunk matching (Kamil Dworakowski, tat.wright) * Progress reporting is no longer deceptive (Roman Plášil) * A 'remove --recursive' option to remove a directory tree from revision control (Roman Plášil) * A '--remote-darcs' flag for pushing to a host where darcs isn't called darcs * Many miscellaneous Windows improvements (Salvatore, Petr and others) * 'darcs send' now mentions the repository name in the email body (Joachim) * Handle files with boring names in the repository correctly (Petr) * Fix parsing of .authorspellings file (Tomáš Caitt) * Various sane new command-line option names (Florent) * Remove the '--checkpoint' option (Petr) * Use external libraries for all UTF-8 handling (Eric, Reinier) * Use the Haskell zlib package exclusively for compression (Petr) Kind Regards, the darcs release manager, Reinier Lamers 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
Re: [Haskell-cafe] Using Haskell to write dbus server
On Tue, 2010-01-05 at 09:37 -0800, John Millikin wrote: Why would you want to? Any conforming D-Bus client can connect to any conforming D-Bus server, so there's no particular advantage to having the same language on both ends of the connection. Additionally, there's a lot of fiddly low-level details (memory management, OS integration) which are difficult to implement in Haskell but relatively easy in C. The reference implementation of D-Bus has had an awful amount of work poured into making it stable and usable even in the face of external errors, such as out of memory -- replicating that work, in any language would be a pain. That isn't a rhetorical question, by the way -- I've written mostly-complete implementation of the client libraries, and intend to write a server at some point. But without a clear reason to write the server, it's just languishing on the TODO list. If you have any use for a Haskell D-Bus server which can't be served by the reference implementation, I'd be glad to hear it. Ok. I'll look on it. Maybe then I'll post the bindings (with some template haskell or similar) to hackage. The client have already established API (in terms of DBus) and is not in Haskell. Regards 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
Re: [Haskell-cafe] Using Haskell to write dbus server
There's already three client libraries: http://hackage.haskell.org/package/dbus-client http://hackage.haskell.org/package/network-dbus http://hackage.haskell.org/package/DBus Perhaps there is some confusion? The D-Bus server, or bus, is a service which allows many-to-many communication between clients. You do not need an implementation of the server in Haskell to use D-Bus in Haskell applications, and (to my knowledge) there is no API for the reference server. On Tue, Jan 5, 2010 at 10:19, Maciej Piechotka uzytkown...@gmail.com wrote: On Tue, 2010-01-05 at 09:37 -0800, John Millikin wrote: Why would you want to? Any conforming D-Bus client can connect to any conforming D-Bus server, so there's no particular advantage to having the same language on both ends of the connection. Additionally, there's a lot of fiddly low-level details (memory management, OS integration) which are difficult to implement in Haskell but relatively easy in C. The reference implementation of D-Bus has had an awful amount of work poured into making it stable and usable even in the face of external errors, such as out of memory -- replicating that work, in any language would be a pain. That isn't a rhetorical question, by the way -- I've written mostly-complete implementation of the client libraries, and intend to write a server at some point. But without a clear reason to write the server, it's just languishing on the TODO list. If you have any use for a Haskell D-Bus server which can't be served by the reference implementation, I'd be glad to hear it. Ok. I'll look on it. Maybe then I'll post the bindings (with some template haskell or similar) to hackage. The client have already established API (in terms of DBus) and is not in Haskell. Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Using Haskell to write dbus delserver/del insclient exporting objects/ins
On Tue, 2010-01-05 at 10:27 -0800, John Millikin wrote: There's already three client libraries: http://hackage.haskell.org/package/dbus-client http://hackage.haskell.org/package/network-dbus http://hackage.haskell.org/package/DBus Perhaps there is some confusion? The D-Bus server, or bus, is a service which allows many-to-many communication between clients. You do not need an implementation of the server in Haskell to use D-Bus in Haskell applications, and (to my knowledge) there is no API for the reference server. Hmm. Yes. By server I mean client server not the dbus daemon. I.e. the side which exports the objects. I.e. for me (my terminology is network-oriented[1]): - dbus server: something exporting objects. Eg. devkit, hal, nm - dbus client: something connecting to server/listining for signals etc. - dbus daemon: something running in background started by /etc/init.d/dbus start with session - dbus bus: namespace in which servers and clients operates. Most popular as system and session buses (now I know there is one-to-one correspondence with daemons) I belive that last time I read dbus-client documentation was 'client'-oriented. Regards PS. I hope no ASCII ribbonner will kill me for using HTML in subject [1] Especially that there is xinetd daemon which runs ssh/ftp/... servers 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
Re: [Haskell-cafe] Using Haskell to write dbus delserver/del insclient exporting objects/ins
Ah, the issue is one of terminology.
To me, server is the central bus, and client is any application
which connects to the bus. Clients may send or receive any support
message type.
D-Bus doesn't actually have any mechanism for exporting objects;
this is an abstraction, layered over the asynchronous message
protocol. Any client library can export objects. Here is an example
of using dbus-core and dbus-client to export some objects /hello and
/world on the org.test.exporting name. It includes name
registration, receiving method calls, sending replies, and sending
errors:
---
{-# LANGUAGE OverloadedStrings #-}
import DBus.Bus
import DBus.Client
import DBus.Types
import DBus.Constants
import qualified Data.Map as Map
import Control.Concurrent.MVar
a x = LocalObject $ Map.fromList
[ (mkInterfaceName' test.iface_1, Interface $ Map.fromList
[ (mkMemberName' Foo, onFoo a x)
, (mkMemberName' Bar, onBar a x)
])
]
onFoo :: String - String - Member
onFoo x y = Method (mkSignature' ) (mkSignature' s) $ \call - do
putStrLn $ Foo ++ x ++ ++ y
replyReturn call [toVariant $ Foo ++ x ++ ++ y]
onBar :: String - String - Member
onBar x y = Method (mkSignature' ) (mkSignature' s) $ \call - do
putStrLn $ Bar ++ x ++ ++ y
replyError call errorFailed [toVariant $ Bar ++ x ++ ++ y]
main = do
client - mkClient = getSessionBus
requestName client (mkBusName' org.test.exporting) []
export client (mkObjectPath' /hello) (a hello)
export client (mkObjectPath' /world) (a world)
mvar - newEmptyMVar
takeMVar mvar
---
On Tue, Jan 5, 2010 at 10:43, Maciej Piechotka uzytkown...@gmail.com wrote:
On Tue, 2010-01-05 at 10:27 -0800, John Millikin wrote:
There's already three client libraries:
http://hackage.haskell.org/package/dbus-client
http://hackage.haskell.org/package/network-dbus
http://hackage.haskell.org/package/DBus
Perhaps there is some confusion? The D-Bus server, or bus, is a
service which allows many-to-many communication between clients. You
do not need an implementation of the server in Haskell to use D-Bus in
Haskell applications, and (to my knowledge) there is no API for the
reference server.
Hmm. Yes. By server I mean client server not the dbus daemon. I.e. the
side which exports the objects.
I.e. for me (my terminology is network-oriented[1]):
- dbus server: something exporting objects. Eg. devkit, hal, nm
- dbus client: something connecting to server/listining for signals etc.
- dbus daemon: something running in background started
by /etc/init.d/dbus start with session
- dbus bus: namespace in which servers and clients operates. Most
popular as system and session buses (now I know there is one-to-one
correspondence with daemons)
I belive that last time I read dbus-client documentation was
'client'-oriented.
Regards
PS. I hope no ASCII ribbonner will kill me for using HTML in subject
[1] Especially that there is xinetd daemon which runs ssh/ftp/...
servers
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [darcs-users] Iteratees, streams, and mmap
Jason Dagit wrote: Heinrich Apfelmus wrote: How about tracking the requirement of bounded in the type system? In particular, I'm thinking of a type class class NFData a = Small a where the idea is that all types that can be stored in constant space are members of this class. For example, we have instance Small () instance Small Int instance Small Char instance (Small a, Small b) = Small (a,b) instance (Small a, Small b) = Small (Either a b) but recursive types like [a] or String are not allowed to be members. On second (and late) thought, this idea is not as good as it sounds and needs more thought. The thing is if A is an instance of Small , we are not guaranteed that a value x :: A will take little memory, we are only guaranteed that its *normal form* takes little memory. Now, due to pervasive lazy evaluation, it's quite impossible to track whether a value is in normal form in the type system. It seems like we also need: instance Small (IO ()) Which is not necessarily bounded due to things like IORefs. [...] In the light of the above, I think this is related to the issue that we can't evaluate IO () to normal form at all, i.e. there is no deepSeq for values of type IO () . I could also see us needing this: bracketSmall :: (Small c) = IO a - (a - IO b) - (a - IO c) - IO c I'm not sure if b needs to be Small, since it's just supposed to be the return value of the deallocation step. Thanks to parametricity, we know that b is thrown away, it can never appear in the result type c . It seems that having functions like bracketSmall are necessary if we want to hide the stream itself from being exposed outside of the traversal function. For example, your foldlSmall doesn't leak, but something at the same level of scope as it could leak the list. Yep, though this does have the unfortunate (?) consequence that we cannot use bracketSmall to return any large values anymore, even if they do not leak the stream. (A notion which literally gets muddier in the course of the program because it might be that c does not leak the vanilla stream, but for example every character of it.) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: About Atom
On Tue, Jan 5, 2010 at 7:05 PM, CK Kashyap ck_kash...@yahoo.com wrote: Hi Tom, Happy new year :) I was wondering if I could use Atom for the purpose of an x86 operating system generator? Hi Kashyap, Ironically Atom was intended to eliminate the need for operating systems -- at least on small embedded projects. But yes, maybe it could be use develop an OS. (I've never written one, so I'm speaking way out of my comfort zone.) I've explored Minix and wanted to get rid of all the noise introduced by C and focus on the logic. I am sorry, I have not really explored Atom sufficiently but I am just too eager to know :) ... I have installed Atom using cabal - I was just going through Example.hs ... One thing I noticed is that the logic to calculate gcd was not clear from the implementation (Haskell side that is) ... Perhaps I am not reading it with the right perspective - can you elaborate it? Also, why exactly did you name the whole thing Atom? Because an Atom design is composed of a bunch of small atomic operations. Take the GCD example: -- A rule to modify A. If a b then set a = a - b. atom a_minus_b $ do cond $ value a . value b a == value a - value b -- A rule to modify B. If b a then set b = b - a. atom b_minus_a $ do cond $ value b . value a b == value b - value a These independent rules periodically wake up and check their guard conditions (cond). If the guard condition is true, it performs the action atomically, in isolation from everything else in the system. In the case of the GCD example, the algorithm converges when a == b, at which point both the a_minus_b and b_minus_a rules are disabled. -Tom Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] unexpected behavior / bug in try . System.FilePath.Find.findWithHandler
say you want to execute a find function, but abort the computation if
it hits any snags, such as an unreadable directory (eg chmod -R a-r
dir).
Currently try . System.FilePath.Find.findWithHandler
will return an exception wrapped in Right, which seems Wrong. For sure
it will just get ignored if wrapped in an ErrorT computation and I
suspect this could lead to other glitchy/unexpected behavior when used
in sysadmin scripts.
You do get the expected exception wrapped in Left for certain errors
(such as a missing directory), which adds to the confusion.
Probable fix: you get the expected behavior if you remove
unsafeInterleaveIO from findWithHandler. Does this seem like a
reasonable thing to suggest to librar...@haskell?
Hacky fix: I haven't actually done this, but I suppose you could trap
stdout or stderr, since the exception does get printed although it's
not reflected in the result type of the computation.
demo of problem:
import qualified System.FilePath.Find as F
import System.FilePath.Find
import System.IO.Error
abort path err = fail $ path ++ , ++ (show err)
prot = /home/thartman/protected -- a protected (unreadable) dir
{-
want result =
Left user error (/home/thartman/protected , user error
(/home/thartman/protected , /home/thartman/protected:
getDirectoryContents: permission denied (Permission denied)))
but get result
Right *** Exception: user error (/home/thartman/protected ,
/home/thartman/protected: getDirectoryContents: permission denied
(Permission denied))
which means, for example, you would miss the error if you wrapped this
in an ErrorT
there is probably a workaround from reading stderr, since it does get
printed out, but this is awkward compared to just catching the error
the right way
and certainly feels like unexpected behavior
Possible fix: you get the expected behavior if you remove
unsafeInterleaveIO from System.FilePath.Find.findWithHandlers
don't know why this fixes the problem, I was just messing around
I don't know if this breaks anything else, but I was unable to find
any breakage when I did a simple test on an unprotected directory
What is the gain from unsafeInterleaveIO, and can it be nixed?
-}
tprot = try . findWithHandler abort (return True) (return True) $ prot
tunprot = return . either (error . show) (length) = ( try $
findWithHandler abort (return True) (return True) unprot )
unprot = /home/thartman/unprot
--
Need somewhere to put your code? http://patch-tag.com
Want to build a webapp? http://happstack.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: Am Dienstag 05 Januar 2010 14:49:58 schrieb Will Ness: ... There are two attempts to eliminate 45. I would say there are two requests to not have 45 in the output. Thers are many possible ways to phrase it. You solution is indeed, exponential: euler ks@(p:rs) = p : euler (rs `minus` map (*p) ks) primes = 2:euler [3,5..] primes = 2:euler (a...@[3,5..]) 3:euler (bs@(tail as `minus` map (3*) as)) 5:euler (cs@(tail bs `minus` map (5*) bs)) Re-write: euler s = head s:euler (tail s `minus` map(head s*) s) primes = euler [2..] primes = euler $ rollFrom [2] 1 = 2:euler ( rollFrom [3] 1 `minus` map(2*) (rollFrom [2] 1)) ) rollFrom [3,4] 2 `minus` rollFrom [4] 2 -- rollFrom [3] 2 -- = 2:3:euler (rollFrom [5] 2 `minus` map(3*) (rollFrom [3] 2)) rollFrom [5,7,9] 6 `minus` rollFrom [9] 6 -- rollFrom [5,7] 6 -- = 2:3:5:euler (rollFrom [7,11] 6 `minus` rollFrom [25,35] 30) [7,11, 13,17, 19,23, 25,29, 31,35] 30 -- rollFrom [7,11,13,17,19,23,29,31] 30 -- = . where rollOnce (x:xs) by = (x, tail xs ++ [x+by]) rollFrom xs by = concat $ iterate (map (+ by)) (xs) multRoll xs@(x:_) by p = takeWhile ( (x+p*by)) $ rollFrom xs by so, reifying, we get data Roll a = Roll [a] a rollOnce (Roll (x:xs) by) = (x,Roll (xs ++ [x+by]) by) rollFrom (Roll xs by) = concat $ iterate (map (+ by)) (xs) multRoll r@(Roll (x:_) by) p = Roll (takeWhile ( (x+p*by)) $ rollFrom r) (by*p) primes = euler $ Roll [2] 1 euler r@(Roll xs _) = x:euler (Roll (mxs `minus` map (x*) xs) mby) where (x,r') = rollOnce r (Roll mxs mby) = multRoll r' x There's much extra primes pre-calculated inside the Roll, of course (upto p^2 in fact, for p = primes!!n ), so this needs to be somehow tapped into, by writing a specialized nthPrime n = to be called instead of (!! n), and also primesUpTo n = This calculated primes !! 1000 == 7927 in 3 seconds for me, interpreted, on my old slowish laptop. It's supposed to have all the primes upto 7927^2 = 62837329 inside the Roll (if I'm not mistaken - or is it?). That's about 3.72 millionth prime, according to WolframAlpha. (nah, it cant be that much). But it is surely not horribly slow. Is this, in fact, the wheels' spiral? not just primes - all the composites not yet removed, too. Between p and p^2, there are only primes left, fortunately. but (map (*p) ks) needs access to the original, non-culled numbers - primes, composites and all. (?) So it can't even be implemented on shared mutable storage if we want to delay the removal (as we must, in unbounded case) - Yes. And it's not nice in the bounded case either. ___ Haskell-Cafe mailing list Haskell-Cafe at 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] lawless instances of Functor
Brent Yorgey wrote: On Mon, Jan 04, 2010 at 11:49:33PM +0100, Steffen Schuldenzucker wrote: [...] As others have pointed out, this doesn't typecheck; but what it DOES show is that if we had a type class class Endofunctor a where efmap :: (a - a) - f a - f a then it would be possible to write an instance for which efmap id = id but efmap (f . g) /= efmap f . efmap g. The difference is that with the normal Functor class, once you have applied your function f :: a - b to get a b, you can't do anything else with it, since you don't know what b is. With the Endofunctor class, once you have applied f :: a - a, you CAN do something with the result: namely, apply f again. Oops. Yeah, sorry, it's been ... late and stuff... Steffen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] GHC 6.12.1 FreeBSD binaries
Does anyone know what the status is of the FreeBSD binaries for the most recent GHC release? In particular, I'm looking or FreeBSD 7.2 binaries. I tried building from source, but it says I don't have iconv library. I'm not enough of a FreeBSD guy to track this one down. Thanks, Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: So we must make sure that the list of composites that primes' consumes is not the same as that which primes'' consumes. yes that is what I had done too. Duplicated everything. Turns out, it works exactly as you told it would when using the compiler switch, -fno-cse, thanks! I used the switch; it didn't help at all. The only thing I can see is wrong. I didn't. When I did, it worked. Unfortunately it grows, as you've said - 23MB for 2 mln. :| And I've found out why. Change the definition of tfold to tfold f (a: ~(b: ~(c:xs))) = (a `f` (b `f` c)) `f` tfold f xs and memory stays low (things are going much slower, though). (forced by gmane poster to delete unusually many of your comments today...) Interesting... As for the structure, I chose it trying to minimize the estimated average cost of a composite production, Sum (1/p)*depth. You can make a compromise by using the above tfold (which is no longer a tree-fold) and grouping (and merging) the multiples in a slower-growing manner, ... memory still grows, but much slower, in my tests, due to the much smaller GC time, it's a bit faster than the version with the original tfold. Great! :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes
Daniel Fischer daniel.is.fischer at web.de writes: Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer: memory still grows, but much slower, in my tests, due to the much smaller GC time, it's a bit faster than the version with the original tfold. Not for larger inputs (but not so large that the tree-fold dies OOM). Fix rfold: rfold f [x] = x rfold f xs = rfold f (pairwise f xs) and it's faster also for those. Niiice This is just great! :) I tried a two-step feed BTW (that's three separate sets of lists) , with the original structure. It ran with same speed as your new version (10..20% faster) but with the memory of the previous one :) (80M for 8 mil primes vs the new one's 10M). But your new structure is just great! I hoped there is something better, that's why I posted it here in the first place. 'pairwise' puts odd leafs higher on the right. It might be better if it was so on the left, for the frequency of production is higher. Thanks a lot for your comments! ___ Haskell-Cafe mailing list Haskell-Cafe at 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
[Haskell-cafe] ANN: uuid-0.1.2
Antione and I are please to announce the release of uuid-0.1.2. CHANGES: - added functions toByteString and fromByteString - added 'nil' UUID - added unit tests and benchmarks, built when configured -ftest - major speed up of to/from functions (as well as in general) - added version-3 generation (deterministic based on MD5) - major changes to internal representation - now uses four strict Word32 values - internal ByteSource classes for easy construction (see Builder.hs) - Storable instance now stores in memory as system libraries in C do: 16 bytes derived from the network order of the fields, no matter what the host native endianess is. - fixed bugs in V1 time and clock stepping, and V1 generated values - builds cleanly under GHC's -Wall - added CHANGES file String conversions were sped up 4x to 7x! - Mark Mark Lentczner (MtnViewMark) http://www.ozonehouse.com/mark/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Seven ways to store 16 bytes
In preparing the speed ups in uuid-0.1.2, I investigated various ways to store 16 bytes of data in a Haskell object. Surprisingly, storing as 4 Word32 values in a standard data type worked best for that application. I've extracted out the testing work for that and put it here: http://bitbucket.org/mtnviewmark/haskell-playground/src/tip/16bytes/ There you can find the code that tests storing 16 bytes in various ways: import qualified Data.Array as A import qualified Data.Array.Unboxed as U import qualified Data.Array.Vector as V import qualified Data.ByteStringas B data InBytes = BY !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 deriving (Eq, Ord) data InWords = WO !Word32 !Word32 !Word32 !Word32 deriving (Eq, Ord) data InList = LI [Word8] deriving (Eq, Ord) data InByteString = BS B.ByteString deriving (Eq, Ord) data InArray = AR (A.Array Int Word8) deriving (Eq, Ord) data InUArray = UA (U.UArray Int Word8) deriving (Eq, Ord) data InVector = VE (V.UArr Word8) deriving (Eq) Depending on operations will be needed most, different storage methods do best. Enjoy! - Mark Mark Lentczner (MtnViewMark) http://www.ozonehouse.com/mark/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: uuid-0.1.2
2010/1/5 Mark Lentczner ma...@glyphic.com: Antione and I are please to announce the release of uuid-0.1.2. Thanks for doing the heavy lifting on this one, Mark. Antoine ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Interpreting profiling results
On Mon, Jan 4, 2010 at 10:05 AM, Daniel Fischer
daniel.is.fisc...@web.de wrote:
Am Montag 04 Januar 2010 02:17:06 schrieb Patrick LeBoutillier:
Hi,
This question didn't get any replies on the beginners list, I thought
I'd try it here...
Sorry, been occupied with other things. I already took a look, but hadn't
anything conclusive enough to reply yet.
No sweat... I didn't mean to be pushy :)
Thanks a lot for all the pointers, they have speeded up my code a lot.
Patrick
I've written (and improved using other solutions I've found on the
net) a simple sudoku solver which I'm trying to profile. Here is the
code:
import Array
Better
import Data.Array.Unboxed
*much* faster
import List (transpose, nub, (\\))
import Data.List
data Sudoku = Sudoku { unit :: Int, cells :: Array (Int, Int) Int,
cells :: UArray (Int,Int) Int
holes :: [(Int, Int)] }
cell :: Sudoku - (Int, Int) - Int
cell s i = (cells s) ! i
instance Read Sudoku where
readsPrec _ s = [(Sudoku unit cells holes, )]
where unit = length . words . head . lines $ s
cells = listArray ((1, 1), (unit, unit)) (map read . words $ s)
holes = [ c | c - indices cells, (cells ! c) == 0]
instance Show Sudoku where
show s = unlines [unwords [show $ cell s (x,y) | x - [1 .. unit s]]
| y - [1 .. unit s]]
genNums :: Sudoku - (Int, Int) - [Int]
genNums s c@(i,j) = ([1 .. u] \\) . nub $ used
where
nub isn't nice. It's quadratic in the length of the list. Use e.g.
map head . group . sort
or
Data.[Int]Set.toList . Data.[Int]Set.fromList
if the type is in Ord (and you don't need the distinct elements in the order
they come in). That gives an O(n*log n) nub with a sorted result.
And (\\) isn't particularly fast either (O(m*n), where m and n are the
lengths of the lists). If you use one of the above instead of nub, you can
use the O(min m n) 'minus' for sorted lists:
xxs@(x:xs) `minus` yys@(y:ys)
| x y = x : xs `minus` yys
| x == y = xs `minus` ys
| otherwise = xxs `minus` ys
xs `minus` _ = xs
Here, you can do better:
genNums s c@(i,j) = nums
where
nums = [n | n - [1 .. u], arr!n]
arr :: [U]Array Int Bool
arr = accumArray (\_ _ - False) True (0,u) used
used = (row s u i j) ++ (col s u i j) ++ (square s sq u i j)
u = unit s
Not good to calculate sq here. You'll use it many times, calculate once and
store it in s.
sq = truncate . sqrt . fromIntegral $ u
row s u i j = [cell s (i, y) | y - [1 .. u]]
col s u i j = [cell s (x, j) | x - [1 .. u]]
square s sq u i j = [cell s (x, y) | y - [1 .. u], x - [1 .. u], f x i,
f
y j] where f a b = div (a-1) sq == div (b-1) sq
Test for f y j before you generate x to skip early.
square s sq u i j = [cell s (ni+x,nj+y) | x - [1 .. sq], y - [1 .. sq]]
where
qi = (i-1) `div` sq
qj = (j-1) `div` sq
ni = qi*sq
nj = qj*sq
solve :: Sudoku - [Sudoku]
solve s =
case holes s of
[] - [s]
(h:hs) - do
n - genNums s h
let s' = Sudoku (unit s) ((cells s) // [(h, n)]) hs
solve s'
main = print . head . solve . read = getContents
When I compile as such:
$ ghc -O2 --make Sudoku.hs -prof -auto-all -caf-all -fforce-recomp
and run it on the following puzzle:
0 2 3 4
3 4 1 0
2 1 4 0
0 3 2 1
I get the following profiling report:
Fri Jan 1 10:34 2010 Time and Allocation Profiling Report (Final)
Sudoku +RTS -p -RTS
total time = 0.00 secs (0 ticks @ 20 ms)
That means the report is basically useless. Not entirely, because the
allocation figures may already contain useful information. Run on a 9x9
puzzle (a not too hard one, but not trivial either).
Also, run the profiling with -P instead of -p, you'll get more info about
time and allocation then.
total alloc = 165,728 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
CAF GHC.Handle 0.0 10.7
CAF Text.Read.Lex 0.0 2.1
CAF GHC.Read 0.0 1.2
square Main 0.0 2.8
solve Main 0.0 1.3
show_aVx Main 0.0 3.7
readsPrec_aYF Main 0.0 60.6
main Main 0.0 9.6
genNums Main 0.0 5.0
cell Main 0.0 1.2
individual inherited
COST CENTRE MODULE
no. entries %time %alloc %time %alloc
MAIN MAIN
1 0 0.0 0.3 0.0 100.0
main Main
186 1 0.0 9.6 0.0 85.6
show_aVx
Re: [Haskell-cafe] Seven ways to store 16 bytes
On Tue, Jan 05, 2010 at 04:06:09PM -0800, Mark Lentczner wrote:
In preparing the speed ups in uuid-0.1.2, I investigated
various ways to store 16 bytes of data in a Haskell object.
Surprisingly, storing as 4 Word32 values in a standard data
type worked best for that application.
However, on an Core 2 Duo in x86-64 mode with GHC 6.10, 2 Word64
values wins over 4 Word32 values. Attached is the modified
source code. Here is the summary between them
equal-itself/words 76.41 ns
equal-itself/words6464.52 ns
equal-same/words79.64 ns
equal-same/words64 67.85 ns
equal-differ/words 66.11 ns
equal-differ/words6462.79 ns
compare-same/words 80.59 ns
compare-same/words6468.68 ns
compare-differ/words67.14 ns
compare-differ/words64 64.22 ns
toList-and-sum/words 991.32 ns
toList-and-sum/words64 839.45 ns
map-and-sum/words1.04 us
map-and-sum/words64 1.12 us
fold-and-sum/words 882.88 ns
fold-and-sum/words64 755.98 ns
fromList-and-eq/words 740.41 ns
fromList-and-eq/words64749.07 ns
build-and-eq/words 484.54 ns
build-and-eq/words64 447.81 ns
unfold-and-eq/words577.12 ns
unfold-and-eq/words64 541.46 ns
Cheers,
--
Felipe.
{-# LANGUAGE RankNTypes #-}
{-
This program benchmarks several different ways to store 16 bytes in type.
-}
import Criterion.Main
import Data.Bits
import Data.List
import Data.Maybe
import Data.Word
import qualified Data.Array as A
import qualified Data.Array.Unboxed as U
import qualified Data.Array.Vector as V
import qualified Data.ByteStringas B
data InBytes = BY !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8
!Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8
deriving (Eq, Ord)
data InWords = WO !Word32 !Word32 !Word32 !Word32
deriving (Eq, Ord)
data InWords64 = WO64 !Word64 !Word64
deriving (Eq, Ord)
data InList = LI [Word8] deriving (Eq, Ord)
data InByteString = BS B.ByteString deriving (Eq, Ord)
data InArray = AR (A.Array Int Word8) deriving (Eq, Ord)
data InUArray = UA (U.UArray Int Word8) deriving (Eq, Ord)
data InVector = VE (V.UArr Word8) deriving (Eq)
instance Ord InVector where
compare (VE va) (VE vb) = V.foldlU lexo EQ $ V.zipU va vb
where lexo EQ (a V.:*: b) = compare a b
lexo r _ = r
class TestSubject d where
toList :: d - [Word8]
fromList:: [Word8] - Maybe d
mapBytes:: (Word8 - a) - d - [a]
foldBytes :: (a - Word8 - a) - a - d - a
unfoldBytes :: (a - Maybe (Word8, a)) - a - Maybe d
build :: Word8 - Word8 - Word8 - Word8
- Word8 - Word8 - Word8 - Word8
- Word8 - Word8 - Word8 - Word8
- Word8 - Word8 - Word8 - Word8 - d
build b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf =
d [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf]
where d = fromJust . fromList
instance TestSubject InBytes where
toList (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf) =
[b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf]
fromList [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf] =
Just $ BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
fromList _ = Nothing
mapBytes f (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf) =
[f b0, f b1, f b2, f b3, f b4, f b5, f b6, f b7,
f b8, f b9, f ba, f bb, f bc, f bd, f be, f bf]
foldBytes f z (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf) =
f' bf $ f' be $ f' bd $ f' bc $ f' bb $ f' ba $ f' b9 $ f' b8 $
f' b7 $ f' b6 $ f' b5 $ f' b4 $ f' b3 $ f' b2 $ f' b1 $ f' b0 $ z
where f' = flip f
unfoldBytes f z = do
(b0, a0) - f z
(b1, a1) - f a0
(b2, a2) - f a1
(b3, a3) - f a2
(b4, a4) - f a3
(b5, a5) - f a4
(b6, a6) - f a5
(b7, a7) - f a6
(b8, a8) - f a7
(b9, a9) - f a8
(ba, aa) - f a9
(bb, ab) - f aa
(bc, ac) - f ab
(bd, ad) - f ac
(be, ae) - f ad
(bf,_af) - f ae
return (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf)
build = BY
instance TestSubject InWords where
toList (WO w0 w1 w2 w3) =
[byte 3 w0, byte 2 w0, byte 1 w0, byte 0 w0,
byte 3 w1, byte 2 w1, byte 1 w1, byte 0 w1,
byte 3 w2, byte 2 w2, byte 1 w2, byte 0 w2,
byte 3 w3, byte 2 w3, byte 1 w3, byte 0 w3]
fromList [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf] =
Just $ build b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
Re: [Haskell-cafe] Seven ways to store 16 bytes
2010/1/5 Mark Lentczner ma...@glyphic.com There you can find the code that tests storing 16 bytes in various ways: data InWords = WO !Word32 !Word32 !Word32 !Word32 deriving (Eq, Ord) data InList = LI [Word8] deriving (Eq, Ord) data InByteString = BS B.ByteString deriving (Eq, Ord) data InArray = AR (A.Array Int Word8) deriving (Eq, Ord) data InUArray = UA (U.UArray Int Word8) deriving (Eq, Ord) data InVector = VE (V.UArr Word8) deriving (Eq) You've got an extra level of indirection there due to the use of data instead of newtype, so you're paying an additional boxing penalty for everything except your first case. Are you compiling with -funbox-strict-fields? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Seven ways to store 16 bytes
On Tue, Jan 05, 2010 at 04:40:55PM -0800, Bryan O'Sullivan wrote:
You've got an extra level of indirection there due to the use of data
instead of newtype, so you're paying an additional boxing penalty for
everything except your first case. Are you compiling with
-funbox-strict-fields?
I've changed those data's to newtype's but using words still
seems better, unless mapping and folding over bytes is more
important. In that case maybe storing the bytes separately might
be better. Maybe a more complex/realistic benchmark?
I've also rerun the benchmark in a x86-32 chroot. In this
environment Word32 seems to win over Word64. But, who cares
about 32 bits anyway? ;)
I'm attaching the source code and the summary results.
Everything was compiled with 'ghc -fforce-recomp -O3'.
--
Felipe.
{-# LANGUAGE RankNTypes #-}
{-
This program benchmarks several different ways to store 16 bytes in type.
-}
import Criterion.Main
import System.IO (hSetBuffering, BufferMode(..), stdout)
import Data.Bits
import Data.List
import Data.Maybe
import Data.Word
import qualified Data.Array as A
import qualified Data.Array.Unboxed as U
import qualified Data.Array.Vector as V
import qualified Data.ByteStringas B
data InBytes = BY !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8
!Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8 !Word8
deriving (Eq, Ord)
data InWords = WO !Word32 !Word32 !Word32 !Word32
deriving (Eq, Ord)
data InWords64 = WO64 !Word64 !Word64
deriving (Eq, Ord)
newtype InList = LI [Word8] deriving (Eq, Ord)
newtype InByteString = BS B.ByteString deriving (Eq, Ord)
newtype InArray = AR (A.Array Int Word8) deriving (Eq, Ord)
newtype InUArray = UA (U.UArray Int Word8) deriving (Eq, Ord)
newtype InVector = VE (V.UArr Word8) deriving (Eq)
instance Ord InVector where
compare (VE va) (VE vb) = V.foldlU lexo EQ $ V.zipU va vb
where lexo EQ (a V.:*: b) = compare a b
lexo r _ = r
class TestSubject d where
toList :: d - [Word8]
fromList:: [Word8] - Maybe d
mapBytes:: (Word8 - a) - d - [a]
foldBytes :: (a - Word8 - a) - a - d - a
unfoldBytes :: (a - Maybe (Word8, a)) - a - Maybe d
build :: Word8 - Word8 - Word8 - Word8
- Word8 - Word8 - Word8 - Word8
- Word8 - Word8 - Word8 - Word8
- Word8 - Word8 - Word8 - Word8 - d
build b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf =
d [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf]
where d = fromJust . fromList
instance TestSubject InBytes where
toList (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf) =
[b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf]
fromList [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf] =
Just $ BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
fromList _ = Nothing
mapBytes f (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf) =
[f b0, f b1, f b2, f b3, f b4, f b5, f b6, f b7,
f b8, f b9, f ba, f bb, f bc, f bd, f be, f bf]
foldBytes f z (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf) =
f' bf $ f' be $ f' bd $ f' bc $ f' bb $ f' ba $ f' b9 $ f' b8 $
f' b7 $ f' b6 $ f' b5 $ f' b4 $ f' b3 $ f' b2 $ f' b1 $ f' b0 $ z
where f' = flip f
unfoldBytes f z = do
(b0, a0) - f z
(b1, a1) - f a0
(b2, a2) - f a1
(b3, a3) - f a2
(b4, a4) - f a3
(b5, a5) - f a4
(b6, a6) - f a5
(b7, a7) - f a6
(b8, a8) - f a7
(b9, a9) - f a8
(ba, aa) - f a9
(bb, ab) - f aa
(bc, ac) - f ab
(bd, ad) - f ac
(be, ae) - f ad
(bf,_af) - f ae
return (BY b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf)
build = BY
instance TestSubject InWords where
toList (WO w0 w1 w2 w3) =
[byte 3 w0, byte 2 w0, byte 1 w0, byte 0 w0,
byte 3 w1, byte 2 w1, byte 1 w1, byte 0 w1,
byte 3 w2, byte 2 w2, byte 1 w2, byte 0 w2,
byte 3 w3, byte 2 w3, byte 1 w3, byte 0 w3]
fromList [b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, ba, bb, bc, bd, be, bf] =
Just $ build b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
fromList _ = Nothing
mapBytes f (WO w0 w1 w2 w3) =
[f $ byte 3 w0, f $ byte 2 w0, f $ byte 1 w0, f $ byte 0 w0,
f $ byte 3 w1, f $ byte 2 w1, f $ byte 1 w1, f $ byte 0 w1,
f $ byte 3 w2, f $ byte 2 w2, f $ byte 1 w2, f $ byte 0 w2,
f $ byte 3 w3, f $ byte 2 w3, f $ byte 1 w3, f $ byte 0 w3]
foldBytes f z (WO w0 w1 w2 w3) =
f' (byte 3 w0) $ f' (byte 2 w0) $ f' (byte 1 w0) $ f' (byte 0 w0) $
f' (byte 3 w1) $ f' (byte 2 w1) $ f' (byte 1 w1) $ f' (byte 0 w1) $
f' (byte 3 w2) $ f' (byte 2 w2) $ f' (byte 1 w2) $ f' (byte 0 w2) $
f' (byte 3 w3) $ f' (byte 2 w3) $ f'
Re: [Haskell-cafe] Re: FASTER primes
Am Mittwoch 06 Januar 2010 00:09:07 schrieb Will Ness: Daniel Fischer daniel.is.fischer at web.de writes: Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer: memory still grows, but much slower, in my tests, due to the much smaller GC time, it's a bit faster than the version with the original tfold. Not for larger inputs (but not so large that the tree-fold dies OOM). Fix rfold: rfold f [x] = x rfold f xs = rfold f (pairwise f xs) and it's faster also for those. Niiice This is just great! :) I tried a two-step feed BTW (that's three separate sets of lists) , with the original structure. It ran with same speed as your new version (10..20% faster) but with the memory of the previous one :) (80M for 8 mil primes vs the new one's 10M). The memory is almost completely due to the tree-merging of the multiples for the fastest runner. While it produces faster than flat merging, the exponential growth of the trees makes a bad memory citizen. With the nwise and rfold, a two-step (or even three-step) feeding doesn't gain nearly as much (I found about 1% speedup). But your new structure is just great! I hoped there is something better, that's why I posted it here in the first place. I have two more goodies :) 1. now that the trees don't grow so fast, don't use lazy patterns in the definition of tfold: tfold f (a:b:c:xs) = (a `f` (b `f` c)) `f` tfold f xs gains something like 6-7% here (and uses a little less memory). 2. Now we have a big wheel, 5760 differences per period. Then dropping a few thousand elements from the wheel after calculating how many in rollFrom is slow: rollFrom n = go ((n-17) `rem` 30030) wheel13 where go r xxs@(x:xs) | r x = roll n xxs | otherwise = go (r-x) xs gains another couple of percents for large targets (~1% for the 10M prime, ~2% for 20M, I expect that to stay in th region of 1.5-3% for larger targets). 'pairwise' puts odd leafs higher on the right. It might be better if it was so on the left, for the frequency of production is higher. Maybe. But how would you do it? I tried passing the length to rfold, so when there was an odd numberof trees in the list, it would move the first out of the recursion. Any possible gains in production have been more than eaten up by the control code (not a big difference, but it was there). Thanks a lot for your comments! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
