<br><font size=3>> But I would expect intTable to be faster,</font>
<br>
<br><font size=2 face="sans-serif">But if I understand correctly, intTable
can only deal with integer keys, whereas BH's original question would have
wanted string keys, and I can't see a way to convert string to int and
back.</font>
<br>
<br><font size=2 face="sans-serif">t.</font>
<br>
<br>
<br>
<br>
<table width=100%>
<tr valign=top>
<td width=40%><font size=1 face="sans-serif"><b>"Chad Scherrer"
<chad.scherrer@gmail.com></b> </font>
<p><font size=1 face="sans-serif">10/17/2007 11:38 PM</font>
<td width=59%>
<table width=100%>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">To</font></div>
<td><font size=1 face="sans-serif">Thomas Hartman/ext/dbcom@DBAmericas</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td><font size=1 face="sans-serif">haskell-cafe@haskell.org, haskell-cafe-bounces@haskell.org</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">Re: [Haskell-cafe] Re: Suspected stupid
Haskell Question</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><font size=3>Hmm, is insertWith' new? If I remember right, I think
the stack overflows were happening because Map.insertWith isn't strict
enough. Otherwise I think the code is the same. But I would expect intTable
to be faster, since it uses IntMap, and there's no IntMap.insertWith' as
of 6.6.1 (though it may be easy enough to add one).<br>
<br>
Chad<br>
</font>
<br><font size=3>On 10/17/07, <b>Thomas Hartman</b> <</font><a href=mailto:thomas.hartman@db.com><font size=3 color=blue><u>
thomas.hartman@db.com</u></font></a><font size=3>> wrote:</font>
<br><font size=2 face="sans-serif"><br>
Since I'm interested in the stack overflow issue, and getting acquainted
with quickcheck, I thought I would take this opportunity to compare your
ordTable with some code Yitzchak Gale posted earlier, against Ham's original
problem.</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
As far as I can tell, they're the same. They work on lists up to 100000
element lists of strings, but on 10^6 size lists I lose patience waiting
for them to finish. </font><font size=3><br>
</font><font size=2 face="sans-serif"><br>
Is there a more scientific way of figuring out if one version is better
than the other by using, say profiling tools?</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
Or by reasoning about the code?</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
t.</font><font size=3> <br>
</font><font size=2 face="sans-serif"><br>
****************************************</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
import Data.List</font><font size=3> </font><font size=2 face="Courier New"><br>
import qualified Data.Map as M</font><font size=3> </font><font size=2 face="Courier New"><br>
import Control.Arrow</font><font size=3> </font><font size=2 face="Courier New"><br>
import Test.QuickCheck</font><font size=3> </font><font size=2 face="Courier New"><br>
import Test.GenTestData</font><font size=3> </font><font size=2 face="Courier New"><br>
import System.Random</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
{-</font><font size=3> </font><font size=2 face="Courier New"><br>
Is there a library function to take a list of Strings and return a list
of</font><font size=3> </font><font size=2 face="Courier New"><br>
ints showing how many times each String occurs in the list.</font><font size=3>
<br>
</font><font size=2 face="Courier New"><br>
So for example:</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
["egg", "egg", "cheese"] would return [2,1]
<br>
-}</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
testYitzGale n = do</font><font size=3> </font><font size=2 face="Courier New"><br>
l <- rgenBndStrRow (10,10) (10^n,10^n) -- 100000 strings,
strings are 10 chars long, works. craps out on 10^6.</font><font size=3>
</font><font size=2 face="Courier New"><br>
m <- return $ freqFold l <br>
putStrLn $ "map items: " ++ ( show $ M.size m )</font><font size=3>
<br>
</font><font size=2 face="Courier New"><br>
testCScherer n = do</font><font size=3> </font><font size=2 face="Courier New"><br>
l <- rgenBndStrRow (10,10) (10^n,10^n) -- same limitations
as yitz gale code.</font><font size=3> </font><font size=2 face="Courier New"><br>
m <- return $ ordTable l <br>
putStrLn $ "items: " ++ ( show $ length m )</font><font size=3>
<br>
<br>
</font><font size=2 face="Courier New"><br>
-- slow for big lists</font><font size=3> </font><font size=2 face="Courier New"><br>
--freqArr = Prelude.map ( last &&& length ) . group . sort</font><font size=3>
<br>
</font><font size=2 face="Courier New"><br>
-- yitz gale code. same as chad scherer code? it's simpler to understand,
but is it as fast?</font><font size=3> </font><font size=2 face="Courier New"><br>
freqFold :: [[Char]] -> M.Map [Char] Int</font><font size=3> </font><font size=2 face="Courier New"><br>
freqFold = foldl' g M.empty</font><font size=3> </font><font size=2 face="Courier New"><br>
where g accum x = M.insertWith' (+) x 1 accum</font><font size=3>
</font><font size=2 face="Courier New"><br>
-- c scherer code. insists on ord. far as I can tell, same speed as yitz.</font><font size=3>
</font><font size=2 face="Courier New"><br>
ordTable :: (Ord a) => [a] -> [(a,Int)]</font><font size=3> </font><font size=2 face="Courier New"><br>
ordTable xs = M.assocs $! foldl' f M.empty xs</font><font size=3> </font><font size=2 face="Courier New"><br>
where f m x = let m' = M.insertWith (+) x 1 m</font><font size=3>
</font><font size=2 face="Courier New"><br>
Just v = M.lookup x m'</font><font size=3> </font><font size=2 face="Courier New"><br>
in v `seq`
m'</font><font size=3> <br>
<br>
</font><font size=2 face="Courier New"><br>
l = ["egg","egg","cheese"]</font><font size=3>
<br>
</font><font size=2 face="Courier New"><br>
-- other quickcheck stuff</font><font size=3> </font><font size=2 face="Courier New"><br>
--prop_unchanged_by_reverse = \l -> ( freqArr (l :: [[Char]]) ) == (
freqArr $ reverse l )</font><font size=3> </font><font size=2 face="Courier New"><br>
--prop_freqArr_eq_freqFold = \l -> ( freqArr (l :: [[Char]]) == (freqFold
l))</font><font size=3> </font><font size=2 face="Courier New"><br>
--test1 = quickCheck prop_unchanged_by_reverse</font><font size=3> </font><font size=2 face="Courier New"><br>
--test2 = quickCheck prop_freqArr_eq_freqFold</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
--------------- generate test data: <br>
genBndStrRow (minCols,maxCols) (minStrLen, maxStrLen) = rgen ( genBndLoL
(minStrLen, maxStrLen) (minCols,maxCols) )</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
gen gen = do</font><font size=3> </font><font size=2 face="Courier New"><br>
sg <- newStdGen</font><font size=3> </font><font size=2 face="Courier New"><br>
return $ generate 10000 sg gen</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
-- generator for a list with length between min and max</font><font size=3>
</font><font size=2 face="Courier New"><br>
genBndList :: Arbitrary a => (Int, Int) -> Gen [a]</font><font size=3>
</font><font size=2 face="Courier New"><br>
genBndList (min,max) = do</font><font size=3> </font><font size=2 face="Courier New"><br>
len <- choose (min,max)</font><font size=3> </font><font size=2 face="Courier New"><br>
vector len</font><font size=3> <br>
<br>
</font><font size=2 face="Courier New"><br>
-- lists of lists</font><font size=3> </font><font size=2 face="Courier New"><br>
--genBndLoL :: (Int, Int) -> (Int, Int) -> Gen [[a]]</font><font size=3>
</font><font size=2 face="Courier New"><br>
genBndLoL (min1,max1) (min2,max2) = do</font><font size=3> </font><font size=2 face="Courier New"><br>
len1 <- choose (min1,max1)</font><font size=3> </font><font size=2 face="Courier New"><br>
len2 <- choose (min2,max2)</font><font size=3> </font><font size=2 face="Courier New"><br>
vec2 len1 len2</font><font size=3> <br>
</font><font size=2 face="Courier New"><br>
--vec2 :: Arbitrary a => Int -> Int -> Gen [[a]]</font><font size=3>
</font><font size=2 face="Courier New"><br>
vec2 n m = sequence [ vector m | i <- [1..n] ]</font><font size=3> <br>
<br>
<br>
</font>
<br>
<br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">---</span><br>
<br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">This e-mail may contain confidential and/or privileged information. If you </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">are not the intended recipient (or have received this e-mail in error) </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">please notify the sender immediately and destroy this e-mail. Any </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">unauthorized copying, disclosure or distribution of the material in this </span><br>
<span style="font-family:sans-serif,helvetica; font-size:10pt; color:#000000">e-mail is strictly forbidden.</span><br>