I'm a newbie here, so I'm not sure about my reply, but I think this is not the answer to his question. freq ["egg", "egg", "cheese"] indeed returns [2,1] but freq ["egg", "cheese", "egg"] returns [1,1,1] BH just mentioned he needed the frequenty of elements in the list, independent of their order. So in that case, the result should be a list of ordered pairs like: [("egg", 2), ("cheese", 1)]. Or a pair of two lists, like (["egg", "cheese"), (2,1)]. Otherwise you would not know which frequency belongs to which element? I can't write this concisely nor efficient yet, but the following does the job: import Data.List freq xs = zip e f where s = sort xs e = nub s f = map length (group s) However, I suspect the experts here will be able to make that much shorter and more efficient (maybe using Data.Map?) Peter Stefan Holdermans wrote:

BH,

...

Is there a library function to take a list of Strings and return a list of ints showing how many times each String occurs in the list.

So for example:

["egg", "egg", "cheese"] would return [2,1]

freq xs = map length (group xs)

HTH,

Stefan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 10/17/07, Peter Verswyvelen wrote:

So in that case, the result should be a list of ordered pairs like: [("egg", 2), ("cheese", 1)]. Or a pair of two lists, like (["egg", "cheese"), (2,1)]. Otherwise you would not know which frequency belongs to which element?

However, I suspect the experts here will be able to make that much shorter and more efficient (maybe using Data.Map?)

import Control.Arrow import Data.List freqs = map (head &&& length) . group . sort I have used this function quite a few times already. Stuart

Oh, why didn't you say you were learning Arrows? Then why not freqs = sort >>> group >>> map (head &&& length) So much more readable, don't you think? ;) Either way, if you run into the dreaded monomorphism restriction: Ambiguous type variable `a' in the constraint: `Ord a' arising from use of `sort' at A.hs:6:40-43 Possible cause: the monomorphism restriction applied to the following: freqs :: [a] -> [(a, Int)] (bound at A.hs:6:0) Probable fix: give these definition(s) an explicit type signature or use -fno-monomorphism-restriction you'll have to either add an explicit type annotation: freqs :: (Ord a) => [a] -> [(a, Int)] or else throw an arg onto it: freqs x = map (head &&& length) . group . sort $ x The latter hurts too much to write, so I always add the type. Peter Verswyvelen wrote:

Nice!!! As I'm learning Arrows now, this is really useful :-)

Stuart Cook wrote:

...

import Control.Arrow import Data.List

freqs = map (head &&& length) . group . sort

I have used this function quite a few times already.

Stuart _______________________________________________ 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

I wrote:

When you can assume Ord, the standard solution is, as you suggest, something like...

Oops, sorry, doesn't typecheck. Here it is corrected:

import qualified Data.Map as M import Data.List

histogram = M.toList . foldl' (\m x -> M.insertWith' (+) x 1 m) M.empty

This should work efficiently, with the right amount of laziness, even for very large lists.

Stuart's Arrows thing is much nicer when your list is small enough to be held in memory all at once. -Yitz

On 17/10/2007, Dougal Stanton wrote:

No, but it is also trivial to create, with the 'group' function in Data.List. I'll stop there though, cos this could be a homework question.

It's just occurred to me that answering questions like these is a bit like the prisoner's dilemma. - If I give the full answer and no-one else does, then maybe I'm doing someone's homework for them? - If I just give clues and someone else gives the answer, it makes me look mean. :-( - If we all give the answer, everybody's happy and the blame (if it was a set question) is spread around a bit. - If we all answer with vague hints then it makes the list as a whole less useful and seem a bit arrogant. There's no way to win! :-) D.

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). Chad On 10/17/07, Thomas Hartman wrote:

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.

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.

Is there a more scientific way of figuring out if one version is better than the other by using, say profiling tools?

Or by reasoning about the code?

t.

****************************************

import Data.List import qualified Data.Map as M import Control.Arrow import Test.QuickCheck import Test.GenTestData import System.Random

{- Is there a library function to take a list of Strings and return a list of ints showing how many times each String occurs in the list.

So for example:

["egg", "egg", "cheese"] would return [2,1] -}

testYitzGale n = do l <- rgenBndStrRow (10,10) (10^n,10^n) -- 100000 strings, strings are 10 chars long, works. craps out on 10^6. m <- return $ freqFold l putStrLn $ "map items: " ++ ( show $ M.size m )

testCScherer n = do l <- rgenBndStrRow (10,10) (10^n,10^n) -- same limitations as yitz gale code. m <- return $ ordTable l putStrLn $ "items: " ++ ( show $ length m )

-- slow for big lists --freqArr = Prelude.map ( last &&& length ) . group . sort

-- yitz gale code. same as chad scherer code? it's simpler to understand, but is it as fast? freqFold :: [[Char]] -> M.Map [Char] Int freqFold = foldl' g M.empty where g accum x = M.insertWith' (+) x 1 accum -- c scherer code. insists on ord. far as I can tell, same speed as yitz. ordTable :: (Ord a) => [a] -> [(a,Int)] ordTable xs = M.assocs $! foldl' f M.empty xs where f m x = let m' = M.insertWith (+) x 1 m Just v = M.lookup x m' in v `seq` m'

