ch09 Exercises :: Lists

We can insert ⊥ (bottom) on Linux Gtk with Ctrl+Shift+U followed by 22a5. On Vim, in insert mode with Ctrl+v u 22a5. On Emacs with C-x u RET 22a5 RET.

Will it blow up?

Will the expressions return a value or ⊥ (bottom)?

1. [x^y | x <- [1..5], y <- [2, undefined]]

2. take 1 $ [x^y | x <- [1..5], y <- [2, undefined]]

3. sum [1, undefined, 3]

4. length [1, 2, undefined]

5. length $ [1, 2, 3] ++ undefined

6. take 1 $ filter even [1, 2, 3, undefined]

7. take 1 $ filter even [1, 3, undefined]

8. take 1 $ filter odd [1, 3, undefined]

9. take 2 $ filter odd [1, 3, undefined]

10. take 3 $ filter odd [1, 3, undefined]

Exercise 01

[x^y | x <- [1..5], y <- [2, undefined]]

The undefined from the second list will have to be evaluated as it is used as the exponent and this expression will return ⊥.

Exercise 02

take 1 $ [x^y | x <- [1..5], y <- [2, undefined]]

It will return the result of 1 ^ 2 and not ⊥. This is because of take 1 which will require the evaluation of the first pair only, not allowing evaluation to reach the undefined.

Because it is a list comprehension, it returns 1 ^ 2 (which is 1) inside a list, so the result is actually [1].

Exercise 03

sum [1, undefined, 3]

Returns ⊥ because sum forces the values.

Exercise 04

length [1, 2, undefined]

Produces 3. length only evals the spine, not forcing the values.

Exercise 05

length $ [1, 2, 3] ++ undefined

Produces ⊥. Because of ++ undefined, that undefined is part of the spine, and length needs to evaluate the spine.

NOTE: Of course, if we place that undefined in a value position (rather than in a spine position), then all is fine for length:

λ> length $ [1, 2, 3] ++ [undefined]
4

Exercise 06

take 1 $ filter even [1, 2, 3, undefined]

Because of take 1, we’ll stop as soon as we find the even number 2 and we won’t reach undefined. The result is [2].

Exercise 07

take 1 $ filter even [1, 3, undefined]

Even though we have take 1, we don’t find an even number until we reach undefined, and even will force the value to check of its “evenness”, thus causing ⊥ to occur.

Exercise 08

take 1 $ filter odd [1, 3, undefined]

An odd number is found before reaching undefined. The result is [1].

Exercise 09

take 2 $ filter odd [1, 3, undefined]

Two odd numbers are found just before reaching undefined. The result is [1, 3].

Exercise 10

take 3 $ filter odd [1, 3, undefined]

Two odd numbers are found, but not the third before reaching undefined, causing ⊥ to occur.

Is it in normal form?

Page 494.

• Question about these in Haskell Discord.

For each expression below, determine whether it’s in:

1. Normal form, which implies weak head normal form.

2. Weak head normal form only.

3. Neither.

Remember that an expression cannot be in normal form or weak head normal form if the outermost part of the expression isn’t a data constructor. It can’t be in normal form if any part of the expression is unevaluated.

NOTE: The _ symbol in the examples below mean a value or expression has not been evaluated.

Exercise 01

[1, 2, 3, 4, 5]

NF and WHNF.

NF because no expression or sub-expression is un-evaluated. WHNF because it is evaluated to at least the first/outermost data constructor (and by definition, anything in NF is also in WHNF).

Exercise 02

1 : 2 : 3 : 4 : _

WHNF. Not all expressions have been evaluated due to the _ symbol.

Exercise 03

enumFromTo 1 10

Neither because it is a function application to all possible arguments.

Exercise 04

length [1, 2, 3, 4, 5]

Neither. It is a function application.

Exercise 05

sum (enumFromTo 1 10)

Neither. It is a function application, which results in a value, which is also applied to a function.

Exercise 06

['a'..'m'] ++ ['n'..'z']

Neither. The outermost part is a function application of ++.

Exercise 07

