Creating a bag/multiset from a list

user_14324482 0
Viewed 228

This has got to be super easy and I'm missing something. I cant for the life of me think about how to do this. I need to create a bag from a list. I tried:

ins n [] = [(n,1)]
ins n ((x,y):xys)
  |n == x    = (x, y + 1):xys
  |otherwise = (x,y): ins x xys

fromList [] = []
fromList (x:xs) = ins x [] : bag xs

This obviously doesnt work as intended and the recursion is working against me here. The insert function does actually work, but I cant figure out how to keep adding to the same list instead of what Im doing

Edit: probably should have been far more specific, apologies. Bag would be the data type where Bag a = [(element, number of occurrences in list)] Possibly also known as multiset. So the list [2,2,3,4,2,3], would become [(2,3),(3,2),(4,1)]

I'm very new to Haskell and programming in general so I apologize again for being abstract about it.

haskell
1 Answers

You've almost got it. What you probably want is:

fromList [] = []
fromList (x:xs) = ins x (fromList xs)

If you look at the types, it is easier to see what went wrong. In the fixed version:

ins :: (Eq a, Num b) => a -> [(a,b)] -> [(a,b)]
fromList :: (Eq a, Num b) => [a] -> [(a,b)]

In the original version of fromList, you should get an error because bag is undefined; but assuming you meant:

fromList [] = []
fromList (x:xs) = ins x [] : fromList xs

the inferred type will be:

fromList :: (Eq a, Num b) => [a] -> [[(a,b)]]

Rather than returning the bag type [(a,b)], it returns a list of bags, [[(a,b)]].

What this version is actually doing is wrapping each element as a singleton bag; basically the same as map (\ x -> ins x []).

comingstorm_2102110
Related