Haskell exercises - Chapter 7

My solutions to exercises from Graham Hutton's Programming in Haskell.

Exercise 7.1

foo :: (a -> b) -> (a -> Bool) -> [a] -> [b]
foo f p xs = [f x | x <- xs, p x]

foo' :: (a -> b) -> (a -> Bool) -> [a] -> [b]
foo' f p xs = map f (filter p xs)

-- For example, the following two expressions generate the same list, [1, 9, 25, 49, 81, ...]
sqrodds  = [(^2) n | n <- [1..], odd n]
sqrodds' = map (^2) $ filter odd [1..] 

Exercise 7.2

all' :: (a -> Bool) -> [a] -> Bool
all' p = foldr (\x y -> p x && y) True

any' :: (a -> Bool) -> [a] -> Bool
any' p = foldr (\x y -> p x || y) False

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' _ []                 = []
takeWhile' p (x:xs) | p x       = x : takeWhile' p xs
                    | otherwise = []

dropWhile' :: (a -> Bool) -> [a] -> [a]
dropWhile' _ []                 = []
dropWhile' p (x:xs) | p x       = dropWhile' p xs
                    | otherwise = (x:xs)

Exercise 7.3

map' :: (a -> b) -> [a] -> [b]
map' f = foldr (\x ys -> f x : ys) []

filter' :: (a -> Bool) -> [a] -> [a]
filter' p = foldr (\x ys -> if p x then x : ys else ys) []

Exercise 7.4

dec2int :: [Int] -> Int
dec2int = foldl (\x y -> x*10 + y) 0

Exercise 7.5

-- Answer: The list passed to compose is invalid because its elements are not all of the same type.

Exercise 7.6

curry' :: ((a, b) -> c) -> a -> b -> c
curry' f = \x y -> f (x, y)

uncurry' :: (a -> b -> c) -> (a, b) -> c
uncurry' f = \(x, y) -> f x y

Exercise 7.7

unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
unfold p h t x | p x       = []
               | otherwise = h x : unfold p h t (t x)
      
type Bit = Int
      
chop8' :: [Bit] -> [[Bit]]
chop8' = unfold null (take 8) (drop 8)

map' :: (a -> b) -> [a] -> [b]
map' f = unfold null (f . head) tail

iterate' :: (a -> a) -> a -> [a]
iterate' f = unfold (\_ -> False) id f

Exercise 7.8

To encode:

parityBit :: [Bit] -> Bit
parityBit bits = if odd ones then 1 else 0
                 where ones = sum [b | b <- make8 bits]

make9 :: [Bit] -> [Bit]
make9 bits = (make8 bits) ++ [parityBit bits]
       
encodePb :: String -> [Bit]
encodePb = concat . map (make9 . int2bin . ord)

To decode:

chop9 :: [Bit] -> [[Bit]]
chop9 = unfold null (take 9) (drop 9)  -- where unfold has been defined in Exercise 7.7

dropPb :: [Bit] -> [Bit]
dropPb bits = if last bits == parityBit bits 
              then take 8 bits
              else error "Parity bit error!"
   
decodePb :: [Bit] -> String
decodePb = (map (chr . bin2int . dropPb)) . chop9

Then:

transmitPb :: String -> String
transmitPb = decodePb . channel . encodePb
             where channel = id

Exercise 7.9

transmitPb' :: String -> String
transmitPb' = decodePb . fawltyChannel . encodePb
              where fawltyChannel = tail

Haskell exercises - Chapter 6

My solutions to exercises from Graham Hutton's Programming in Haskell.

Exercise 6.1

import Prelude hiding ( (^) )

(^) :: Int -> Int -> Int
n ^ 0     = 1
n ^ (m+1) = n * (n^m)

Exercise 6.3

import Prelude hiding (and, concat, replicate, (!!), elem)

and :: [Bool] -> Bool
and []     = True
and (b:bs) = b && and bs

concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

replicate :: Int -> a -> [a]
replicate 0     x = []
replicate (n+1) x = x : replicate n x

(!!) :: Integral a => [a] -> n -> a
(!!) (x:xs) 0     = x
(!!) (x:xs) (n+1) = xs !! n

elem :: Eq a => a -> [a] -> Bool
elem x []     = False
elem x (y:ys) = if x == y then True else elem x ys

Exercise 6.4

merge :: Ord a => [a] -> [a] -> [a]
merge xs     []     = xs
merge []     ys     = ys
merge (x:xs) (y:ys) = if x < y then x : merge xs (y:ys) else y : merge (x:xs) ys

Exercise 6.5

halve :: [a] -> ([a], [a])
halve xs = (fsthalf, sndhalf) 
    where fsthalf = take ((length xs) `div` 2) xs
           sndhalf = drop (length fsthalf) xs

msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort firsthalf) (msort secondhalf)
    where 
        firsthalf = fst halves
        secondhalf = snd halves
        halves = halve xs

Exercise 6.6