(_, 'b')

WHNF. The outermost part is the data constructor (,) even though not all sub-expressions are fully evaluated.

---

To be clear here what’s super important is recognizing that WHNF and NF are syntactic properties of expressions And in particular it’s very easy to find out if an expression is in WHNF Neither are properties of the values denoted by those expressions

---

More Bottoms

Page 504.

Exercise 01

take 1 $ map (+1) [undefined, 2, 3]

Will be ⊥ because the first element we try to take and force is undefined, which is bottom.

Exercise 02

take 1 $ map (+1) [1, undefined, 3]

Yes,m it will return [2] from the evaluation of (+ 1) 1. We take 1 element before having to reach and try to force undefined.

Exercise 03

take 2 $ map (+1) [1, undefined, 3]

No, it will be ⊥ because we try have to force two elements from the list, and the second one is undefined.

Note the part in red. It was able to evaluate at least the first value, but reached bottom when trying the second one.

Exercise 04

What does the following mystery function do? What is its type? Describe it (to yourself or a loved one) in standard English and then test it out in the REPL to make sure you are correct.

itIsMystery xs = map (\x -> elem x "aeiou") xs

It returns a list of Bool. True if the current element is a lowercase vowel, False otherwise.

It’s type is [Char] -> [Bool].

λ> isMistery "hello"
[False,True,False,False,True]

λ> isMistery "abcde"
[True,False,False,False,True]

Exercise 05

What will be the result of the following functions:

a. map (^2) [1..10] b. map minimum [[1..10], [10..20], [20..30]] (n.b. minimum is not the same function ass the min function that we used before) c. map sum [[1..5], [1..5], [1..5]]

a

Each element in the list will be raised to the second power:

λ> map (^ 2) [1 .. 10]
[1,4,9,16,25,36,49,64,81,100]

b

It will return a list with the smallest (minimum) value of each sub-list.

λ> minimum [1 .. 10]
1
λ> minimum [10 .. 20]
10
λ> minimum [20 .. 30]
20
λ> map minimum [[1 .. 10], [10 .. 20], [20 .. 30]]
[1,10,20]

c

It will return a list with three elements which sums [1 .. 5] in each case.

λ> map sum [[1 .. 5], [1 .. 5], [1 .. 5]]
[15,15,15]

Exercise 06

Back in Chapter 7, you wrote a function called foldBool. That function exists in a module known as Data.Bool and is called bool. Write a function that does the same (or similar, if you wish) as the map if-then-else function you saw above but uses bool instead of the if-then-else syntax. Your first step should be bringing the bool function into scope by typing import Data. Bool at your REPL prompt.

This is the “map if-then-else function we saw above”:

λ> map (\x -> if x == 3 then (- x) else x) [1 .. 10]
[1,2,-3,4,5,6,7,8,9,10]

First, here’s how bool from Data.Bool works:

It takes an argument of type \(a\) and another argument of type \(a\) and a Bool. If the Bool is False, return the first argument; else return the second argument.

λ> import Data.Bool (bool)
λ> :type bool
bool :: a -> a -> Bool -> a
λ> bool "Lara" "Croft" False
"Lara"
λ> bool "Lara" "Croft" True
"Croft"

λ> if not False then "Lara" else "Croft"
"Lara"
λ> if False then "Lara" else "Croft"
"Croft"

So, the solution:

import Data.Bool (bool)

λ> map (\n -> bool n (- n) (n == 3)) [1 .. 5]
[1,2,-3,4,5]

n is the current number. If n == 3 is False, simply return n. But if n == 3 is True, then negate n.

Exercises: Filtering

Page 335.

Exercise 1

How might we write a filter function that would give us all the multiples of 3 out of a list from 1 to 30?

A multiple of 3 is a number whose remainder of it by 3 is 0.

One approach is to make a tiny helper function to check if a number is a multiple of three and then use it in the “main” function.

isMultipleOf3 :: Int -> Bool
isMultipleOf3 n = rem n 3 == 0

λ> filter isMultipleOf3 [1 .. 30]
[3,6,9,12,15,18,21,24,27,30]

