88 lines
2.2 KiB
Haskell
88 lines
2.2 KiB
Haskell
stepAux :: Eq a => a -> [a] -> [a]
|
|
stepAux a (x:xs)
|
|
| a==x = a:stepAux a xs
|
|
| otherwise = []
|
|
stepAux a [] = []
|
|
|
|
|
|
-- returns: (result, remaining)
|
|
step :: Eq a => a -> [a] -> ([a], [a])
|
|
step a l =
|
|
let rv = stepAux a l in
|
|
(a:rv, drop (length rv) l)
|
|
|
|
|
|
pack :: Eq a => [a] -> [[a]]
|
|
pack [] = []
|
|
pack (x:xs) =
|
|
let (res, rem) = step x xs in
|
|
case rem of
|
|
[] -> [res]
|
|
_ -> res:pack rem
|
|
|
|
-- Test case of 9:
|
|
-- λ> pack ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
|
|
-- ["aaaa","b","cc","aa","d","eeee"]
|
|
|
|
encode :: Eq a => [a] -> [(Int, a)]
|
|
encode l = map (\x -> (length x, head x)) $ pack l
|
|
|
|
-- Test case of 10:
|
|
-- λ> encode "aaaabccaadeeee"
|
|
-- [(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]
|
|
|
|
encodeMod :: Eq a => [a] -> [(Int, a)]
|
|
encodeMod l = foldr f [] $ pack l where
|
|
f x acc =
|
|
if length x/=1 then (length x, head x):acc
|
|
else acc
|
|
-- Test case of 11 (v1):
|
|
-- λ> encodeMod "aaaabccaadeeee"
|
|
-- [(4,'a'),(2,'c'),(2,'a'),(4,'e')]
|
|
|
|
data Multiplicity a
|
|
= Single a
|
|
| Multiple Int a
|
|
deriving Show
|
|
|
|
encodeMod' :: Eq a => [a] -> [Multiplicity a]
|
|
encodeMod' l = foldr f [] $ pack l where
|
|
f x acc =
|
|
if length x/=1 then (Multiple (length x) (head x)):acc
|
|
else (Single (head x)):acc
|
|
-- Test case of 11 (v2):
|
|
-- λ> encodeMod' "aaaabccaadeeee"
|
|
-- [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
|
|
|
|
|
|
decode :: [Multiplicity a] -> [a]
|
|
decode l = foldr f [] l where
|
|
f (Single a) acc = a:acc
|
|
f (Multiple n a) acc = (replicate n a) ++ acc
|
|
|
|
-- Test case of 12:
|
|
-- λ> decode (encodeMod' "aaaabccaadeeee")
|
|
-- "aaaabccaadeeee"
|
|
--
|
|
-- λ> decode (encodeMod' "aaaabccaadeeee") == "aaaabccaadeeee"
|
|
-- True
|
|
|
|
|
|
encodeDirectAux :: Eq a => a -> [a] -> Int
|
|
encodeDirectAux a [] = 0
|
|
encodeDirectAux a (x:xs)
|
|
| x==a = 1 + (encodeDirectAux a xs)
|
|
| otherwise = 0
|
|
|
|
encodeDirect :: Eq a => [a] -> [Multiplicity a]
|
|
encodeDirect [] = []
|
|
encodeDirect (x:xs) =
|
|
let rv = encodeDirectAux x xs in
|
|
case rv of
|
|
0 -> (Single x):encodeDirect xs
|
|
_ -> Multiple (rv+1) x : encodeDirect (drop rv xs)
|
|
|
|
-- Test case of 13:
|
|
-- λ> encodeDirect "aaaabccaadeeee"
|
|
-- [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
|