Difference between revisions of "99 questions/11 to 20"
(added foldr solution to problem 14)
|Line 126:||Line 126:|
== Problem 15 ==
== Problem 15 ==
Revision as of 09:36, 24 April 2008
(*) Modified run-length encoding. Modify the result of problem 10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.
Example: * (encode-modified '(a a a a b c c a a d e e e e)) ((4 A) B (2 C) (2 A) D (4 E)) Example in Haskell: P11> encodeModified "aaaabccaadeeee" [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
data ListItem a = Single a | Multiple Int a deriving (Show) encodeModified :: Eq a => [a] -> [ListItem a] encodeModified = map encodeHelper . encode where encodeHelper (1,x) = Single x encodeHelper (n,x) = Multiple n x
Again, like in problem 7, we need a utility type because lists in haskell are homogeneous. Afterwards we use the
encode function from problem 10 and map single instances of a list item to
Single and multiple ones to
The ListItem definition contains 'deriving (Show)' so that we can get interactive output.
(**) Decode a run-length encoded list. Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.
Example in Haskell: P12> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e'] "aaaabccaadeeee"
decodeModified :: [ListItem a] -> [a] decodeModified = concatMap decodeHelper where decodeHelper (Single x) = [x] decodeHelper (Multiple n x) = replicate n x
We only need to map single instances of an element to a list containing only one element and multiple ones to a list containing the specified number of elements and concatenate these lists.
(**) Run-length encoding of a list (direct solution). Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.
Example: * (encode-direct '(a a a a b c c a a d e e e e)) ((4 A) B (2 C) (2 A) D (4 E)) Example in Haskell: P13> encodeDirect "aaaabccaadeeee" [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
encode' :: Eq a => [a] -> [(Int,a)] encode' = foldr helper  where helper x  = [(1,x)] helper x (y:ys) | x == snd y = (1+fst y,x):ys | otherwise = (1,x):y:ys encodeDirect :: Eq a => [a] -> [ListItem a] encodeDirect = map encodeHelper . encode' where encodeHelper (1,x) = Single x encodeHelper (n,x) = Multiple n x
First of all we could rewrite the function
encode from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using
foldr) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function
encodeModified from problem 11 to use
(*) Duplicate the elements of a list.
Example: * (dupli '(a b c c d)) (A A B B C C C C D D) Example in Haskell: > dupli [1, 2, 3] [1,1,2,2,3,3]
dupli  =  dupli (x:xs) = x:x:dupli xs
or, using list comprehension syntax:
dupli list = concat [[x,x] | x <- list]
or, using the list monad:
dupli xs = xs >>= (\x -> [x,x])
or, using concatMap:
dupli = concatMap (\x -> [x,x])
or, using foldr:
dupli = foldr (\ x xs -> x : x : xs) 
(**) Replicate the elements of a list a given number of times.
Example: * (repli '(a b c) 3) (A A A B B B C C C) Example in Haskell: > repli "abc" 3 "aaabbbccc"
repli :: [a] -> Int -> [a] repli xs n = concatMap (replicate n) xs
(**) Drop every N'th element from a list.
Example: * (drop '(a b c d e f g h i k) 3) (A B D E G H K) Example in Haskell: *Main> dropEvery "abcdefghik" 3 "abdeghk"
An iterative solution:
dropEvery :: [a] -> Int -> [a] dropEvery  _ =  dropEvery (x:xs) n = dropEvery' (x:xs) n 1 where dropEvery' (x:xs) n i = (if (n `divides` i) then  else [x]) ++ (dropEvery' xs n (i+1)) dropEvery'  _ _ =  divides x y = y `mod` x == 0
or an alternative iterative solution:
dropEvery :: [a] -> Int -> [a] dropEvery list count = helper list count count where helper  _ _ =  helper (x:xs) count 1 = helper xs count count helper (x:xs) count n = x : (helper xs count (n - 1))
or using zip:
dropEvery n = map snd . filter ((n/=) . fst) . zip (cycle [1..n])
(*) Split a list into two parts; the length of the first part is given.
Do not use any predefined predicates.
Example: * (split '(a b c d e f g h i k) 3) ( (A B C) (D E F G H I K)) Example in Haskell: *Main> split "abcdefghik" 3 ("abc", "defghik")
Solution using take and drop:
split xs n = (take n xs, drop n xs)
Alternatively, we have the following recursive solution:
split :: [a] -> Int -> ([a], [a]) split  _ = (, ) split l@(x : xs) n | n > 0 = (x : fst splitSub, snd splitSub) | otherwise = (, l) where splitSub = split xs (n - 1)
Note that this function, with the parameters in the other order, exists as
(**) Extract a slice from a list.
Given two indices, i and k, the slice is the list containing the elements between the i'th and k'th element of the original list (both limits included). Start counting the elements with 1.
Example: * (slice '(a b c d e f g h i k) 3 7) (C D E F G) Example in Haskell: *Main> slice ['a','b','c','d','e','f','g','h','i','k'] 3 7 "cdefg"
slice xs (i+1) k = take (k-i) $ drop i xs
(**) Rotate a list N places to the left.
Hint: Use the predefined functions length and (++).
Examples: * (rotate '(a b c d e f g h) 3) (D E F G H A B C) * (rotate '(a b c d e f g h) -2) (G H A B C D E F) Examples in Haskell: *Main> rotate ['a','b','c','d','e','f','g','h'] 3 "defghabc" *Main> rotate ['a','b','c','d','e','f','g','h'] (-2) "ghabcdef"
rotate  _ =  rotate l 0 = l rotate (x:xs) (n+1) = rotate (xs ++ [x]) n rotate l n = rotate l (length l + n)
There are two separate cases:
- If n > 0, move the first element to the end of the list n times.
- If n < 0, convert the problem to the equivalent problem for n > 0 by adding the list's length to n.
or using cycle:
rotate xs n = take len . drop (n `mod` len) . cycle $ xs where len = length xs
rotate xs n = if n >= 0 then drop n xs ++ take n xs else let l = ((length xs) + n) in drop l xs ++ take l xs
rotate xs n = drop nn xs ++ take nn xs where nn = n `mod` length xs
(*) Remove the K'th element from a list.
Example in Prolog:
?- remove_at(X,[a,b,c,d],2,R). X = b R = [a,c,d]
Example in Lisp:
* (remove-at '(a b c d) 2) (A C D)
(Note that this only returns the residue list, while the Prolog version also returns the deleted element.)
Example in Haskell:
*Main> removeAt 1 "abcd" ('b',"acd")
removeAt :: Int -> [a] -> (a, [a]) removeAt k xs = case back of  -> error "removeAt: index too large" x:rest -> (x, front ++ rest) where (front, back) = splitAt k xs
Simply use the
splitAt to split after k elements.
If the original list has fewer than k+1 elements, the second list will be empty, and there will be no element to extract.
Note that the Prolog and Lisp versions treat 1 as the first element in the list, and the Lisp version appends NIL elements to the end of the list if k is greater than the list length.
removeAt n xs = (xs!!n,take n xs ++ drop (n+1) xs)