Exercise 2

Recalling what we learned about function composition, how could we compose the above function with the length function to tell us how many multiples of 3 there are between 1 and 30?

isMultipleOf3 :: Int -> Bool
isMultipleOf3 n = rem n 3 == 0

countMultiplesOf3 :: [Int] -> Int
countMultiplesOf3 = length . filter isMultipleOf3

Of course, we’d rather do it more abstract and reusable:

--
-- Checks whether y is a multiple of x.
--
isMultipleOf :: Integer -> Integer -> Bool
isMultipleOf x y = rem y x == 0

countMultiplesOf :: Integer -> [Integer] -> Int
countMultiplesOf n = length . filter (isMultipleOf n)

λ> countMultiplesOf 3 [1 .. 30]
10
λ> countMultiplesOf 5 [1 .. 30]
6
λ> countMultiplesOf 10 [1 .. 30]
3

Exercise 3

Next, we’re going to work on removing all articles (“the,” “a,” and “an”) from sentences. You want to get to something that works like this:

λ> myFilter "the brown dog was a goof"
["brown","dog","was","goof"]

Let’s assume these three string examples:

snake :: [Char]
snake = "there a snake in here"

fruit :: [Char]
fuit = "an apple is a fruit"

jedi :: [Char]
jedi = "may the force be with you"

Solution 1

One approach is maybe create a tiny isArticle function that is then used in the “main” function:

--
-- ASSUME: The input is all in lower case.
--
isArticle :: [Char] -> Bool
isArticle word = word == "a" || word == "an" || wrod "the"

--
-- ASSUME: The input is all in lowercase.
--
dropArticles :: [Char] -> [[Char]]
dropArticles str = filter (not . isArticle) (words str)

Note the not . isArticle composition.

λ> dropArticles snake
["there","snake","here"]

λ> dropArticles fruit
["apple","is","fruit"]

λ> dropArticles jedi
["may","force","be","with","you"]

Hint

