[Haskell-cafe] Suspected stupid Haskell Question
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] I couldn't find anything on a search, or anything in the librarys. Thanks BH. -- View this message in context: http://www.nabble.com/Suspected-stupid-Haskell-Question-tf4639170.html#a13250044 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
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
Re: [Haskell-cafe] Suspected stupid Haskell Question
On 17/10/2007, Big_Ham [EMAIL PROTECTED] wrote: 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] I couldn't find anything on a search, or anything in the librarys. Thanks BH. 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. Cheers, D. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
On 17/10/2007, Dougal Stanton [EMAIL PROTECTED] 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
you are indeed right Peter, that's what I was after, the frequency regardless of elements. It also doesn't matter if it outputs them as tuples, or as a separate list on their own because each value would belong to the first occurance of that element if you seem what I mean, so you could still tell what came from what. Peter Verswyvelen wrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- View this message in context: http://www.nabble.com/Suspected-stupid-Haskell-Question-tf4639170.html#a13251343 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
Dougal Stanton wrote: It's just occurred to me that answering questions like these is a bit like the prisoner's dilemma... There's no way to win! :-) Yes there is. Just mention the following wiki page as part of your answer: http://haskell.org/haskellwiki/Homework_help -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
On 10/17/07, Peter Verswyvelen [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
Peter Verswyvelen wrote: However, I suspect the experts here will be able to make that much shorter and more efficient (maybe using Data.Map?) That makes it difficult to respond. I am definitely not claiming to be an expert. For one thing, my name is not Simon. But I'll say something anyway, fwiw. The problem there is that nub is O(n^2). You're stuck with that if your type is not an instance of Ord (but then you can't use sort, either). When you can assume Ord, the standard solution is, as you suggest, something like: import qualified Data.Map as M import Data.List histogram = M.toList . foldl' (\m x - M.insertWith' (+) x 1 m) M.empty . M.fromList This should work efficiently, with the right amount of laziness, even for very large lists. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
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
Re: [Haskell-cafe] Suspected stupid Haskell Question
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
The problem there is that nub is O(n^2). Is there a place where one can look up the complexity of Standard Libraries functions ? E.D ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
Is there a place where one can look up the complexity of Standard Libraries functions ? No. Some modules have it in their Haddock docs. Most don't. But the source code is available. :) -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Suspected stupid Haskell Question
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
