<br><font size=2 face="sans-serif">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>
<br>
<br><font size=2 face="sans-serif">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>
<br>
<br><font size=2 face="sans-serif">Is there a more scientific way of figuring
out if one version is better than the other by using, say profiling tools?</font>
<br>
<br><font size=2 face="sans-serif">Or by reasoning about the code?</font>
<br>
<br><font size=2 face="sans-serif">t.</font>
<br>
<br><font size=2 face="sans-serif">****************************************</font>
<br>
<br><font size=2 face="Courier New">import Data.List</font>
<br><font size=2 face="Courier New">import qualified Data.Map as M</font>
<br><font size=2 face="Courier New">import Control.Arrow</font>
<br><font size=2 face="Courier New">import Test.QuickCheck</font>
<br><font size=2 face="Courier New">import Test.GenTestData</font>
<br><font size=2 face="Courier New">import System.Random</font>
<br>
<br><font size=2 face="Courier New">{-</font>
<br><font size=2 face="Courier New">Is there a library function to take
a list of Strings and return a list of</font>
<br><font size=2 face="Courier New">ints showing how many times each String
occurs in the list.</font>
<br>
<br><font size=2 face="Courier New">So for example:</font>
<br>
<br><font size=2 face="Courier New">["egg", "egg",
"cheese"] would return [2,1] </font>
<br><font size=2 face="Courier New">-}</font>
<br>
<br><font size=2 face="Courier New">testYitzGale n = do</font>
<br><font size=2 face="Courier New"> l <- rgenBndStrRow (10,10)
(10^n,10^n) -- 100000 strings, strings are 10 chars long, works.
craps out on 10^6.</font>
<br><font size=2 face="Courier New"> m <- return $ freqFold l
</font>
<br><font size=2 face="Courier New"> putStrLn $ "map items:
" ++ ( show $ M.size m )</font>
<br>
<br><font size=2 face="Courier New">testCScherer n = do</font>
<br><font size=2 face="Courier New"> l <- rgenBndStrRow (10,10)
(10^n,10^n) -- same limitations as yitz gale code.</font>
<br><font size=2 face="Courier New"> m <- return $ ordTable l
</font>
<br><font size=2 face="Courier New"> putStrLn $ "items: "
++ ( show $ length m )</font>
<br>
<br>
<br><font size=2 face="Courier New">-- slow for big lists</font>
<br><font size=2 face="Courier New">--freqArr = Prelude.map ( last &&&
length ) . group . sort</font>
<br>
<br><font size=2 face="Courier New">-- yitz gale code. same as chad scherer
code? it's simpler to understand, but is it as fast?</font>
<br><font size=2 face="Courier New">freqFold :: [[Char]] -> M.Map [Char]
Int</font>
<br><font size=2 face="Courier New">freqFold = foldl' g M.empty</font>
<br><font size=2 face="Courier New"> where g accum x = M.insertWith'
(+) x 1 accum</font>
<br><font size=2 face="Courier New">-- c scherer code. insists on ord.
far as I can tell, same speed as yitz.</font>
<br><font size=2 face="Courier New">ordTable :: (Ord a) => [a] ->
[(a,Int)]</font>
<br><font size=2 face="Courier New">ordTable xs = M.assocs $! foldl' f
M.empty xs</font>
<br><font size=2 face="Courier New"> where f m x = let m'
= M.insertWith (+) x 1 m</font>
<br><font size=2 face="Courier New">
Just v = M.lookup x m'</font>
<br><font size=2 face="Courier New">
in v `seq` m'</font>
<br>
<br>
<br><font size=2 face="Courier New">l = ["egg","egg","cheese"]</font>
<br>
<br><font size=2 face="Courier New">-- other quickcheck stuff</font>
<br><font size=2 face="Courier New">--prop_unchanged_by_reverse = \l ->
( freqArr (l :: [[Char]]) ) == ( freqArr $ reverse l )</font>
<br><font size=2 face="Courier New">--prop_freqArr_eq_freqFold = \l ->
( freqArr (l :: [[Char]]) == (freqFold l))</font>
<br><font size=2 face="Courier New">--test1 = quickCheck prop_unchanged_by_reverse</font>
<br><font size=2 face="Courier New">--test2 = quickCheck prop_freqArr_eq_freqFold</font>
<br>
<br><font size=2 face="Courier New">--------------- generate test data:
</font>
<br><font size=2 face="Courier New">genBndStrRow (minCols,maxCols) (minStrLen,
maxStrLen) = rgen ( genBndLoL (minStrLen, maxStrLen) (minCols,maxCols)
)</font>
<br>
<br><font size=2 face="Courier New">gen gen = do</font>
<br><font size=2 face="Courier New"> sg <- newStdGen</font>
<br><font size=2 face="Courier New"> return $ generate 10000 sg gen</font>
<br>
<br><font size=2 face="Courier New">-- generator for a list with length
between min and max</font>
<br><font size=2 face="Courier New">genBndList :: Arbitrary a => (Int,
Int) -> Gen [a]</font>
<br><font size=2 face="Courier New">genBndList (min,max) = do</font>
<br><font size=2 face="Courier New"> len <- choose (min,max)</font>
<br><font size=2 face="Courier New"> vector len</font>
<br>
<br>
<br><font size=2 face="Courier New">-- lists of lists</font>
<br><font size=2 face="Courier New">--genBndLoL :: (Int, Int) -> (Int,
Int) -> Gen [[a]]</font>
<br><font size=2 face="Courier New">genBndLoL (min1,max1) (min2,max2) =
do</font>
<br><font size=2 face="Courier New"> len1 <- choose (min1,max1)</font>
<br><font size=2 face="Courier New"> len2 <- choose (min2,max2)</font>
<br><font size=2 face="Courier New"> vec2 len1 len2</font>
<br>
<br><font size=2 face="Courier New">--vec2 :: Arbitrary a => Int ->
Int -> Gen [[a]]</font>
<br><font size=2 face="Courier New">vec2 n m = sequence [ vector m | i
<- [1..n] ]</font>
<br>
<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>
<br><font size=1 face="sans-serif">Sent by: haskell-cafe-bounces@haskell.org</font>
<p><font size=1 face="sans-serif">10/17/2007 01:35 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">haskell-cafe@haskell.org</font>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">cc</font></div>
<td>
<tr valign=top>
<td>
<div align=right><font size=1 face="sans-serif">Subject</font></div>
<td><font size=1 face="sans-serif">[Haskell-cafe] Re: Suspected stupid
Haskell Question</font></table>
<br>
<table>
<tr valign=top>
<td>
<td></table>
<br></table>
<br>
<br>
<br><tt><font size=2>Big_Ham <joymachine2001 <at> hotmail.com>
writes:<br>
<br>
> <br>
> <br>
> Is there a library function to take a list of Strings and return a
list of<br>
> ints showing how many times each String occurs in the list.<br>
> <br>
> So for example:<br>
> <br>
> ["egg", "egg", "cheese"] would return
[2,1]<br>
> <br>
> I couldn't find anything on a search, or anything in the librarys.<br>
> <br>
> Thanks BH.<br>
<br>
Hi BH,<br>
<br>
This might be overkill, but it works well for me. And it avoid stack overflows
I<br>
was originally getting for very large lists. Dean Herrington and I came
up with<br>
this:<br>
<br>
ordTable :: (Ord a) => [a] -> [(a,Int)]<br>
ordTable xs = Map.assocs $! foldl' f Map.empty xs<br>
where f m x = let m' = Map.insertWith (+) x 1 m<br>
Just v = Map.lookup x m'<br>
in v `seq`
m'<br>
<br>
intTable :: [Int] -> [(Int,Int)]<br>
intTable xs = IntMap.assocs $! foldl' f IntMap.empty xs<br>
where f m x = let m' = IntMap.insertWith (+) x 1 m<br>
Just v = IntMap.lookup x m'<br>
in v `seq`
m'<br>
<br>
enumTable :: (Enum a) => [a] -> [(a,Int)]<br>
enumTable = map fstToEnum . intTable . map fromEnum<br>
where fstToEnum (x,y) = (toEnum x, y)<br>
<br>
If you like, it's easily wrapped in a Table class.<br>
<br>
Chad<br>
<br>
<br>
<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
Haskell-Cafe@haskell.org<br>
http://www.haskell.org/mailman/listinfo/haskell-cafe<br>
</font></tt>
<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>