The type [Char] -> [[Char] is the same as String -> [String].

Solution 2

Another approach is to do it all at once in the same function:

dropArticles :: [Char] -> [[Char]]
dropArticles = filter (\s -> not . elem s $ ["a", "an", "the"]) . words

First split the string into individual words and then drop it if it is not “a”, “an” or “the”. Function composition and point-free style were used for this solution and also the application operator $.

And instead of not . elem, let’s remember that notElem exists in Prelude:

dropArticles :: [Char] -> [[Char]]
dropArticles = filter (\s -> notElem s $ ["a", "an", "the"]) . words

Zipping exercises

Page 337.

Exercise 1

Write your own version of zip, and ensure it behaves the same as the original:

zip :: [a] -> [b] -> [(a, b)]
zip = undefined

Solution 1

myZip :: [a] -> [b] -> [(a, b)]
myZip [] _              = []
myZip _ []              = []
myZip (x : xs) (y : ys) = (:) (x, y) $ myZip xs ys

Pattern matching and the cons operator. The application operator $ is used too, and it is possible because the cons operator : was placed in prefix position.

We could also use parentheses instead of $:

... = (:) (x, y) (myZip xs ys)

And use the cons in infix position:

... = (x, y) : (myZip xs ys)

Solution 2

Using the go function pattern, which allows us to use tail call recursion:

myZip :: [a] -> [b] -> [(a, b)]
myZip xs ys = go xs ys []
  where
    go :: [a] -> [b] -> [(a, b)] -> [(a, b)]
    go [] _ acc                = acc
    go _ [] acc                = acc
    go (x : lox) (y : loy) acc = go lox loy (acc ++ [(x, y)])

Note how an accumulator was introduced so the consing of the list happens at the last position, thus enabling TCO.

Also, we do acc ++ [(x, y)] rather than [(x, y)] ++ acc, because we want to append to the accumulator, not prepend to it.

Exercise 2

Do what you did for zip but now for zipWith:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith = undefined

Solution 1

myZipWith :: (a -> b -> c) -> [] a -> [] b -> [] c
myZipWith _ [] _              = []
myZipWith _ _ []              = []
myZipWith f (x : xs) (y : ys) = [f x y] ++ (myZipWith f xs ys)

Because we are NOT doing tail call in this solution, we do [f x y] ++ “the rest of the recursion”.

Solution 2

Using the go function pattern and tail call optimization.

myZipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
myZipWith f xs ys = go f xs ys []
  where
    go :: (a -> b -> c) -> [a] -> [b] -> [c] -> [c]
    go _ [] _ acc                 = acc
    go _ _ [] acc                 = acc
    go fn (x : lox) (y : loy) acc = go fn lox loy (acc ++ [(fn x y)])

Because we are doing TCO, we do acc ++ [(fn x y)]. The accumulator always has the latest computation thus far. With TCO, we are not just storing expressions that will be evaluated later, in the unwinding phase of the execution.

So, if we do (f x) ++ rest or acc ++ (f x) depends on the type of recursion we are doing.

Exercise 3

Rewrite your zip in terms of the zipWith you wrote.

Solution 1

Well, zip must create a tuple, and to create a tuple we use the tuple constructor (,). zipWith takes a function. We can simply partially apply myZipWith to (,) and we are done!

myZip :: [a] -> [b] -> [(a, b)]
myZip = myZipWith (,)

λ> myZip [1, 2] "ab"
[(1,'a'),(2,'b')]

We also made myZip point-free.

Chapter exercises

Page 338.

NOTE: We’ll need to import functions from Data.Char.

Data.Char

Exercise 1

Query the types of isUpper and toUpper.

Solution

λ> import Data.Char (isUpper, isLower)

λ> :type isUpper
isUpper :: Char -> Bool

λ> :type isLower
isLower :: Char -> Bool

Exercise 2

Given the following behaviors, which would we use to write a function that filters all the uppercase letters out of a String?

λ> isUpper 'J'
True
λ> toUpper 'j'
'J'

Write that function such that, given the input "HbEfLrLxO", your function will return "HELLO".

Which function?

If we want to filter all uppercase letters, it means we want to ignore the lowercase letters. We could use not . isLower, but simpler yet is to simply use isUpper.

Also, we don’t to transform a letter to uppercase, but just check if it is uppercase. Thus, we use isUpper instead of toUpper.

Solution 1

Idiomatic approach making use of stdfn filter and simply partially applying it to isUpper. We also use point-free style.

import Data.Char (isUpper)

onlyUppers :: [Char] -> [Char]
onlyUppers = filter isUpper

--
-- λ> onlyUppers "HbEfLrLxO"
-- "HELLO"
--

Solution 2

Pattern matching, go function approach, and manually accumulating the uppercase letters.

import Data.Char (isUpper)

onlyUppers :: [Char] -> [Char]
onlyUppers str = go str []
  where
    go :: [Char] -> [Char] -> [Char]
    go [] loc       = loc
    go (c : cs) loc =
      if isUpper c
      then go cs (c : loc)
      else go cs loc

Exercise 3

Write a function that will capitalize the first letter of a string and return the entire string. For example, if given the argument “julie”, it will return “Julie”.

Solution

Pattern match on the first char and the rest of the string uppercase the first char and cons it to the rest of the unmodified string.

import Data.Char (toUpper)

--
-- ASSUME: The input has length >= 1.
--
capitalize :: [Char] -> [Char]
capitalize [] = ""
capitalize (c : cs) = toUpper c : cs
--
-- λ> capitalize "yoda"
-- "Yoda"
--
-- λ> capitalize "ahsoka tano"
-- "Ahsoka tano"
--

Exercise 4

Now make a new version of that function that is recursive, such that if you give it the input “woot”, it will holler back at you “WOOT”. The type signature won’t change, but you will want to add a base case.

Solution 1

Pattern matching and the cons operator :.

import Data.Char (toUpper)

capitalizeAll :: [Char] -> [Char]
capitalizeAll []       =      ""
capitalizeAll (c : cs) =  toUpper c : capitalizeAll cs
--
-- λ> capitalizeAll "https"
-- "HTTPS"
--

Solution 2

Point-free style using foldr (not yet learned in the book at this point) and function composition.

import Data.Char (toUpper)

capitalizeAll :: [Char] -> [Char]
capitalizeAll = foldr ((:) . toUpper) ""

: cons is composed with toUpper. Each character is then uppercased and consed onto the accumulator, producing the final all-uppercase string result.

Exercise 5

To do the final exercise in this section, we’ll need another standard function for lists called head. Query the type of head, and experiment with it to see what it does. Now write a function that will capitalize the first letter of a String and return only that letter as the result.

λ> :type head
head :: [a] -> a

Solution 1

The $ ‘infixr 0’ function application operator causes head to be applied to str first. That result is then the argument to toUpper.

capitalizeFirst :: [Char] -> Char
capitalizeFirst str = toUpper $ head str

Exercise 6

Solution 1

Point-free, function composition. head returns the first char of the string which toUpper is then applied.

capitalizeFirst :: [Char] -> Char
capitalizeFirst = toUpper . head
--
-- λ> capitalizeFirst "haskell"
-- 'H'
--

Ciphers

Basically, do a rightwards Caesar shift.

Let’s consider lowercase-only English alphabet letters.

Solution 1 (baby steps 😅)

We’ll go with an approach where we map each letter from ‘a’ to ‘z’ to ints from 0 to 25. So ‘a’ is 0 and ‘z’ is 25.

Recall that ‘a’ is 97 in both ASCII and UTF-8. Let’s name our 97 as a:

a :: Int
a = 97

The English alphabet has 26 letters:

λ> length ['a' .. 'z']
26

That means we need to “wrap around” at 26. That will be one of our parameters to the mod function:

λ> mod 0 26
0

λ> mod 1 26
1

λ> mod 25 26
25

λ> mod 26 26
0

λ> mod 27 26
1

Consider ‘z’, which is 25 in our 0 to 25 mapping. If we want to shift ‘z’ rightwards by 1 position, we’ll do \(25 + 1 = 26\), and mod 26 26 is 0, which is the position for ‘a’. Then, \(0 + 97 = 97\), and ord 97 is ‘a’. \(1 + 97 = 98\), and ord 98 is ‘b’. By adding 97 to our ints, we can compute the int value of each one of the letters from 0 to 25.

Play with those ideas in GHCi’s REPL to get a better feeling for it.

module Cipher1 where

import Data.Char (chr, ord)

--
-- The int value of 'a' in ASCII and UTF-8 is 97.
--
a :: Int
a = 97

--
-- Because the English alphabet contains 26 letters, this is the
-- number we need to “wrap around” when shifting char positions.
--
wrp :: Int
wrp = 26

--
-- Translates the zero-based position of a character `c` in the
-- lowercase English alphabet into its corresponding 0 to 25 numeric
-- mapping.
--
-- Examples:
-- • ‘a’ → 0
-- • ‘z’ → 25
--
toPos :: Char -> Int
toPos c = ord c - a

--
-- Translates the zero-based position `i` into its corresponding
-- lowercase letter in the English Alphabet.
--
-- Examples:
-- •  0 → ‘a’
-- • 25 → ‘z’
--
toChr :: Int -> Char
toChr i = chr $ i + a

--
-- Right-shifts c by n positions.
--
-- Examples:
--
-- • move 1 'a' → 'b'
-- • move 3 'a' → 'd'
-- • move 1 'z' → 'a'
-- • move 3 'z' → 'c'
--
move :: Int -> Char -> Char
move n c = toChr $ mod (toPos c + n) wrp

--
-- Applies the Caesar to `chrs` by shifting each letter `n` positions
-- to the right.
--
-- ASSUME: Lowercase-only English alphabet letters.
--
caesar :: Int -> [Char] -> [Char]
caesar n chrs = map (move n) chrs

Then, on a GHCi session, we can test try it:

λ> caesar 3 "xyz"
"abc"

λ> caesar 1 "abc"
"bcd"

λ> caesar 3 "abc"
"def"

λ> caesar 1 "xyz"
"yza"

λ> caesar 3 "xyz"
"abc"

We could make caesar take only the n param and leave the chrs argument to map point free:

caesar :: Int -> [Char] -> [Char]
caesar n = map (move n)

Other changes like partially applying move to n would also be possible, but this is good enough.

Solution 2

Currently, move can only shift chars to the right. How can we make move able to shift characters to the right and to the left as well? If we find a solution for this, we would also be able to do the unCaesar function asked in the book.

This is the current implementation:

--
-- Right-shifts c by n positions.
--
-- Examples:
--
-- • move 1 'a' → 'b'
-- • move 3 'a' → 'd'
-- • move 1 'z' → 'a'
-- • move 3 'z' → 'c'
--
move :: Int -> Char -> Char
move n c = toChr $ mod (toPos c + n) wrp

Hmm… We are always using + to add (shift to the right). If we can improve move so that it takes the function + or - as parameter, then it would be able to shift chars left and right.

Let’s try this:

--
-- Shifts `c` by `n` positions left or right according to `f`.
--
-- Examples:
--
-- • move (+) 3 'z' → 'c'
-- • move (-) 3 'a' → 'x'
--
move :: (Int -> Int -> Int) -> Int -> Char -> Char
move f n c = toChr $ mod (f (toPos c) n) wrp

And a in GHCi:

λ> move (+) 1 'z'
'a'

λ> move (-) 1 'a'
'z

And let’s also update caesar:

--
-- Applies the Caesar to `chrs` by shifting each letter `n` positions
-- to the right or left according to `f`.
--
-- ASSUME: Lowercase-only English alphabet letters.
--
caesar :: (Int -> Int -> Int) -> Int -> [Char] -> [Char]
caesar f n = map (move f n)

Which then works like this:

λ> caesar (+) 3 "xyz"
"abc"

λ> caesar (-) 3 "abc"
"xyz"

That is cool and all and all this FP trickery! Nice to practice and learn, but it so happens that our original version was already taking are of left and right shifts.

Solution 3

Our original move function was already able to take care of _both left and right shifting:

move :: Int -> Char -> Char
move n c = toChr $ mod (toPos c + n) wrp

Even though it uses (+) exclusively, if we pass it a negative n, it actually subtracts n from the result of toPos c. Isn’t math a lot of fun‽

λ> 1 + (-3)
-2

λ> toPos 'a'
0

λ> toPos 'a' + (-3)
-3

λ> move (-1) 'z'
'y'

λ> move (-1) 'a'
'z'

So, let’s just update our doc comments and the examples and call it a day!

module Cipher3 where

import Data.Char (chr, ord)

--
-- The int value of 'a' in ASCII and UTF-8 is 97.
--
a :: Int
a = 97

--
-- Because the English alphabet contains 26 letters, this is the
-- number we need to “wrap around” when shifting char positions.
--
wrp :: Int
wrp = 26

--
-- Translates the zero-based position of a character `c` in the
-- lowercase English alphabet into its corresponding 0 to 25 numeric
-- mapping.
--
-- Examples:
-- • ‘a’ → 0
-- • ‘z’ → 25
--
toPos :: Char -> Int
toPos c = ord c - a

--
-- Translates the zero-based position `i` into its corresponding
-- lowercase letter in the English Alphabet.
--
-- Examples:
-- •  0 → ‘a’
-- • 25 → ‘z’
--
toChr :: Int -> Char
toChr i = chr $ i + a

--
-- Shifts `c` by `n` positions left or right according to `n` being
-- positive or negative!
--
-- Examples:
--
-- • move 1 'a' → 'b'
-- • move (-1) 'a' → 'z'
-- • move 3 'z' → 'c'
-- • move (-3) 'a' → 'x'
--
move :: Int -> Char -> Char
move n c = toChr $ mod (toPos c + n) wrp

--
-- Applies the Caesar to `chrs` by shifting each letter `n` positions
-- to the right if `n` is positive; to the left if `n` is negative.
--
-- ASSUME: Lowercase-only English alphabet letters.
--
caesar :: Int -> [Char] -> [Char]
caesar n = map (move n)
--
-- λ> caesar 3 "abc"
-- "def"
--
-- λ> caesar 3 "xyz"
-- "abc"
--
-- λ> caesar (-3) "abc"
-- "xyz"
--
-- λ> caesar (-3) "xyz"
-- "uvw"
--

Solution 4

So our caesar implementation is able to encrypt and decrypt messages just by virtue of the n param being positive or negative. But the book mentions we should create both caesar and the unCaesar functions.

caesar :: Int -> [Char] -> [Char]
caesar n = map (move $ abs n)

unCaesar :: Int -> [Char] -> [Char]
unCaesar n = map (move (negate . abs $ n))

We use abs and negate to prevent caesar and unCaesar to work incorrectly in case users pass a negative int, as these two functions will now each work to shift chars to the right or left directions respectively.

This fourth solution is not much better than the third one where caesar alone was able to encrypt and decrypt messages solely based on n being positive or negative.

Writing your own standard functions

myAnd

myAnd :: [Bool] -> Bool
myAnd []       = True
myAnd (b : bs) = case b of
  False -> False
  _     -> myAnd bs

Linter suggests rewriting using if then else syntax:

myAnd :: [Bool] -> Bool
myAnd [] = True
myAnd (b : bs) = if b then myAnd bs else False

Which in turn complains if is redundant, and && should be used instead:

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

And using foldr (which we didn’t learn yet in the book):

myAnd :: [Bool] -> Bool
myAnd bs = foldr (&&) True bs

And it is possible to make it point-free:

myAnd :: [Bool] -> Bool
myAnd = foldr (&&) True

myOr

We could do as with myAnd and try different implementations, but let’s stick to this one:

myOr :: [Bool] -> Bool
myOr []       = False
myOr (b : bs) = b || myOr bs

Note that for myAnd, the base case for the empty list is True, whereas for myOr, the base case for the empty list is False.

myAny

myAny :: (a -> Bool) -> [a] -> Bool
myAny _ []       = False
myAny f (x : xs) = f x || myAny f xs
--
-- λ> myAny even [1, 3, 4, 5]
-- True
--

myElem

First the recursive approach:

myElem :: Eq a => a -> [a] -> Bool
myElem _ []       = False
myElem e (x : xs) = (==) e x || myElem e xs

Then using myAny:

myElem :: Eq a => a -> [a] -> Bool
myElem e = myAny (e ==)
--
-- λ> myElem 3 [1, 5, 9]
-- False
--
-- λ> myElem 3 [1, 5, 3, 9]
-- True
--

Point-free on the list element (we don’t do myElem e xs, but myElem e). And we do sectioning and partial application of == to e.

myReverse

Get x from the head of the list, and concatenate it to the end :) We put it (the x) inside brackets to make a list out of it, as ++ concatenates lists (both operands must be lists).

