Re: [Haskell-cafe] Style and a problem
I should've mentioned that the maximum number in such a list is n. That's
why it stuck me as 'a bit' inexpensive.
\/\/
On Fri, Sep 10, 2010 at 5:02 AM, Richard O'Keefe o...@cs.otago.ac.nz wrote:
On Sep 10, 2010, at 8:55 AM, Wanas wrote:
Hey all,
So I have a two part question (I'm new to haskell, so you can throw all
your mugs at me).
a) I want to write a function that generates lists of lists of size $n$.
All having the property that sum lst = sum [1..n].
a-1) After that, I want to remove all permutations. My idea of doing this
is to get all lists from the first function and create a new list with the
property that if sorted list A is not in the list, add it.
It's not completely clear to me what you want.
Here's my take on it:
S0 = {L | L is a list of positive integers and sum L = n}
L1 ~~ L2 iff L2 is a permutation of L1
You want to enumerate S0/~~.
Staring at this for a bit, what you want is
ENUMERATING THE PARTITIONS OF AN INTEGER.
Look this up in almost any combinatorics book and you will find an
algorithm that you can adapt. There's stuff in Knuth, AOCP, Vol 4,
for example. A good reference is The Theory of Partitions, by
G. E. Andrews, Cambridge University Press, 1998.
Rung-Bin Lin has reported in Efficient Data Structures for Storing
the Partitions of an Integer on a data structure for representing
all the partitions of an integer n in O(n**2) space, taking O(n**2)
time to construct it, so a list of lists might not be the best way
to do it in Haskell.
What you want to do is to generate the partitions in a canonical
order with no duplicates in the first place. Something along these
lines:
the partiions of n are
the partitions of n into pieces no bigger than n with [] appended.
the partitions of n into pieces no bigger than k with xx appended are
the partitions of n-k into pieces no bigger than k with k::xx appended
followed by
the partitions of n into pieces no bigger than k-1 with xx appended
*with* some termination clauses which I haven't shown.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style and a problem
On Fri, Sep 10, 2010 at 1:06 AM, Nils Schweinsberg m...@n-sch.de wrote: Something like this? import Data.List newList :: Int - [[Int]] newList n = myNub [ l | l - undefined -- not really sure how you want -- to generate these lists :) , sum l == sum [1..n] ] myNub :: (Ord a) = [[a]] - [[a]] myNub = nubBy (\a b - sort a == sort b) - Nils So I've checked out this code, and it doesn't compile on ghci. My version, without the undefined portion is(which still doesn't work): import Data.List newList :: Int - [[Int]] newList n = myNub [ l | l - [1..n], sum l == sum [1..n] ] myNub :: (Ord a) = [[a]] - [[a]] myNub = nubBy (\a b - sort a == sort b) Maybe there's something in the syntax that I'm not quite getting... \/\/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style and a problem
On Fri, Sep 10, 2010 at 12:24:39PM +0300, Wanas wrote: On Fri, Sep 10, 2010 at 1:06 AM, Nils Schweinsberg m...@n-sch.de wrote: Something like this? import Data.List newList :: Int - [[Int]] newList n = myNub [ l | l - undefined -- not really sure how you want -- to generate these lists :) , sum l == sum [1..n] ] myNub :: (Ord a) = [[a]] - [[a]] myNub = nubBy (\a b - sort a == sort b) - Nils So I've checked out this code, and it doesn't compile on ghci. My version, without the undefined portion is(which still doesn't work): import Data.List newList :: Int - [[Int]] newList n = myNub [ l | l - [1..n], sum l == sum [1..n] ] The reason this doesn't compile is that l - [1..n] means l will take on each of the values 1 through n in turn. So l is of type Int. But then you do 'sum l' which requires l to be a list. So clearly that does not typecheck. But I'm not quite sure I understand what you actually want l to be. Do you want it to run through all lists of a certain length with elements chosen from [1..n]? In that case you could do something like import Control.Monad -- for replicateM ... [ l | l - replicateM n [1..n], ... ] which will generate all length-n lists with elements chosen from [1..n]. If you wanted all lists with lengths from 1 to n and elements chosen from 1 to n, you could do [ l | len - [1..n], l - replicateM len [1..n], ... ] As others have pointed out there are likely far more efficient ways to do what you want, but I'm just trying to help you get this code to work first, even if it's inefficient. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style and a problem
Am 09.09.2010 22:55, schrieb Wanas: Hey all, So I have a two part question (I'm new to haskell, so you can throw all your mugs at me). a) I want to write a function that generates lists of lists of size $n$. All having the property that sum lst = sum [1..n]. a-1) After that, I want to remove all permutations. My idea of doing this is to get all lists from the first function and create a new list with the property that if sorted list A is not in the list, add it. b-2) I think that's too much questions, but I want to get the hang of this quickly (it was kickass for the few things I've tried out). Something like this? import Data.List newList :: Int - [[Int]] newList n = myNub [ l | l - undefined -- not really sure how you want -- to generate these lists :) , sum l == sum [1..n] ] myNub :: (Ord a) = [[a]] - [[a]] myNub = nubBy (\a b - sort a == sort b) - Nils ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style and a problem
On Thursday 09 September 2010 22:55:14, Wanas wrote: Hey all, So I have a two part question (I'm new to haskell, so you can throw all your mugs at me). a) I want to write a function that generates lists of lists of size $n$. All having the property that sum lst = sum [1..n]. a-1) After that, I want to remove all permutations. My idea of doing this is to get all lists from the first function and create a new list with the property that if sorted list A is not in the list, add it. It's better to not create equivalent lists from the beginning. For n = 12, for example, there are almost 500 million (479001600) permutations of [1 .. 12], that's a lot of wasted work if you create them all and throw away all but one. Assuming that the list elements should be positive (or at least non- negative), what you want is to create the partitions of a target sum with a given length. Such a partition can be represented as a list of pairs (number, multiplicity) with the properties a) the sum of the multiplicities is the target length sum (map snd partition) == targetLength b) the sum of (number * multiplicity) is the target sum sum [n * m | (n,m) - partition] == targetSum Such a representation is unique if you demand that the numbers (map fst partition) form a strictly decreasing (or increasing, but decreasing is simpler to construct) list and all multiplicities are strictly positive. So you want a function buildPartitions :: Integer - Integer - Integer - [[(Integer,Integer)]] buildPartitions targetSum targetLength maxNumber should create the list of all essentially different partitions of targetSum into exactly targetLength positive (non-negative) numbers not greater than maxNumber. There are two sorts of such partitions, those containing maxNumber and those which don't, hence buildPartitions targetSum targetLength maxNumber = listOne ++ listTwo where listTwo = buildPartitions targetSum targetLength (maxNumber - 1) and listOne is constructed per - for all multiplicities mul from 1 to some limit - for all partitions part of (targetSum - mul*maxNumber) with length (targetLength - mul) into positive numbers maxNumber - prefix (maxNumber, mul) to part Of course, for there to be any such partitions, some conditions have to be met: targetSum = targetLength*maxNumber targetSum = targetLength (if the numbers have to be strictly positive) With these conditions in mind for the recursive call, you can efficiently generate the list of all essentially different partitions via buildPartitions targetSum targetLength maxNumber = [(maxNumber, mul) : part | mul - [1 .. maxMul] , part - buildPartitions newSum newLength newMax] ++ buildPartitions targetSum targetLength (maxNumber-1) with appropriate values of maxMul and newMax (newMax can often be smaller than maxNumber-1) and a few cases to end the recursion (when no or only one partition is possible). Then you have to flatten the [(Integer, Integer)] lists into [Integer] lists, for example per flatten ps = [n | (n,m) - ps, _ - [1 .. m]] b-2) I think that's too much questions, but I want to get the hang of this quickly (it was kickass for the few things I've tried out). Thanks, \/\/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style and a problem
Hello Wanas, Friday, September 10, 2010, 12:55:14 AM, you wrote: a) I want to write a function that generates lists of lists of size $n$. All having the property that sum lst = sum [1..n]. a-1) After that, I want to remove all permutations. My idea of you have very interesting questions. hopefully it was already answered at http://www.haskell.org/haskellwiki/Homework_help -- 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] Style and a problem
Although it was phrased as one, it wasn't. If it were a homework question, wouldn't you think that I'd be trained to do it or have a TA to ask? But who said that you're accusing me of anything :) Thanks for your concern, Bulat. \/\/ On Fri, Sep 10, 2010 at 1:47 AM, Bulat Ziganshin bulat.zigans...@gmail.comwrote: Hello Wanas, Friday, September 10, 2010, 12:55:14 AM, you wrote: a) I want to write a function that generates lists of lists of size $n$. All having the property that sum lst = sum [1..n]. a-1) After that, I want to remove all permutations. My idea of you have very interesting questions. hopefully it was already answered at http://www.haskell.org/haskellwiki/Homework_help -- 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] Style and a problem
On Sep 10, 2010, at 8:55 AM, Wanas wrote:
Hey all,
So I have a two part question (I'm new to haskell, so you can throw all your
mugs at me).
a) I want to write a function that generates lists of lists of size $n$. All
having the property that sum lst = sum [1..n].
a-1) After that, I want to remove all permutations. My idea of doing this is
to get all lists from the first function and create a new list with the
property that if sorted list A is not in the list, add it.
It's not completely clear to me what you want.
Here's my take on it:
S0 = {L | L is a list of positive integers and sum L = n}
L1 ~~ L2 iff L2 is a permutation of L1
You want to enumerate S0/~~.
Staring at this for a bit, what you want is
ENUMERATING THE PARTITIONS OF AN INTEGER.
Look this up in almost any combinatorics book and you will find an
algorithm that you can adapt. There's stuff in Knuth, AOCP, Vol 4,
for example. A good reference is The Theory of Partitions, by
G. E. Andrews, Cambridge University Press, 1998.
Rung-Bin Lin has reported in Efficient Data Structures for Storing
the Partitions of an Integer on a data structure for representing
all the partitions of an integer n in O(n**2) space, taking O(n**2)
time to construct it, so a list of lists might not be the best way
to do it in Haskell.
What you want to do is to generate the partitions in a canonical
order with no duplicates in the first place. Something along these
lines:
the partiions of n are
the partitions of n into pieces no bigger than n with [] appended.
the partitions of n into pieces no bigger than k with xx appended are
the partitions of n-k into pieces no bigger than k with k::xx appended
followed by
the partitions of n into pieces no bigger than k-1 with xx appended
*with* some termination clauses which I haven't shown.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style Guide for Haskell Code
Henning Thielemann wrote: Of course, style is a matter of taste. So there are as many good styles as programmers and there won't be an official style guide, I'm afraid. While that is true, it's no valid reason to not have a style guide. Sun's style guide for Java has been very successful, improving legibility of Java code in general. Noone has to adhere to it, but most people do anyway. Martijn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style Guide for Haskell Code
On Sat, 14 Mar 2009, Martijn van Steenbergen wrote: Henning Thielemann wrote: Of course, style is a matter of taste. So there are as many good styles as programmers and there won't be an official style guide, I'm afraid. While that is true, it's no valid reason to not have a style guide. Sun's style guide for Java has been very successful, improving legibility of Java code in general. Noone has to adhere to it, but most people do anyway. I'm glad about everyone who follows the tips I have written in Category:Style, but I can by no way call them official. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style Guide for Haskell Code
On Tue, 10 Mar 2009, Manlio Perillo wrote: After a quick search with Google, it seems that there is not yet an official document for Style Guide for Haskell Code. I was only able to found: http://www.cs.caltech.edu/courses/cs11/material/haskell/misc/haskell_style_guide.html http://urchin.earth.li/~ian/style/haskell.html http://github.com/tibbe/haskell-style-guide/tree/master and, of course, the GHC style guide. Ah, why does Google not show http://haskell.org/haskellwiki/Category:Style ? Of course, style is a matter of taste. So there are as many good styles as programmers and there won't be an official style guide, I'm afraid. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Style Guide for Haskell Code
After a quick search with Google, it seems that there is not yet an official document for Style Guide for Haskell Code. I was only able to found: http://www.cs.caltech.edu/courses/cs11/material/haskell/misc/haskell_style_guide.html http://urchin.earth.li/~ian/style/haskell.html http://github.com/tibbe/haskell-style-guide/tree/master and, of course, the GHC style guide. Any plans for a common document? Thanks Manlio Perillo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style Guide for Haskell Code
On Tue, Mar 10, 2009 at 4:34 PM, Manlio Perillo manlio_peri...@libero.it wrote: After a quick search with Google, it seems that there is not yet an official document for Style Guide for Haskell Code. I was only able to found: http://www.cs.caltech.edu/courses/cs11/material/haskell/misc/haskell_style_guide.html http://urchin.earth.li/~ian/style/haskell.html http://github.com/tibbe/haskell-style-guide/tree/master I plan to polish my style guide and add some things I haven't covered in the coming weeks. I believe it for the most part codifies what's common practice in the Haskell community. Cheers, Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
Bjorn Bringert wrote: Here's a much more inefficient version, but it has the merit of being very easy to understand: tm_silly n = length $ takeWhile (=='0') $ reverse $ show $ product [1..n] Be careful with types - use Data.List.genericLength here instead of length. Otherwise, tm_silly n is wrong for n = 13 (on my 32-bit machine) due to round-off error in the Int type. Here is another implementation: base5 n | n 1 = [] | otherwise = let (q, r) = n `divMod` 5 in r : base5 q tm6 = sum . zipWith (*) [(5^k-1)`div`4 | k - [0..]] . base5 Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
2007/8/26, Yitzchak Gale [EMAIL PROTECTED]: Bjorn Bringert wrote: Here's a much more inefficient version, but it has the merit of being very easy to understand: tm_silly n = length $ takeWhile (=='0') $ reverse $ show $ product [1..n] Be careful with types - use Data.List.genericLength here instead of length. Otherwise, tm_silly n is wrong for n = 13 (on my 32-bit machine) due to round-off error in the Int type. Are you sure you really tested tm_silly ? length is perfectly enough to count the 0 in n! since the number of zeros don't go over the Int limit before n = 8_589_934_615 (though this solution will stack overflow due to the product much sooned than that). -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
I wrote: Be careful with types - use Data.List.genericLength here instead of length. Otherwise, tm_silly n is wrong for n = 13 (on my 32-bit machine) due to round-off error in the Int type. Are you sure you really tested tm_silly ? length is perfectly enough to count the 0 in n! since the number of zeros don't go over the Int limit True, that is not the problem. Using length forces the result to be Int, which is different than all of the other tm's so far. So for example, try this: [n | n - [0..25], tm_silly n /= tm n] -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
2007/8/26, Yitzchak Gale [EMAIL PROTECTED]: True, that is not the problem. Using length forces the result to be Int, which is different than all of the other tm's so far. So for example, try this: [n | n - [0..25], tm_silly n /= tm n] You mean to say that tm_silly returns Int, which means we can't use it directly in a comparison but have to use toInteger or fromInteger ? Ok, in this case, but it's still a nice test for our more optimized functions (and using genericLength is much slower than toInteger . length, though of course the results differ for really long list) $ [n | n - [1..1000], toInteger (tm_silly n) /= tm n] [] -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Style
Hi, I defined several functions for calculating the number of trailing zero's of n! tm = sum . takeWhile(0) . iterate f . f where f = flip div 5 tm1 n = sum . takeWhile(0) . map (div n . (5^)) $ [1..] tm2 n = sum . takeWhile(0) . map (div n) $ iterate ((*)5) 5 tm3 = sum . takeWhile(0) . flip map (iterate ((*)5) 5) . div Questions: Which one is the most elegant one generally speaking? Which one is most natural in Haskell? Is there more 'beauty' to possible? My personal choice is 'tm'. I like 'tm3' (a revised version of tm2) in terms of pointlessness and not having a 'where', but I think it's a bit contrived because of the 'flip'. Comments? Thanks @@i ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
On Aug 24, 2007, at 9:18 , Arie Groeneveld wrote: Hi, I defined several functions for calculating the number of trailing zero's of n! tm = sum . takeWhile(0) . iterate f . f where f = flip div 5 tm1 n = sum . takeWhile(0) . map (div n . (5^)) $ [1..] tm2 n = sum . takeWhile(0) . map (div n) $ iterate ((*)5) 5 tm3 = sum . takeWhile(0) . flip map (iterate ((*)5) 5) . div Questions: Which one is the most elegant one generally speaking? Which one is most natural in Haskell? Is there more 'beauty' to possible? My personal choice is 'tm'. I like 'tm3' (a revised version of tm2) in terms of pointlessness and not having a 'where', but I think it's a bit contrived because of the 'flip'. Comments? Here's a much more inefficient version, but it has the merit of being very easy to understand: tm_silly n = length $ takeWhile (=='0') $ reverse $ show $ product [1..n] /Björn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
Bjorn Bringert wrote: Here's a much more inefficient version, but it has the merit of being very easy to understand: tm_silly n = length $ takeWhile (=='0') $ reverse $ show $ product [1..n] You're rigth. I came up with that one too the first time. But for large value's of n it takes too much time. You may improve that (time) by using another product formula: *Main length $ takeWhile (=='0') $ reverse $ show $ foldl' (*) 1 [1..3] 7498 (0.96 secs, 790685000 bytes) *Main length $ takeWhile (=='0') $ reverse $ show $ product [1..3] 7498 (4.05 secs, 792259140 bytes) But: *Main tm 3 7498 (0.00 secs, 524924 bytes) Thanks @@i ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
On Fri, 24 Aug 2007, Arie Groeneveld wrote: I defined several functions for calculating the number of trailing zero's of n! tm = sum . takeWhile(0) . iterate f . f where f = flip div 5 This is very elegant! You could also inline 'f' tm4 = sum . takeWhile(0) . tail . iterate (flip div 5) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
tm = sum . takeWhile(0) . iterate f . f where f = flip div 5 Quite nice. I like tm5 0 = 0 tm5 n = let q = div n 5 in q + tm5 q This version corresponds to what I'm think when parsing |tm|, so I wrote it down directly. Also possible tm6 = sum . unfoldr ( \ n - case div n 5 of 0 - mzero q - return (q,q) ) I tend to not use |iterate|, when it is known in advance, which prefix of the so constructed infinite list is used. /BR -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ --- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
Marc A. Ziegert [EMAIL PROTECTED] tm_parallelizable_v1 = \n - sum . takeWhile (0) $ map (div n) fives where fives = iterate (*5) 1 tm_improved_v1 n = sum . takeWhile (0) $ iterate (div `flip` 5) (div n 5) tm_fastestIMHO n = let m=div n 5 in if m5 then m else m+tm_fastestIMHO m Henning Thielemann [EMAIL PROTECTED] tm4 = sum . takeWhile(0) . tail . iterate (flip div 5) Bjorn Bringert [EMAIL PROTECTED] tm_silly n = length $ takeWhile (=='0') $ reverse $ show $ product [1..n] Arie Groeneveld [EMAIL PROTECTED] tm = sum . takeWhile(0) . iterate f . f where f = flip div 5 tm1 n = sum . takeWhile(0) . map (div n . (5^)) $ [1..] tm2 n = sum . takeWhile(0) . map (div n) $ iterate ((*)5) 5 tm3 = sum . takeWhile(0) . flip map (iterate ((*)5) 5) . div 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] Style
Thanks for all the instructive replies and alternatives! Learned a bit more in terms of feeling about style and improvement of some of the functions: f.e. 'killing' the 'where' in my number one choice. Thanks @@i ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
Henning Thielemann wrote: tm4 = sum . takeWhile(0) . tail . iterate (flip div 5) FWIW: as a result of all this I learned to write this as: tm41 = sum . takeWhile(0) . tail . iterate (`div` 5) @@i ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
Arie Groeneveld wrote: tm = sum . takeWhile(0) . iterate f . f where f = flip div 5 Which one is the most elegant one generally speaking? I like that tm only uses div. My personal choice is 'tm'. I like 'tm3' (a revised version of tm2) in terms of pointlessness and not having a 'where', but I think it's a bit contrived because of the 'flip'. You can make tm whereless by noticing that you use because you use the function twice in iterate f . f, which is because you don't want the initial value that iterate gives. You can instead use tail on iterate's result, and use a section to avoid flip: tm = sum . takeWhile (0) . tail . iterate (`div` 5) (Hope that works, can't test now...) All the best Christian Sievers ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Style
whops... i did check it, but that was a copypaste mistake. buggy: tm_parallelizable_v1 = \n - sum . takeWhile (0) $ map (div n) fives where fives = iterate (*5) 1 should be: tm_parallelizable_v1 = \n - sum . takeWhile (0) $ map (div n) fives where fives = iterate (*5) 5 - marc Am Freitag, 24. August 2007 schrieben Sie: Hi Marc First off, thanks for your reply. tm_parallelizable_v1 = \n - sum . takeWhile (0) $ map (div n) fives where fives = iterate (*5) 1 Did you check this one? IMHO I think it's producing the 'wrong' answer. *Main tm_parallelizable_v1 100 124 (0.00 secs, 0 bytes) *Main tm 100 24 (0.00 secs, 0 bytes) If comparing the result to the other variants is accepted as a sort of proof. ;-) But calculating the number of trailing zero's of n! is a matter of counting powers of five in the factorized n!: f.e.: 10! = 1 2 3 2^2 5 2*3 7 2^3 3^2 2*5 -- 5^2 -- picking up enough powers of 2 -- (2*5)^2 = 100 So you will have to correct your 'fives' to f.e. fives = tail $ iterate (*5) 1 Regards @@i 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[2]: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
Hello Gregory, Friday, August 25, 2006, 3:08:09 AM, you wrote: Some performance data: using unsafeIOToST to write log messages directly to the output, the simulation does 10^7 state updates in about 45 seconds on my 1.5 GHz ppc G4. Using LogT, with a list of strings as the monoid, it takes about 7 minutes to do the same, and the system swaps heavily during the last few minutes. Not surprising, given that the mappend operation is not very efficient for the list monoid. are you sure that you know how monads are implemented? IO/ST monads just organize order of execution, without any penalty comparing to imperative languages. but other monads and all monad transformers add their data to the tuple passed between monad operations. and this makes their execution significantly slower. you can read more about this in http://sigfpe.blogspot.com/2006/08/you-could-have-invented-monads-and.html about multi-threading - you can (and should!) use ghc's internal concurrency with forkIO. it is a perfect way - with minimal overhead and ability to use any Haskell features in each thread without fighting against multi-threading implementation -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
Hi Bulat, On Aug 25, 2006, at 3:36 AM, Bulat Ziganshin wrote: Hello Gregory, Friday, August 25, 2006, 3:08:09 AM, you wrote: Some performance data: using unsafeIOToST to write log messages directly to the output, the simulation does 10^7 state updates in about 45 seconds on my 1.5 GHz ppc G4. Using LogT, with a list of strings as the monoid, it takes about 7 minutes to do the same, and the system swaps heavily during the last few minutes. Not surprising, given that the mappend operation is not very efficient for the list monoid. are you sure that you know how monads are implemented? IO/ST monads just organize order of execution, without any penalty comparing to imperative languages. but other monads and all monad transformers add their data to the tuple passed between monad operations. and this makes their execution significantly slower. you can read more about this in http://sigfpe.blogspot.com/2006/08/you-could-have-invented- monads-and.html No doubt my understanding of the underlying implementation could be improved. I will read the reference. Thank you. about multi-threading - you can (and should!) use ghc's internal concurrency with forkIO. it is a perfect way - with minimal overhead and ability to use any Haskell features in each thread without fighting against multi-threading implementation I will give this a try when I get to that stage in the project. Best Wishes, Greg -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ 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] style question: Writer monad or unsafeIOToST?
Hi,
Thanks to the responses earlier from the list, the core of my simulator
now happy processes tens of millions of state updates without running
out of stack.
The goal of the simulator is to produce a log of tag states, which
can be
analyzed to find statistics of how often the sensor tags in a
particular state.
(In the toy model below there is no external signal, so the log isn't
very
interesting yet.) For the moment, I am using the big stick
approach of
unsafeIOToST to write log messages. Since the only outputs of the
program
are the log messages, and invocations of step are ordered by the ST
monad,
it seems that unsafeIOToST is safe in this case, in the sense that
the outputs
will all be ordered the same as the actual state updates.
I've tested the program test1.hs below and it quite fast (runs in
just under 10 s,
or about 10^6 state updates per second).
I've considered using a WriterT monad to wrap the ST monad to produce
a log. The problem with this seems to be ensuring that the log output
is generated lazily so it can be incrementally output. A somewhat broken
sketch is the program test2.hs below. I used a function from
[String] - [String]
as the monoid to avoid the O(n^2) inefficiency of appending to a
list, but
my implementation of this may well be faulty.
To my eye, the Writer monad should be a better way, since it
encapsulates
the logging process, separating it from other I/O that the program
may do.
On the other hand, I don't see an easy way to ensure that the log output
is generated lazily so that it can be output incrementally. I think
that the
main issue is that until_ is building up a list of log strings, but
that these
aren't passed to the putStrLn until after the completion of the whole
runTag
function. ATM, running test2 gives a stack overflow.
Could someone point out how the Writer monad could be adapted to this,
or tell me that, Real programmers just use unsafe* and get on with
it ?
Best,
greg
--
test1.hs, the big stick (unsafeIOToST):
--
-- test1.hs, state updating with logging via unsafeIOToST.
--
module Main where
import Control.Monad.ST
import Data.STRef
import Maybe
data TagState = Syncing | Listening | Sleeping
deriving (Eq, Show)
-- A structure with internal state:
--
data Tag s = Tag {
tagID :: ! Int,
state :: ! (STRef s TagState),
count :: ! (STRef s Integer)
}
data FrozenTag = FrozenTag {
ft_tagID :: Int,
ft_state :: TagState,
ft_count :: Integer
} deriving Show
-- Repeat a computation until it returns Nothing:
--
until_ :: Monad m = m (Maybe a) - m ()
until_ action = do
result - action
if isNothing result
then return ()
else until_ action
-- Here is a toy stateful computation:
--
runTag :: ST s (FrozenTag)
runTag = do
tag - initialize
until_ (step tag)
freezeTag tag
initialize :: ST s (Tag s)
initialize = do
init_count - newSTRef 100
init_state - newSTRef Syncing
return (Tag { tagID = 1,
state = init_state,
count = init_count })
step :: Tag s - ST s (Maybe Integer)
step t = do
c - readSTRef (count t)
s - readSTRef (state t)
writeSTRef (count t) $! (c - 1)
writeSTRef (state t) $! (nextState s)
unsafeIOToST $! putStrLn (next state is ++ show s)
if (c = 0) then return Nothing else return (Just c)
nextState :: TagState - TagState
nextState s = case s of
Syncing - Listening
Listening - Sleeping
Sleeping - Syncing
freezeTag :: Tag s - ST s (FrozenTag)
freezeTag t = do
frozen_count - readSTRef (count t)
frozen_state - readSTRef (state t)
return (FrozenTag { ft_tagID = tagID t,
ft_count = frozen_count,
ft_state = frozen_state })
main :: IO ()
main = do
print $ runST (runTag)
-
test2.hs: stacked WriterT and ST monads:
--
-- test2.hs, state updating with logging via the WriterT monad.
--
module Main where
import Control.Monad.ST
import Control.Monad.Writer
import Data.STRef
import Maybe
data TagState = Syncing | Listening | Sleeping
deriving (Eq, Show)
-- A type for combined logging and state transformation:
--
type LogMonoid = [String] - [String]
type LogST s a = WriterT LogMonoid (ST s) a
-- A structure with internal state:
--
data Tag s = Tag {
tagID :: ! Int,
state :: ! (STRef s TagState),
count :: ! (STRef s Integer)
}
data FrozenTag = FrozenTag {
ft_tagID :: Int,
ft_state :: TagState,
ft_count :: Integer
} deriving Show
-- Repeat a
Re: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
Gregory Wright wrote: Hi, Thanks to the responses earlier from the list, the core of my simulator now happy processes tens of millions of state updates without running out of stack. The goal of the simulator is to produce a log of tag states, which can be analyzed to find statistics of how often the sensor tags in a particular state. (In the toy model below there is no external signal, so the log isn't very interesting yet.) For the moment, I am using the big stick approach of unsafeIOToST to write log messages. Since the only outputs of the program are the log messages, and invocations of step are ordered by the ST monad, it seems that unsafeIOToST is safe in this case, in the sense that the outputs will all be ordered the same as the actual state updates. I've tested the program test1.hs below and it quite fast (runs in just under 10 s, or about 10^6 state updates per second). I've considered using a WriterT monad to wrap the ST monad to produce a log. The problem with this seems to be ensuring that the log output is generated lazily so it can be incrementally output. A somewhat broken sketch is the program test2.hs below. I used a function from [String] - [String] as the monoid to avoid the O(n^2) inefficiency of appending to a list, but my implementation of this may well be faulty. (Writer [String] [Int]) can produce the log lazily. (WriterT [String] Identity [Int]) cannot produce the log lazily. But (Identity [Int]) can produce its output lazily. Using ST.Lazy and Either instead of WriterT, I can get the streaming behavior. But I have to use a continuation passing style module Main where import Control.Monad.ST.Lazy import Data.STRef.Lazy import Control.Monad.Writer import Control.Monad.Identity import Maybe import Debug.Trace type LogMonoid = [String] - [String] loop :: Int - Writer [String] [Int] loop 0 = trace end of loop (return [0]) loop x = do let msg = loop now ++ show x tell [msg] liftM (x:) (loop (pred x)) loop' :: Int - WriterT [String] Identity [Int] loop' 0 = trace end of loop' (return [0]) loop' x = do let msg = loop' now ++ show x tell [msg] liftM (x:) (loop' (pred x)) loopI :: Int - Identity [Int] loopI 0 = trace end of loopI (return [0]) loopI x = liftM (x:) (loopI (pred x)) loopM :: Int - WriterT LogMonoid Identity [Int] loopM 0 = trace end of loopM (return [0]) loopM x = do let msg = loopM now ++ show x tell (msg:) liftM (x:) (loopM (pred x)) loopST :: Int - ST s [Either String Int] loopST init = do ref - newSTRef init let loop = do x - readSTRef ref writeSTRef ref $! (pred x) let msg = Left (loopST now ++ show x) cont = if x==0 then trace end of loopST (return [Right 0]) else loop liftM (msg :) cont loop loopST2 :: Int - ST s [Either String Int] loopST2 init = do ref - newSTRef init let loop = do x - readSTRef ref writeSTRef ref $! (pred x) let msg = Left (loopST now ++ show x) cont = if x==0 then trace end of loopST (return [Right 0]) else loop rest - cont return (msg : rest) loop main :: IO () main = do let log = execWriter (loop 100) print (head log) print (last log) let log' = runIdentity (execWriterT (loop' 100)) print (head log') print (last log') let logI = runIdentity (loopI 100) print (head logI) print (last logI) let logMf = runIdentity (execWriterT (loopM 100)) logM = logMf [] print (head logM) print (last logM) let logst = runST (loopST 100) print (head logst) print (last logst) let logst2 = runST (loopST2 100) print (head logst2) print (last logst2) Edited output is $ ./maindemo loop now 100 end of loop loop now 1 end of loop' loop' now 100 loop' now 1 100 end of loopI 0 end of loopM loopM now 100 loopM now 1 Left loopST now 100 end of loopST Right 0 Left loopST now 100 end of loopST Right 0 From the above the WriterT in loop' and loopM are not lazy but the other examples are. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
The problem with WriterT is it is too strict.
See http://www.mail-archive.com/haskell@haskell.org/msg16088.html
The fix is adding ~ to the patterns inside the definition of (=):
~(a,w) - runLogT m
~(b,w') - runLogT (k a)
A lazy version of WriterT, called LogT:
{-# OPTIONS_GHC -fglasgow-exts #-}
module Main where
import Control.Monad.ST.Lazy
import Data.STRef.Lazy
import Control.Monad.Writer
import Control.Monad.Identity
import Control.Monad.Fix
import Control.Monad.Trans
import Control.Monad.Reader
import Maybe
import Debug.Trace
type LogMonoid = [String] - [String]
loopLT :: Int - LogT [String] Identity [Int]
loopLT 0 = trace end of loopLT (return [0])
loopLT x = do
let msg = loopLT now ++ show x
tell [msg]
liftM (x:) (loopLT (pred x))
newtype LogT w m a = LogT { runLogT :: m (a, w) }
instance (Monad m) = Functor (LogT w m) where
fmap f m = LogT $ do
(a, w) - runLogT m
return (f a, w)
instance (Monoid w, Monad m) = Monad (LogT w m) where
return a = LogT $ return (a, mempty)
m = k = LogT $ do
~(a,w) - runLogT m
~(b,w') - runLogT (k a)
return (b, w `mappend` w')
fail msg = LogT $ fail msg
instance (Monoid w, MonadPlus m) = MonadPlus (LogT w m) where
mzero = LogT mzero
m `mplus` n = LogT $ runLogT m `mplus` runLogT n
instance (Monoid w, MonadFix m) = MonadFix (LogT w m) where
mfix m = LogT $ mfix $ \ ~(a, _) - runLogT (m a)
instance (Monoid w, Monad m) = MonadWriter w (LogT w m) where
tell w = LogT $ return ((), w)
listen m = LogT $ do
(a, w) - runLogT m
return ((a, w), w)
pass m = LogT $ do
((a, f), w) - runLogT m
return (a, f w)
instance (Monoid w) = MonadTrans (LogT w) where
lift m = LogT $ do
a - m
return (a, mempty)
instance (Monoid w, MonadIO m) = MonadIO (LogT w m) where
liftIO = lift . liftIO
-- This instance needs -fallow-undecidable-instances, because
-- it does not satisfy the coverage condition
instance (Monoid w, MonadReader r m) = MonadReader r (LogT w m) where
ask = lift ask
local f m = LogT $ local f (runLogT m)
execLogT :: Monad m = LogT w m a - m w
execLogT m = do
(_, w) - runLogT m
return w
mapLogT :: (m (a, w) - n (b, w')) - LogT w m a - LogT w' n b
mapLogT f m = LogT $ f (runLogT m)
main :: IO ()
main = do
let logLT = runIdentity (execLogT (loopLT 100))
print (head logLT)
print (last logLT)
The output is
./maindemo
loopLT now 100
end of loopLT
loopLT now 1
Just as we want.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
So using LogT instead of WriterT, and changing from Control.Monad.ST to
Control.Monad.ST.Lazy I can make you code work as you wanted:
{-# OPTIONS_GHC -fglasgow-exts #-}
module Main where
import Control.Monad.ST.Lazy
import Data.STRef.Lazy
import Maybe
import Debug.Trace
-- LogT, copied from
http://darcs.haskell.org/packages/mtl/Control/Monad/Writer.hs
import Control.Monad.Writer
import Control.Monad.Reader
import Control.Monad.Fix
import Control.Monad.Trans
newtype LogT w m a = LogT { runLogT :: m (a, w) }
instance (Monad m) = Functor (LogT w m) where
fmap f m = LogT $ do
(a, w) - runLogT m
return (f a, w)
instance (Monoid w, Monad m) = Monad (LogT w m) where
return a = LogT $ return (a, mempty)
m = k = LogT $ do
~(a,w) - runLogT m
~(b,w') - runLogT (k a)
return (b, w `mappend` w')
fail msg = LogT $ fail msg
instance (Monoid w, MonadPlus m) = MonadPlus (LogT w m) where
mzero = LogT mzero
m `mplus` n = LogT $ runLogT m `mplus` runLogT n
instance (Monoid w, MonadFix m) = MonadFix (LogT w m) where
mfix m = LogT $ mfix $ \ ~(a, _) - runLogT (m a)
instance (Monoid w, Monad m) = MonadWriter w (LogT w m) where
tell w = LogT $ return ((), w)
listen m = LogT $ do
(a, w) - runLogT m
return ((a, w), w)
pass m = LogT $ do
((a, f), w) - runLogT m
return (a, f w)
instance (Monoid w) = MonadTrans (LogT w) where
lift m = LogT $ do
a - m
return (a, mempty)
instance (Monoid w, MonadIO m) = MonadIO (LogT w m) where
liftIO = lift . liftIO
instance (Monoid w, MonadReader r m) = MonadReader r (LogT w m) where
ask = lift ask
local f m = LogT $ local f (runLogT m)
execLogT :: Monad m = LogT w m a - m w
execLogT m = do
(_, w) - runLogT m
return w
mapLogT :: (m (a, w) - n (b, w')) - LogT w m a - LogT w' n b
mapLogT f m = LogT $ f (runLogT m)
-- End of LogT
data TagState = Syncing | Listening | Sleeping
deriving (Eq, Show)
-- A type for combined logging and state transformation:
--
type LogMonoid = [String] - [String]
type LogST s a = LogT LogMonoid (ST s) a
-- A structure with internal state:
--
data Tag s = Tag {
tagID :: ! Int,
state :: ! (STRef s TagState),
count :: ! (STRef s Integer)
}
data FrozenTag = FrozenTag {
ft_tagID :: Int,
ft_state :: TagState,
ft_count :: Integer
} deriving Show
-- Repeat a computation until it returns Nothing:
--
until_ :: Monad m = m (Maybe a) - m ()
until_ action = do
result - action
if isNothing result
then trace until_ is finished (return ())
else until_ action
-- Here is a toy stateful computation:
--
runTag :: LogST s (FrozenTag)
runTag = do
tag - initialize
until_ (step tag)
freezeTag tag
initialize :: LogST s (Tag s)
initialize = do
init_count - lift $ newSTRef 100
init_state - lift $ newSTRef Syncing
return (Tag { tagID = 1,
state = init_state,
count = init_count })
step :: Tag s - LogST s (Maybe Integer)
step t = do
c - lift $ readSTRef (count t)
s - lift $ readSTRef (state t)
lift $ writeSTRef (count t) $! (c - 1)
lift $ writeSTRef (state t) $! (nextState s)
tell ((next state is ++ show s) : )
if (c = 0) then return Nothing else return (Just c)
nextState :: TagState - TagState
nextState s = case s of
Syncing - Listening
Listening - Sleeping
Sleeping - Syncing
freezeTag :: Tag s - LogST s (FrozenTag)
freezeTag t = do
frozen_count - lift $ readSTRef (count t)
frozen_state - lift $ readSTRef (state t)
return (FrozenTag { ft_tagID = tagID t,
ft_count = frozen_count,
ft_state = frozen_state })
main :: IO ()
main = do
let (t, l) = runST (runLogT runTag)
log = l []
putStrLn (show . head $ log)
putStrLn (show . last $ log)
output is
$ ./main2
next state is Syncing
until_ is finished
next state is Listening
with a very long delay after the first line of output and before the second.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
Hello Gregory, Thursday, August 24, 2006, 7:29:47 PM, you wrote: it seems that unsafeIOToST is safe in this case, in the sense that why you are stuck to ST monad? isn't it better to use just IO monad? and about total style - again, you can use my lib or write this yourself so that all you reference operations will work independent on Monad used and you can freely experiment with different monads without rewriting whole code: class Ref m r | m-r where newRef readRef writeRef instance Ref IO IORef writeRef r x = writeIORef r $! x instance (Ref m r) = Ref (WriterT m) r where writeRef = lift . writeRef and so on... ps to Brian: it is why i was so interested in your idea. writing monad-independent code, including code that can be applied to any monad lifted from ST or IO, looks for me very promising idea, somewhat that will be widely used in future -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
Hi Chris,
Thank you. That is exactly what I needed to know.
It's good to know that I'm not totally crazy and that with the
lazier LogT the code can run as it was written. It seems
as if a request should be made for a Writer.Lazy as well as
the existing Writer.Strict. (The latter could well be the default,
just as with the ST monad.) A good idea?
Virtual beer to you sir!
-Greg
On Aug 24, 2006, at 1:05 PM, Chris Kuklewicz wrote:
The problem with WriterT is it is too strict.
See http://www.mail-archive.com/haskell@haskell.org/msg16088.html
The fix is adding ~ to the patterns inside the definition of (=):
~(a,w) - runLogT m
~(b,w') - runLogT (k a)
A lazy version of WriterT, called LogT:
{-# OPTIONS_GHC -fglasgow-exts #-}
module Main where
import Control.Monad.ST.Lazy
import Data.STRef.Lazy
import Control.Monad.Writer
import Control.Monad.Identity
import Control.Monad.Fix
import Control.Monad.Trans
import Control.Monad.Reader
import Maybe
import Debug.Trace
type LogMonoid = [String] - [String]
loopLT :: Int - LogT [String] Identity [Int]
loopLT 0 = trace end of loopLT (return [0])
loopLT x = do
let msg = loopLT now ++ show x
tell [msg]
liftM (x:) (loopLT (pred x))
newtype LogT w m a = LogT { runLogT :: m (a, w) }
instance (Monad m) = Functor (LogT w m) where
fmap f m = LogT $ do
(a, w) - runLogT m
return (f a, w)
instance (Monoid w, Monad m) = Monad (LogT w m) where
return a = LogT $ return (a, mempty)
m = k = LogT $ do
~(a,w) - runLogT m
~(b,w') - runLogT (k a)
return (b, w `mappend` w')
fail msg = LogT $ fail msg
instance (Monoid w, MonadPlus m) = MonadPlus (LogT w m) where
mzero = LogT mzero
m `mplus` n = LogT $ runLogT m `mplus` runLogT n
instance (Monoid w, MonadFix m) = MonadFix (LogT w m) where
mfix m = LogT $ mfix $ \ ~(a, _) - runLogT (m a)
instance (Monoid w, Monad m) = MonadWriter w (LogT w m) where
tell w = LogT $ return ((), w)
listen m = LogT $ do
(a, w) - runLogT m
return ((a, w), w)
pass m = LogT $ do
((a, f), w) - runLogT m
return (a, f w)
instance (Monoid w) = MonadTrans (LogT w) where
lift m = LogT $ do
a - m
return (a, mempty)
instance (Monoid w, MonadIO m) = MonadIO (LogT w m) where
liftIO = lift . liftIO
-- This instance needs -fallow-undecidable-instances, because --
it does not satisfy the coverage condition
instance (Monoid w, MonadReader r m) = MonadReader r (LogT w m)
where
ask = lift ask
local f m = LogT $ local f (runLogT m)
execLogT :: Monad m = LogT w m a - m w
execLogT m = do
(_, w) - runLogT m
return w
mapLogT :: (m (a, w) - n (b, w')) - LogT w m a - LogT w' n b
mapLogT f m = LogT $ f (runLogT m)
main :: IO ()
main = do
let logLT = runIdentity (execLogT (loopLT 100))
print (head logLT)
print (last logLT)
The output is
./maindemo
loopLT now 100
end of loopLT
loopLT now 1
Just as we want.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] style question: Writer monad or unsafeIOToST?
Hi Bulat! On Aug 24, 2006, at 1:17 PM, Bulat Ziganshin wrote: Hello Gregory, Thursday, August 24, 2006, 7:29:47 PM, you wrote: it seems that unsafeIOToST is safe in this case, in the sense that why you are stuck to ST monad? isn't it better to use just IO monad? The IO monad may be more appropriate. The simulation evolved out of a different (and simpler) simulate for a 6502 microcontroller which used the ST monad. I had thought at the time that there may be multiple threads in the full simulation, so using state threads seemed a good idea at the time. (The full simulation may still need multiple threads; I don't know yet.) As it stands, the code I had written was almost correct. I needed a lazy version of the WriterT monad to make it work. Chris Kuklewicz pointed this out to me. The toy model now works with both the lazy WriterT (called LogT here) and the unsafe* operation. Some performance data: using unsafeIOToST to write log messages directly to the output, the simulation does 10^7 state updates in about 45 seconds on my 1.5 GHz ppc G4. Using LogT, with a list of strings as the monoid, it takes about 7 minutes to do the same, and the system swaps heavily during the last few minutes. Not surprising, given that the mappend operation is not very efficient for the list monoid. Is there a simple monoid structure I could use instead of a list to generate the log string incrementally? I don't care if the order of the output is reversed. and about total style - again, you can use my lib or write this yourself so that all you reference operations will work independent on Monad used and you can freely experiment with different monads without rewriting whole code: class Ref m r | m-r where newRef readRef writeRef instance Ref IO IORef writeRef r x = writeIORef r $! x instance (Ref m r) = Ref (WriterT m) r where writeRef = lift . writeRef and so on... The code snippet above looks like a very good idea. The monad dependent operations combined with lift seem more complicated than necessary. lift in particular often seems like plumbing that should not be necessary. Best Wishes, Greg ps to Brian: it is why i was so interested in your idea. writing monad-independent code, including code that can be applied to any monad lifted from ST or IO, looks for me very promising idea, somewhat that will be widely used in future -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ 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] style question: Writer monad or unsafeIOToST?
class Ref m r | m-r where newRef readRef writeRef instance Ref IO IORef writeRef r x = writeIORef r $! x instance (Ref m r) = Ref (WriterT m) r where writeRef = lift . writeRef and so on... The code snippet above looks like a very good idea. The monad dependent operations combined with lift seem more complicated than necessary. lift in particular often seems like plumbing that should not be necessary. Best Wishes, Greg Well, lift is the common plumbing that lets you build writeRef and liftIO. So it is an intermediate invention. In fact it is the only thing in MonadTrans: class MonadTrans (t::(* - *) - * - *) where lift :: forall (m::* - *) a. Monad m = m a - t m a -- Imported from Control.Monad.Trans You are supposed to make higher level shorthand and abstractions from it. But it helps to learn how the plumbing works. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
