``` 51fcd0bb » epsilonhalbe ``` 2012-05-24 begun the famous 99-haskell-problems 1 module HP1120 where 2 import Data.List (group) 3 import Control.Arrow (first, 4 (&&&)) 5 6 data Count a = Single a 7 | Multiple Int a 8 deriving (Eq, Show) 9 10 encode :: String -> [(Int, Char)] 11 encode = map (length &&& head) . group 12 13 encodeModified :: String -> [Count Char] 14 encodeModified = map transform . encode 15 16 transform :: (Int,Char) -> Count Char 17 transform (1,x) = Single x 18 transform (i,x) = Multiple i x 19 20 decodeModified :: [Count Char] -> String 21 decodeModified = concatMap stringify 22 23 stringify :: Count Char -> String 24 stringify (Single x) = [x] 25 stringify (Multiple i x) = replicate i x 26 27 (.+.) :: Count Char -> [Count Char] -> [Count Char] 28 x .+. [] = [x] 29 y@(Single x2) .+. xx@(Single x1:xs) | x1 == x2 = Multiple 2 x1:xs 30 | otherwise = y:xx 31 y@(Single x2 ) .+. xx@(Multiple i1 x1:xs) | x1 == x2 = Multiple (i1+ 1) x1:xs 32 | otherwise = y:xx 33 y@(Multiple i2 x2) .+. xx@(Single x1:xs) | x1 == x2 = Multiple (1 +i2) x1:xs 34 | otherwise = y:xx 35 y@(Multiple i2 x2 ) .+. xx@(Multiple i1 x1:xs) | x1 == x2 = Multiple (i1+i2) x1:xs 36 | otherwise = y:xx 37 38 encodeDirect :: String -> [Count Char] 39 -- encodeDirect = foldr (.+.) [] . map transform . zip (repeat 1) 40 encodeDirect = foldr ((.+.) . transform) [] . zip (repeat 1) 41 42 dupli :: [a] -> [a] 43 dupli = foldr (\x y -> x:x:y) [] 44 45 repli :: [a] -> Int -> [a] 46 repli xx i = foldr (\x y -> replicate i x++y) [] xx 47 48 dropEvery :: [a] -> Int -> [a] 49 dropEvery xx 0 = xx 50 dropEvery xx i = _dropEvery xx i 51 where _dropEvery [] _ = [] 52 _dropEvery (x:xs) 1 = _dropEvery xs i 53 _dropEvery (x:xs) n = x:_dropEvery xs (n-1) 54 55 split :: [a] -> Int -> ([a],[a]) 56 split x 0 = ([],x) 57 split x i | i < 0 = split x (length x + i) 58 | otherwise = _split ([],x) i 59 where _split xx 0 = xx 60 _split (y,x:xs) i = _split (y++[x],xs) (i-1) 61 62 slice :: [a] -> Int -> Int -> [a] 63 slice xx i1 i2 = [x| (x,i)<- zip xx [1..], i1<=i,i<=i2] 64 65 rotate :: [a] -> Int -> [a] 66 rotate x i = bb++aa 67 where (aa,bb) = split x i 68 69 removeAt :: Int -> [a] -> (a,[a]) 70 removeAt i x | i<0 = (b,aa++bs) 71 where (aa,b:bs) = split x i 72 removeAt i x = (head a,as++bb) 73 where (aa,bb) = split x (i+1) 74 (as,a ) = split aa (-1) 75 76