myRev :: [a] -> [a]
myRev []       = []
myRev (x : xs) = myRev xs ++ [x]
--
-- λ> myRev "xyz"
-- "zyx"
--

squish

squish :: [[a]] -> [a]
squish []         = []
squish (xs : xss) = xs ++ squish xss
-- 
-- λ> squish [[1], [2], [3]]
-- [1,2,3]
-- 

Or using foldr and point-free style (not specifying the xss param):

squish :: [[a]] -> [a]
squish = foldr (++) []

squishMap

NOTE: squishMap is just like concatMap from Data.Foldable.

squishMap :: (a -> [b]) -> [a] -> [b]
squishMap _ []         = []
squishMap f (xs : xss) = f xs ++ squishMap f xss
--
-- λ> squishMap (\x -> [1, x, 3]) [2]
-- [1,2,3]
--
-- λ> squishMap (\x -> [x + 1]) [1, 2, 3]
-- [2,3,4]
--

Or reusing squish and function composition with map. Point-free as the list parameter is not explicitly specified.

squishMap :: (a -> [b]) -> [a] -> [b]
squishMap f = squish . map f

To try to understand it better, look at this:

λ> map (\n -> [1, n, 3]) [2]
[[1,2,3]]

map itself returns a list, and the lambda is returning a list of its own, thus the result the list returned by the lambda contained inside of the list returned by map. Then squish flattens it to a single-level list.

