CODEWITHSUNDEEP
haskelltuplesmultiset
simon paul
simon paul

Reputation: 23

string to multi set haskell

Convert string to multi set as the example below:

"bacaba" --> [(b,2),(a,3),(c,1)]

type MSet a = [(a,Int)]

convert :: Eq a => [a] -> MSet

what is wrong with my code and what is the better way to do it? ty

convert :: Eq a => [a] -> MSet a
convert [] = []
convert (x:xs) = ((x,1+count x xs) : converte xs) 
  where count x [] = 0
        count x (y:ys) = if (x == y) then 1 + count x ys else count x ys

Upvotes: 1

Views: 400

Answers (2)

behzad.nouri
behzad.nouri

Reputation: 77951

what is the better way to do it?

Your code performs O(n^2); If the type is an instance of Ord type class (as in your example), using Data.Map you may get an O(n log n) performance:

import Data.Map (toList, fromListWith)

convert :: (Ord a) => [a] -> [(a, Int)]
convert xs = toList . fromListWith (+) . zip xs $ repeat 1

This would result in the right counts but the list would be sorted by the keys:

\> convert "bacaba"
[('a',3),('b',2),('c',1)]

If you need to preserve the order, then 

import qualified Data.Map as M
import Data.Map (delete, fromListWith)

convert :: (Ord a) => [a] -> [(a, Int)]
convert xs = foldr go (const []) xs . fromListWith (+) . zip xs $ repeat 1
    where
    go x f cnt = case M.lookup x cnt of
        Just i  -> (x, i): f (x `delete` cnt)
        Nothing -> f cnt

which would output:

\> convert "bacaba"
[('b',2),('a',3),('c',1)]

Upvotes: 1

Sibi
Sibi

Reputation: 48654

You are almost there.

The problem is with your recursive call to the convert function. Since you have already computed the number of characters for a particular character, you don't need to calculate them again. Just use a filter function to remove that character out while calling to convert:

convert :: Eq a => [a] -> MSet a
convert [] = []
convert (x:xs) = (x,1+count x xs) : convert (filter (\y -> y /= x) xs)
  where count x [] = 0
        count x (y:ys) = if (x == y) then 1 + count x ys else count x ys

Or written more concisely:

convert :: Eq a => [a] -> MSet a
convert [] = []
convert (x:xs) = (x,1+count x xs) : convert (filter (/= x) xs)
  where count x [] = 0
        count x (y:ys) = if (x == y) then 1 + count x ys else count x ys

Demo in ghci:

ghci| > convert "bacaba"
[('b',2),('a',3),('c',1)]

Upvotes: 1

Related Questions