Compression reverse Haskell

Question

I have this function where i compress a string

compression :: String -> [(Char,Int)]
compression str = map (\lt -> (head lt, length lt)) (group str)

I've tried to edit this into it's reverse

EXAMPLE:

revcompression [('a', 2), ('b', 3), ('c', 4), ('b', 1)] ==  "aabbbccccb"

Can anyone edit the first one into the reverse?

You should show what you've tried and where you're stuck. See [How do I ask and answer homework questions?](https://meta.stackoverflow.com/q/334822) — Brian McCutchon, Nov 30 '20 at 20:00
@NoNameDRR if your problem is solved, please accept an answer. — rethab, Dec 03 '20 at 19:27

rethab · Answer 1 · 2020-11-30T17:29:52.797

3

This is without recursion:

decompress :: [(Char,Int)] -> String
decompress xs = concat $ map (\(c, n) -> replicate n c) xs

Or using >>=:

decompress :: [(Char,Int)] -> String
decompress xs = xs >>= (\(c, n) -> replicate n c)

Or point-free:

decompress :: [(Char,Int)] -> String
decompress = flip (>>=) (uncurry replicate . swap)
  where swap (a, b) = (b,a)

Or with the imports suggested in the comments:

import Control.Monad ((=<<))
import Data.Tuple (swap)

decompress :: [(Char,Int)] -> String
decompress = (=<<) (uncurry replicate . swap)

the joys of haskell :)

edited Nov 30 '20 at 17:29

answered Nov 30 '20 at 14:19

rethab

7,170
29
46

Note that `swap` is already defined in `Data.Tuple`. – chepner Nov 30 '20 at 17:08
And `(=<<) == flip (>>=)` is defined in `Control.Monad`. – chepner Nov 30 '20 at 17:10
we can use `(uncurry (flip replicate) =<<)` – Willem Van Onsem Nov 30 '20 at 17:22

score 1 · Answer 2 · answered Nov 30 '20 at 13:55

1

This can be done with recursion using the replicate function, which will repeat an element a certain number of times:

decompress :: [(Char, Int)] -> String
decompress [] = ... -- what should you get when you decompress the empty array?
decompress ((c, n):xs) = replicate n c ++ ... -- hint: you'll want to have a recursive call

Where the ... is something you need to fill in.

answered Nov 30 '20 at 13:55

Aplet123

33,825
1
29
55

Thanks a lot but i need without recursion, only map filter zipWith etc... – NoNameDRR Nov 30 '20 at 14:00

score 0 · Answer 3 · answered Nov 30 '20 at 18:04

Jut play with some example data, and generalize:

compressed str = map (\lt -> (head lt, length lt)) (group str)

compressed [a,a,a,b,b,b,c,d,d,a] =
  = map (head &&& length) [ [a,a,a], [b,b,b], [c], [d,d], [a] ]
  = [ (a, 3), (b, 3), (c, 1), (d, 2), (a, 1)]

uncompressed cs@[ (a, 3), (b, 3), (c, 1), (d, 2), (a, 1)] =
  = concat [ [a,a,a], [b,b,b], [c], [d,d], [a] ]
  = concat [ replicate k x | (x,k) <- cs ]
  = concatMap (uncurry (flip replicate)) cs

Indeed,

> :t concatMap (uncurry (flip replicate))
concatMap (uncurry (flip replicate)) :: [(b, Int)] -> [b]

specdrake · Answer 4 · 2020-11-30T19:55:29.037

compression :: String -> [(Char,Int)]
compression str = map (\lt -> (head lt, length lt)) (group str)

So you basically need a function that reverses the operations done in compression.

The type of that function(say decompression) will be [(Char, Int)] -> String and it will go through a list of tuples and populate a list with the first tuple member the number of times determined by the second tuple member. One simple way to do it would be a fold as follows:

decompression = foldl (\acc (a, n) -> acc ++ (replicate n a)) []

A fold uses recursion implicitly and we are also using a handy function replicate to make our work easier. There are other, perhaps more elegant way to do it in the other answers, I think using a fold is pretty readable and natural.

EDIT : As pointed out by @Will Ness in a comment below. Using ++ in a left associated chain is an antipattern. It's quite inefficient as explained in that answer. So it's better to use foldr instead as it is right-associative.

decompression = foldr (\(a, n) acc -> (replicate n a) ++ acc) []

left-associated `++` chain [is an anti-pattern](https://stackoverflow.com/a/13879693/849891), unfortunately. but you could use `foldr`, then the `++`s would get grouped on the right, and that's OK. — Will Ness, Nov 30 '20 at 19:40

score 0 · Answer 5 · answered Jan 08 '21 at 23:02

You've already been provided with various solutions. I'll try to provide some insight on how to go about finding one such solution. Below we will derive the solution provided by @rethab,

decompress xs = concat $ map (\(c, n) -> replicate n c) xs

or more succinctly,

decompress = concat . map (\(c, n) -> replicate n c)

In what follows we will write f' to denote a left inverse of f, i.e. a function such that f' . f = id. The two following properties hold,

f' . g' is a left inverse of g . f
map f' is a left inverse of map f

The original compress function can be written as,

headLen lt = (head lt, length lt)
compression str = map headLen . group

We are looking for a function decompress = compress'. Given the two properties above, if we have group' and headLen' then a solution would be,

decompression = group' . map headLen'

So we've factored the original problem into two smaller ones. Finding a left inverse of group and a left inverse of headLen. These are rather simple,

group' = concat
headLen' (c, n) = replicate n c

and so we have,

decompression = concat . map (\(c, n) -> replicate n c)

Compression reverse Haskell

5 Answers5