squishAgain

squishAgain :: [[a]] -> [a]
squishAgain = squishMap id
--
-- λ> squishAgain [[1], [2], [3]]
-- [1,2,3]
--

id simply returns the argument given to it, and our squishAgain is supposed to simply flatten a list of lists. Because we are asked to use squishMap which requires a function as its first arg, but we don’t want to transform each inner list in any way, we then simply give it id.

myMaximumBy

λ> import Data.Foldable (maximumBy)

λ> :type maximumBy 
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a

λ> maximumBy compare []
*** Exception: maximumBy: empty structure

Note that maximumBy is not defined for empty lists.

For now, we can consider Folable t to be a list of t [t].

Solution 1

myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy f xs = go f (tail xs) (head xs)
  where
    go :: (a -> a -> Ordering) -> [a] -> a -> a
    go _  []        winner = winner
    go fn (h : lst) winner =
      case fn h winner of
        GT -> go fn lst h
        _  -> go fn lst winner

Using the go function pattern, start by considering the head of the list to be the maximum so far, keep go recurring with either the current maximum so far or the new maximum value.

Solution 2

NOTE: There is a Discord thread on this solution.

myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy _ [x]      = x
myMaximumBy f (x : xs) =
  case f x g of
    LT -> g
    _  -> x
  where g = myMaximumBy f xs

