Personal tools

99 questions/Solutions/10

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
m
Line 32: Line 32:
 
encode xs = (enc . pack) xs
 
encode xs = (enc . pack) xs
 
where enc = foldr (\x acc -> (length x, head x) : acc) []
 
where enc = foldr (\x acc -> (length x, head x) : acc) []
  +
</haskell>
  +
  +
Or using takeWhile and dropWhile:
  +
  +
<haskell>
  +
encode [] = []
  +
encode (x:xs) = (length $ x : takeWhile (==x) xs, x) : encode (dropWhile (==x) xs)
 
</haskell>
 
</haskell>

Revision as of 14:56, 9 April 2011

(*) Run-length encoding of a list.

Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

encode xs = map (\x -> (length x,head x)) (group xs)

which can also be expressed as a list comprehension:

[(length x, head x) | x <- group xs]

Or writing it Pointfree (Note that the type signature is essential here to avoid hitting the Monomorphism Restriction):

encode :: Eq a => [a] -> [(Int, a)]
encode = map (\x -> (length x, head x)) . group

Or (ab)using the "&&&" arrow operator for tuples:

encode :: Eq a => [a] -> [(Int, a)]
encode xs = map (length &&& head) $ group xs

Or with the help of foldr (pack is the resulting function from P09):

encode xs = (enc . pack) xs
	where enc = foldr (\x acc -> (length x, head x) : acc) []

Or using takeWhile and dropWhile:

encode [] = []
encode (x:xs) = (length $ x : takeWhile (==x) xs, x) : encode (dropWhile (==x) xs)