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)
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.
getElemAt :: Int -> [a] -> a getElemAt _  = error "Index too large" -- a custom error message, just for extra "sugar" getElemAt 0 ls = head ls getElemAt n ls = getElemAt (n-1) (tail ls)
-- this is just like the Prelude function last lastOf :: [a] -> a lastOf  = error "Empty list" lastOf (x:) = x lastOf (_:xs) = lastOf (xs) -- somewhat more complicated alternative with no pattern matching lastOf :: [a] -> a lastOf  = error "Empty list" lastOf ls = if (null (tail ls)) then head ls else lastOf (tail ls) -- this is just like the Prelude init dropLast :: [a] -> [a] dropLast  = error "Empty list" dropLast (x:) =  dropLast (x:xs) = x : (dropLast xs) -- again, the head/tail alternative dropLast :: [a] -> [a] dropLast  = error "Empty list" dropLast ls = if (null (tail ls)) then  else ((head ls) : dropLast (tail ls))