import Prelude hiding (sum, take, last)

sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs

take :: Int -> [a] -> [a]
take 0     xs     = xs
take (n+1) (x:xs) = x : take n xs

last :: [a] -> a
last [x]    = x
last (x:xs) = last xs

Haskell exercises - Chapter 5

My solutions to exercises from Graham Hutton's Programming in Haskell.


Exercise 5.1

sum2 :: Int
sum2 = sum [ x^2 | x <- [1..100] ]

Exercise 5.2

replicate :: Int -> a -> [a]
replicate n x = [ x | _ <- [1..n] ]

Exercise 5.3

pyths :: Int -> [(Int, Int, Int)]
pyths n = [ (x, y, z) | x <- [1..n], y <- [1..n], z <- [1..n], z^2 == x^2 + y^2 ]

Exercise 5.4

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

perfects :: Int -> [Int]
perfects n = [p | p <- [1..n], p == sum (factors p) - p]

A cleaner version uses a different implementation of factors, that returns only the factors which are different than the number itself:

factors' :: Int -> [Int]
factors' n = [x | x <- [1..n], n `mod` x == 0, x <= n `div` 2]

perfects' :: Int -> [Int]
perfects' n = [p | p <- [1..n], p == sum (factors' p)]

Exercise 5.5

xys :: [(Int, Int)]
xys = [(x,y)| x <- [1, 2, 3], y <- [4, 5, 6]] 

xys' :: [(Int, Int)]
xys' = concat [[(x,y) | y <- [4,5,6]] | x <- [1,2,3]]

Exercise 5.6

find :: Eq a => a -> [(a, b)] -> [b]
find k t = [v| (k', v) <- t, k == k']

positions' :: Eq a => a -> [a] -> [Int]
positions' x xs = find x (zip xs [0..n]) where n = length xs - 1

Exercise 5.7

scalarproduct :: [Int] -> [Int] -> Int
scalarproduct xs ys = sum [ fst xy * snd xy | xy <- zip xs ys ]

Exercise 5.8
The idea is that when we calculate the table of frequencies we shouldn't differentiate between lowercase and uppercase letters. Then, once the shift factor is calculated, we crack the code by shifting both lowercases and uppercases.

1. Changes for calculating the frequencies:

-- Converts all letters to lowercases:
toLowers :: String -> String
toLowers cs = [toLower c | c <- cs]

-- Generates the same table as freqs does, but ignoring the capitalization:
freqs' :: String -> [Float]
freqs' cs = [ percent (count c cs') n | c <- ['a'..'z'] ]
           where 
               n = lowers cs'
               cs' = toLowers cs

2. Redefinitions of the functions shift and encode to make them case-insensitive:

let2intU :: Char -> Int
let2intU c = ord c - ord 'A'

int2letU :: Int -> Char
int2letU n = chr (ord 'A' + n)

shift' :: Int -> Char -> Char
shift' n c | isLower c = int2let ((let2int c + n) `mod` 26)
           | isUpper c = int2letU ((let2intU c + n) `mod` 26)
           | otherwise = c   

encode' :: Int -> String -> String
encode' n cs = [ shift' n c | c <- cs ]     

3. Use the newly defined encode' to crack the code, when the frequency table is calculated by the case-insensitive function freqs':

crack' :: String -> String
crack' xs = encode' (-factor) xs
    where 
        factor = head (positions (minimum chitab) chitab)
        chitab = [ chisqr (rotate n table') table | n <- [0..25] ]
        table' = freqs' xs 

Haskell exercises - Chapter 4

My solutions to exercises from Graham Hutton's Programming in Haskell.


Exercise 4.1

halve :: [a] -> ([a], [a])
halve xs
  | len `mod` 2 == 0 = (take (len `div` 2) xs, drop (len `div` 2) xs)
  | otherwise = (xs, [])
  where len = length xs

Exercise 4.2
a)

safetail :: [a] -> [a]
safetail xs = if null xs then [] else tail xs

b)

safetail :: [a] -> [a]
safetail xs | null xs   = []
            | otherwise = tail xs

c)

safetail :: [a] -> [a]
safetail [] = []
safetail xs = tail xs

Exercise 4.3

(||) :: Bool -> Bool -> Bool

First method:

(||) True  True  = True
(||) True  False = True
(||) False True  = True
(||) False False = False

Second method:

(||) False False = False
(||) _    _     = True

Third method:

(||) False q = q
(||) True  _ = True

A variation of the 3rd method:

(||) True _ = True
(||) _    q = q

Fourth method:

(||) p q | p == q    = p
         | otherwise = True

Exercise 4.4

(&&) :: Bool -> Bool -> Bool
p && q = if p 
              then 
                  if q then True else False
              else
                  False

Exercise 4.5

(&&) :: Bool -> Bool -> Bool
p && q = if p then q else False

Exercise 4.6

mult :: Num a => a -> (a -> (a -> a))
mult = \x -> (\y -> (\z -> x * y * z))