CODEWITHSUNDEEP
haskelltype-constructor
mohammad farhady
mohammad farhady

Reputation: 53

How to convert my own Data constructor to List in Haskell

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?

Upvotes: 1

Views: 791

Answers (3)

radrow
radrow

Reputation: 7129

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.

Upvotes: 2

414owen
414owen

Reputation: 801

@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)

Upvotes: 2

SergeyKuz1001
SergeyKuz1001

Reputation: 875

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

Upvotes: 3

Related Questions