How to convert my own Data constructor to List in Haskell

Question

I have just started trying Haskell after using Python, and I'm facing a lot of problems understanding it

for example after I tried to make a new type called ListBag and writing a simple function to convert list to ListBag I can't go back and do anything with that data:

data ListBag a = LB [(a,Int)] deriving (Show,Eq)

fromList :: (Ord a) => [a] ->ListBag a
fromList xs = LB [ y| y<- ys]
            where ys = toList(fromListWith (+) [(x, 1) | x <- xs])

a :: [Integer]
a=[1,1,1,1,1,1,2,2,2,3,3,3,3,4,5,5]
b = fromList a

Now b is:

LB [(1,6),(2,3),(3,4),(4,1),(5,2)]

and because b is b :: ListBag Integer it can't be mapped or ... So how can I convert it to List again?

Answer 1

Firstly, your ListBag doesn't save order in which elements was in initial list, but... you can convert ListBag a to [a] like so:

toList :: ListBag a -> [a]
toList (LB ys) = concat $ (\(y, n) -> replicate n y) <$> ys

---

And you can redefine your fromList as

fromList xs = LB $ toList $ fromListWith (+) [ (x, 1) | x <- xs]

Because [ y | y <- ys] ~ ys and x where x = y ~ y

Answer 2

Ahh, monads

toList :: ListBag a -> [a]
toList (LB l) = do
  (what, howmany) <- l
  replicate howmany what

Or if you like list comprehensions:

toList (LB l) =
  [x | (what, howmany) <- l, x <- replicate howmany what] 

The trick is to make use of the fact that a monadic bind on lists can put arbitrary number of things in place of each element. So for every pair (what, howmany) we output howmany number of whats.

This isn't much different from the SergeyKuz1001's solution, just a different style. Due to optimizations I believe the performance ist rather the same in all versions.

Answer 3

@SergeyKuz1001's answer is excellent. When you're ready to take it up a notch, you can use List's Monad instance, and a few combinators to make toList very concise.

toList :: ListBag a -> [a]
toList (LB ys) = ys >>= uncurry (flip replicate)