g is the result of applying myMaximumBy to f and xs, but here xs is actually the tail of the list (because of (x : xs) pattern matching).

It will build expressions up to a point where the list is composed of a single element, when it pattern matches on _ [x]. From there, it can finally “unwind” and evaluate the built expressions. And because of those things, it will actually compare backwards.

Let’s rename myMaximumBy to mmb, inline g, rename x and xs to h and rest respectively, make f an alias to compare, and try to visualize what is going on.

mmb :: (a -> a -> Ordering) -> [a] -> a
mmb _ [n]        = n
mmb f (h : rest) =
  case f h (mmb f rest) of
    LT -> mmb f rest
    _  -> h

Apply mmb to f and [3, 2, 4, 1].

h is 3 and rest is [2, 4, 1].

mmb f (2 : [3, 4, 1])
  case f 2 (mmb f [3, 4, 1]) of
    LT -> mmb f [3, 4, 1]
    _  -> 2

We yet don’t know what is the result of case f 3 (mmb f [2, 4, 1]) of, so we have to evaluate it.

Our new h is 3 and the new rest is [4, 1].

mmb f (2 : [4, 1])
  case f 2 (mmb f [4, 1]) of
    LT -> mmb f [4, 1]
    _  -> 2

We yet don’t know what is the result of case f 2 (mmb f [4, 1]) of, so we have to evaluate it.

Our new h is 4 and the new rest is [1].

mmb f (4 : [1])
  case f 4 (mmb f [1]) of
    LT -> mmb f [1]
    _  -> 4

At this point, we call mmb f [1], which will finally cause _ [n] pattern to match, and return 1. We finally have two numeric values to compare in case of and start “unwinding” the expressions.

The case ... of will now compare 4 and 1, and 4 is the winner. Then 4 and 2, an 4 is still the winner. Then 4 and 3, and 4 is still the winner.

What about we try with [1, 5, 3, 4, 2]? Remember our case ... of:

case f h (mmb f rest) of
  LT -> mmb f rest
  _  -> h

Then:

case f 1 (mmb f [5, 3, 4, 2])

  case f 5 (mmb f [3, 4, 2])

    case f 3 (mmb f [4, 2])

      case f 4 (mmb f [2])

      case f 4 2 ⇒ 4

    case f 3 4 ⇒ 4

  case f 5 4 ⇒ 5

case f 1 5 ⇒ 5