Haskell/Solutions/More about lists
Write the following functions and test them out. Don't forget the type signatures.
takeInt :: Int -> [a] -> [a] takeInt 0 _ =  takeInt _  =  takeInt n (x:xs) = x : takeInt (n-1) xs
dropInt :: Int -> [a] -> [a] dropInt 0 list = list dropInt _  =  dropInt n (x:xs) = dropInt (n-1) xs
sumInt :: [Int] -> Int sumInt  = 0 sumInt (x:xs) = x + sumInt xs
--------- USING Helper function ----------- scanSum :: [Int] -> [Int] scanSum = scanSum' 0 scanSum' :: Int -> [Int] -> [Int] scanSum' tot  =  scanSum' tot (x:xs) = x + tot : scanSum' (x + tot) xs ---- USING takeInt, dropInt and sumInt ---- scanSum :: [Int] -> [Int] scanSum  =  scanSum (x:) = [x] scanSum (x:xs) = x : scanSum ((x + sumInt (takeInt 1 xs)) : dropInt 1 xs) ----------- USING (a:b:as) ---------------- scanSum :: [Int] -> [Int] scanSum  =  scanSum (a:) = a: scanSum (a:b:as) = a : scanSum ((a+b):as)
diffs :: [Int] -> [Int] diffs  =  diffs (x:) =  diffs (x:y:xs) = (y-x) : diffs (y:xs) -- alternative with the auxiliary function: diffsAlt :: [Int] -> [Int] diffsAlt  =  diffsAlt (x:xs) = diffsAlt' (x:xs) xs where diffsAlt' :: [Int] -> [Int] -> [Int] diffsAlt' _  =  diffsAlt'  _ =  diffsAlt' (x:xs) (y:ys) = (y-x): diffsAlt' xs ys
In one block of code. In addition to the variations here, you can also replace Int by Integer:
negateList, negateList2 :: [Int] -> [Int] negateList = map negate negateList2 list = map negate list factorList, factorList2 :: [Int] -> [[Int]] factorList = map factors factorList2 list = map factors list -- There are a few possible variations for this one. If yours is different, check with a Haskell interpreter to see if it's correct. -- The dots are just another higher-order trick. (g . f) x = g(f(x)) negateFactorList, negateFactorList2, negateFactorList3, negateFactorList4 :: [Int] -> [[Int]] negateFactorList = map (negateList . factors) negateFactorList2 = map negateList . factorList negateFactorList3 list = map (negateList . factors) list negateFactorList4 list = map (map negate) (map factors list)
Here's my Run Length Encoding, although I don't see how I'm supposed to use
map. (Maybe if the text explained
encode :: Eq a => [a] -> [(Int,a)] encode  =  encode [x] = [(1,x)] encode (x:y:xs) | x == y = succHead (encode (y:xs)) | otherwise = (1,x) : encode (y:xs) succHead :: [(Int,a)] -> [(Int,a)] succHead  =  -- this should never be called by encode on any input succHead ((n,x):ps) = (n+1,x):ps decode :: [(Int,a)] -> [a] decode  =  decode ((n,x):ps) = (repetition n x) ++ decode ps repetition :: Int -> a -> [a] repetition 0 _ =  -- this should never be called by decode on a properly formatted input repetition n x = x:(repetition (n-1) x)
Here is my version which uses
map in a single function with a anonymous helper function (I only included the solution for encode because in my opinion there are a few very useful functions that need to be introduced prior to going through the other functions.
concatMap, which can be used as an inverse of map and
replicate, which can be used for repetition.):
import Data.List encode :: [Char] -> [(Int, Char)] encode list = map go (group list) where go (x:xs) = (length (x:xs), x)
And here is mine using
map. To understand what the
group command did, I visited hayoo. If you aren't familiar with hayoo yet, take a couple of minutes to try it now. It's very useful.
import Data.List lenwhat :: [Char] -> (Int, Char) lenwhat x = (length x, head x) encode :: [Char] -> [(Int, Char)] encode "" =  encode x = map lenwhat (group x) decode :: [(Int, Char)] -> [Char] decode  = "" decode ((l, w):xs) = (replicate l w) ++ decode xs toRleString :: [(Int, Char)] -> [Char] toRleString  = "" toRleString ((l, w):xs) = show l ++ w : rlestring xs
This is a version I made to learn to use map and group.
import Data.List count_tuple (x:xs) = (length (x:xs) , x) map count_tuple (group "aaaaaabbbbbcccccccaaaaaaaaaaaaaaa")
Here's my (Zevras) solution:
import Data.List encode :: (Eq a) => [a] -> [(Int, a)] encode x = map helper $ group x where helper x = (length x, head x) decode :: [(Int, a)] -> [a] decode xs = concat $ map rep xs where rep (n, x) = take n $ repeat x
N.B., the RLE example is inspired from a blog post by Don Stewart on the same subject. See Don's post for a more elegant solution (which might not be immediately understandable; see Haskell/Understanding arrows for a discussion on
Here’s my solution to the “bonus” problem. The function is called
-- Takes a string like "2a4c11b" and turns it into its encoded -- counterpart; in this case: [(2, 'a'), (4, 'c'), (11, 'b')]. extract :: String -> [(Int, Char)] extract  =  extract (x:xs) = extract' [x] xs -- helper function to keep track of the numbers. -- ns : List of digits ("1234"). extract' :: String -> String -> [(Int, Char)] extract' _  =  extract' ns [x] = [(read ns, x)] -- the last element of the string -- is assumed to be a non-digit. extract' ns (y:z:zs) = if y `elem` ['0','1','2','3','4','5','6','7','8','9'] then extract' (ns ++ [y]) (z:zs) else (read ns, y) : extract' [z] zs
A possible answer to the question "How would you convert the list of tuples (e.g. [(4,'a'), (6,'b')]) into a string (e.g. "4a6b")?"
-- Convert a list of tuples into a string. -- For example, [(4, 'a'), (6, 'b')] becomes "4a6b". -- I begin with a function that converts a single tuple into a string two characters long. -- The intToDigit function converts a interger into a character. For example: intToDigit 1 = '1'. -- If intToDigit isn't used, GHCi will throw a type error. import Data.Char tupleToString :: (Int, Char) -> [Char] tupleToString x = (intToDigit.fst) x:(snd x): -- Now we'll map this function to a list of tuples. We get back a list of strings. -- For example: tuplesToStrings [(1, 'a'), (2, 'b')] = ["1a", "2b"]. tuplesToStrings  =  tuplesToStrings (x:xs) = tupleToString x : tuplesToStrings xs -- A little concat and we're done. tuplesToString xs = (concat . tuplesToStrings) xs Test with the function call tuplesToString [(4,'a'), (6,'b')] ==> "4a6b"
Tips and tricks
scanSum (takeInt 10 [1..]) and
takeInt 10 (scanSum [1..]) have the same value. This is possible because Haskell is a lazy language, thus in both cases the result is only evaluated as needed.
-- this is just like the Prelude function last lastOf :: [a] -> a lastOf  = error "Empty list" lastOf (x:) = x lastOf (_:xs) = lastOf (xs) -- this is just like the Prelude init dropLast :: [a] -> [a] dropLast  = error "Empty list" dropLast (x:) =  dropLast (x:xs) = x : (dropLast xs)