l = ["egg","egg","cheese"]

-- other quickcheck stuff --prop_unchanged_by_reverse = \l -> ( freqArr (l :: [[Char]]) ) == ( freqArr $ reverse l ) --prop_freqArr_eq_freqFold = \l -> ( freqArr (l :: [[Char]]) == (freqFold l)) --test1 = quickCheck prop_unchanged_by_reverse --test2 = quickCheck prop_freqArr_eq_freqFold

--------------- generate test data: genBndStrRow (minCols,maxCols) (minStrLen, maxStrLen) = rgen ( genBndLoL (minStrLen, maxStrLen) (minCols,maxCols) )

gen gen = do sg <- newStdGen return $ generate 10000 sg gen

-- generator for a list with length between min and max genBndList :: Arbitrary a => (Int, Int) -> Gen [a] genBndList (min,max) = do len <- choose (min,max) vector len

-- lists of lists --genBndLoL :: (Int, Int) -> (Int, Int) -> Gen [[a]] genBndLoL (min1,max1) (min2,max2) = do len1 <- choose (min1,max1) len2 <- choose (min2,max2) vec2 len1 len2

--vec2 :: Arbitrary a => Int -> Int -> Gen [[a]] vec2 n m = sequence [ vector m | i <- [1..n] ]

But I would expect intTable to be faster,

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. t. "Chad Scherrer" 10/17/2007 11:38 PM To Thomas Hartman/ext/dbcom@DBAmericas cc haskell-cafe@haskell.org, haskell-cafe-bounces@haskell.org Subject Re: [Haskell-cafe] Re: Suspected stupid Haskell Question 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). Chad On 10/17/07, Thomas Hartman < thomas.hartman@db.com> wrote: 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. 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. Is there a more scientific way of figuring out if one version is better than the other by using, say profiling tools? Or by reasoning about the code? t. **************************************** import Data.List import qualified Data.Map as M import Control.Arrow import Test.QuickCheck import Test.GenTestData import System.Random {- Is there a library function to take a list of Strings and return a list of ints showing how many times each String occurs in the list. So for example: ["egg", "egg", "cheese"] would return [2,1] -} testYitzGale n = do l <- rgenBndStrRow (10,10) (10^n,10^n) -- 100000 strings, strings are 10 chars long, works. craps out on 10^6. m <- return $ freqFold l putStrLn $ "map items: " ++ ( show $ M.size m ) testCScherer n = do l <- rgenBndStrRow (10,10) (10^n,10^n) -- same limitations as yitz gale code. m <- return $ ordTable l putStrLn $ "items: " ++ ( show $ length m ) -- slow for big lists --freqArr = Prelude.map ( last &&& length ) . group . sort -- yitz gale code. same as chad scherer code? it's simpler to understand, but is it as fast? freqFold :: [[Char]] -> M.Map [Char] Int freqFold = foldl' g M.empty where g accum x = M.insertWith' (+) x 1 accum -- c scherer code. insists on ord. far as I can tell, same speed as yitz. ordTable :: (Ord a) => [a] -> [(a,Int)] ordTable xs = M.assocs $! foldl' f M.empty xs where f m x = let m' = M.insertWith (+) x 1 m Just v = M.lookup x m' in v `seq` m' l = ["egg","egg","cheese"] -- other quickcheck stuff --prop_unchanged_by_reverse = \l -> ( freqArr (l :: [[Char]]) ) == ( freqArr $ reverse l ) --prop_freqArr_eq_freqFold = \l -> ( freqArr (l :: [[Char]]) == (freqFold l)) --test1 = quickCheck prop_unchanged_by_reverse --test2 = quickCheck prop_freqArr_eq_freqFold --------------- generate test data: genBndStrRow (minCols,maxCols) (minStrLen, maxStrLen) = rgen ( genBndLoL (minStrLen, maxStrLen) (minCols,maxCols) ) gen gen = do sg <- newStdGen return $ generate 10000 sg gen -- generator for a list with length between min and max genBndList :: Arbitrary a => (Int, Int) -> Gen [a] genBndList (min,max) = do len <- choose (min,max) vector len -- lists of lists --genBndLoL :: (Int, Int) -> (Int, Int) -> Gen [[a]] genBndLoL (min1,max1) (min2,max2) = do len1 <- choose (min1,max1) len2 <- choose (min2,max2) vec2 len1 len2 --vec2 :: Arbitrary a => Int -> Int -> Gen [[a]] vec2 n m = sequence [ vector m | i <- [1..n] ] --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

Thomas Hartman wrote:

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.

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.

Is there a more scientific way of figuring out if one version is better than the other by using, say profiling tools?

Or by reasoning about the code?

It can be reasoned. Some people know how to do it. No one has written up the method and theory properly. It is currently rather ad hoc. I want to write one in the future. Some of the knowledge is in: http://www.haskell.org/haskellwiki/Stack_overflow http://en.wikibooks.org/wiki/Haskell (Advanced Track, Haskell Performance) Richard Bird's "Introduction to Functional Programming using Haskell", second edition (chapter 7 "Efficiency", but also other chapters contain efficiency discussions) anything that adequately defines lazy evaluation (or whatever evaluation your favourite executor seems to use)