Using Bag in Haskell

Question

I've been tasked with creating a Haskell program that contains a definition for a polymorphic datatype Bag and some simple functions, such as, converting a list to a bag and checking if two bags are the same.

My problem is I'm new to Haskell, so I'm not sure how to use Bags. Can anyone point me in the direction of some resources to do with Bags?

Answer 1

• You can start by reading about algebraic data types.
• First try to implement a simple algebraic data type like tree and then you can go and implement your own Bag data type. If you have any problems you can always ask here.
• If this is not a homework then you can use already implemented Bags or use Data.Map to implement the same.

I have given the definition using Data.Map to compare your implementation which I suppose you would be writing using your own algebraic data types.

import qualified Data.Map as M
import Data.Map (Map)

newtype Bag a = Bag (Map a Int)
    deriving (Show,Eq)

empty :: Bag a
empty = Bag $ M.empty

singleton :: a -> Bag a
singleton a = Bag $ M.singleton a 1

fromList :: (Ord a) => [a] -> Bag a
fromList = foldl f empty
    where
        f (Bag map) x = Bag $ M.insertWith (+) x 1 map

toList :: Bag a -> [a]
toList (Bag m) = concatMap f $ M.toList m
    where f (a,b) = replicate b a

I have defined some very basic functions, but you can do things which you asked and a lot more, like

*Main> let x = fromList [1,2,3,2,2,1]
*Main> x
Bag (fromList [(1,2),(2,3),(3,1)])
*Main> let y = fromList [1,1,2,2,2,3]
*Main> y
Bag (fromList [(1,2),(2,3),(3,1)])
*Main> x==y
True