Chapter 9: Lists

9.1 Lists

In this chapter, we will:

  • Explain the list datatype and how to pattern match on lists.

  • Practice many standard library functions for operating on lists.

  • Learn about the underlying representations of lists.

  • See what that representation means for their evaluation.

  • And do a whole bunch of exercises!

9.2 The list datatype

--#   The binary infix data constructor (:), used to
--# construct nested cells of a list, pronounced "cons".
--# Cons is right associative, and has a precedence of 5,
--#  which is lower than the default of precedence of 9
--#    for regular left associative prefix functions.
--#              vvvvvvv
data [] a = [] | a : [a]
--#         ^^
--#  The empty list data constructor, [], pronounced "nill".
--#
--# Since the [] type constructor only takes one type argument,
--# a, lists must be homogenous in Haskell.
--#
--# Because of non-strict evaluation, lists can be infinite, and
--# are often used similarly to iterators generated by range()
--# in python.

instance Eq   a => Eq          [a]
instance Ord  a => Ord         [a]
instance Show a => Show        [a]
instance Read a => Read        [a]
instance           Semigroup   [a]
instance           Monoid      [a]  --# Depends on Semigroup.
instance           Foldable    []   --# (foldMap) depends on Monoid.
instance           Functor     []
instance           Traversable []   --# Depends on Functor and Foldable.
instance           Applicative []   --# Depends on Functor.
instance           Monad       []   --# Depends on Applicative.
instance           MonadFail   []   --# Depends on Monad.

9.3 Pattern matching on lists

9.3.1 Using Maybe

9.4 List’s syntactic sugar

In both Lisp and Haskell, lists are implemented as linked records with two fields - one field contains the elements value, and the other field contains a link to the next record or Nil (end-of-list). These records are called cons cells in lisp.

More generally, for other data structures, linked records are instead called nodes. Nodes may have many fields, including the possibility of multiple links to other nodes. Data may be arranged into arbitrary structures this way.

The spine refers to the entire succession of nested cons cells that comprise a list. (Or linked nodes that comprise some other data structure.) The field of a cons cell that contains the value is not considered part of the spine.

9.5 Using ranges to construct lists

9.5.1 Exercise: EnumFromTo

Write your own enumFromTo for the types provided. Do not use range syntax to do so. It should return the same results as if you did [start..stop]. Replace the undefined with your own definition.

eftBool :: Bool -> Bool -> [Bool]
eftBool = undefined

eftOrd :: Ordering -> Ordering -> [Ordering]
eftOrd = undefined

eftInt :: Int -> Int -> [Int]
eftInt = undefined

eftChar :: Char -> Char -> [Char]
eftChar = undefined

Here is my attempt. To check it, navigate to exercises/9.5.1_-_enumfromto.rst.d/eft and run stack test.

module Lib where


eftBool :: Bool -> Bool -> [Bool]
eftBool True  False  =  []
eftBool True  True   =  [True]
eftBool False True   =  [False,True]
eftBool False False  =  [False]


eft :: (Ord t, Enum t) => t -> t -> [t]
eft from to | from > to   =  []
            | from == to  =  [from]
            | from < to   =  from : eft (succ from) to


eftOrd :: Ordering -> Ordering -> [Ordering]
eftOrd from to = eft from to


eftInt :: Int -> Int -> [Int]
eftInt from to = eft from to


eftChar :: Char -> Char -> [Char]
eftChar from to = eft from to

Here are the tests, for your perusal.

import Test.Hspec
import Test.QuickCheck
import Lib

main :: IO ()
main = hspec $ do
  describe "eftBool" $ do
    it "True False ==> []" $ do
      eftBool True False `shouldBe` []
      eftBool True False `shouldBe` enumFromTo True False
    it "True True ==> [True]" $ do
      eftBool True True `shouldBe` [True]
      eftBool True True `shouldBe` enumFromTo True True
    it "False True ==> [False,True]" $ do
      eftBool False True `shouldBe` [False,True]
      eftBool False True `shouldBe` enumFromTo False True
    it "False False ==> [False]" $ do
      eftBool False False `shouldBe` [False]
      eftBool False False `shouldBe` enumFromTo False False
  describe "eftOrd" $ do
    it "LT LT ==> [LT]" $ do
      eftOrd LT LT `shouldBe` [LT]
      eftOrd LT LT `shouldBe` enumFromTo LT LT
    it "LT EQ ==> [LT,EQ]" $ do
      eftOrd LT EQ `shouldBe` [LT,EQ]
      eftOrd LT EQ `shouldBe` enumFromTo LT EQ
    it "LT GT ==> [LT,EQ,GT]" $ do
      eftOrd LT GT `shouldBe` [LT,EQ,GT]
      eftOrd LT GT `shouldBe` enumFromTo LT GT
  describe "eft" $ do
    it "eft will return the same result as enuFromTo" $
      property (\x y -> enumFromTo x y == eft x (y :: Int))

9.6 Extracting portions of lists

9.6.1 Exercises: Thy Fearful Symmetry

  1. Using takeWhile and dropWhile, write a function that splits a string on spaces to return a list of words.

  2. Next, write a function that takes a string and splits it into lines, breaking on the newline character '\n'.

  3. Try writing a new function that parameterizes the character you’re breaking the string on. Rewrite myWords and myLines to use it.

    Here is the answer to all three questions:

    module Lib where

myWords :: String -> [String]
myWords = mySplit ' '

myLines :: String -> [String]
myLines = mySplit '\n'

mySplit :: Char -> String -> [String]
mySplit _  ""  = []
mySplit ch str =
  takeWhile (/= ch) str : mySplit ch (drop 1 $ dropWhile (/= ch) str)

    Some tests:

    Navigate to exercises/9.6.1_-_thy_fearful_symmetry.rst.d/thy-fearful-symmetry/ and run stack test for proof it works. (I did not use the main function in the textbook.)

9.7 List comprehensions

9.7.1 Adding predicates

9.7.2 Exercises: Comprehend thy lists

Take a look at the following functions, determine what you think the output lists will be, and then run them in your REPL to verify. (Note that you will need the mySqr list from above in scope to do this.)

Here is mySqr, again, for convenience:

mySqr = [x^2 | x <- [1..10]]

  1. [x | x <- mySqr, rem x 2 == 0]

  2. [(x,y) | x <- mySqr, y <- mySqr, x < 50, y > 50]

  3. take 5 [(x,y) | x <- mySqr, y <- mySqr, x < 50, y > 50]

I’ve tested these out in a terminal session. My guesses are left as comments in it.

There is also a stack project under exercises/9.7.2_-_compehend_thy_lists.rst.d/ that includes tests you can run by navigating to that directory and then running stack test.

9.7.3 List comprehensions with strings

9.7.4 Exercises: Square Cube

Given the following:

mySqr = [x^2 | x <- [1..5]]
myCube = [x^3 | x <- [1..5]]

  1. First write an expression that will make tuples of the outputs of mySqr and myCube.

    
one = [ (x,y) | x <- mySqr, y <- myCube]

  2. Now alter that expression so that it only uses the x and y values that are less than 50.

    
two = [ (x,y) | (x,y) <- one, x < 50 && y < 50 ]

  3. Apply another function to that list comprehension to determine how many tuples inhabit your output list.

    Navigate to exercises/9.7.4_-_square_cube.rst.d/square-cube/ and run stack test to verify.

9.8 Spines and nonstrict evaluation

The spine is the structure of a collection type that arranges values in some order.

The spine is the connective structure that links a composite data-structure together. In the case of a list, it’s the succession of nested cons data constructors (and the final empty list data constructor), like so: _ : _ : _ : [].

Lists aren’t constructed until they’re consumed. Until a value is consumed, there is a series of placeholders as a blueprint of the lists that can be constructed when it’s needed.

Also, functions can traverse the spine of a list without forcing evaluation of the values within that list.

Another way of phrasing this is: You can evaluate the cons data constructors in a spine without forcing evaluation of the arguments to those constructors.

Evaluation of the spine proceeds down the spine. However, constructing the list (when that is necessary) proceeds up the spine.

9.8.1 Using GHCi’s :sprint command

9.8.2 Spines are evaluated independently of values

Values in Haskell get reduced to weak head normal form by default.

Weak head normal form means the expression is only evaluated as far as is necessary to reach a data constructor or a lambda awaiting an argument.

Also, since Haskell uses an outermost reduction strategy, the subexpressions within the lambda or data constructor don’t need to be evaluated.

To determine if something is in WHNF we only have to look at the outermost part of the expression. If it’s a data constructor or lambda, it’s in WHNF. If it’s a function application, it’s not.

Evaluation of the list goes “down the spine” (left to right). Construction of the lists goes “up the spine” (right to left).

Functions that are spine strict can force complete evaluation of the spine of a list even if they don’t force evaluation of each value.

9.8.3 Exercise: Bottom Madness

9.8.3.1 Will it blow up?

Will the following expressions return a value or be ⊥ ?

(NB: I had a hard time writing test for this, so I’ve also included an expect script and asciinema recordings under exercises/9.8.3*.rst.d/ as proof to myself that I’ve done the work.)

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

    Prediction: The code should expand to a list like this. Until forced, though, the elements (x^y) remain unevaluated.

    [ (1 ^ 2), (2 ^ undefined)
, (2 ^ 2), (2 ^ undefined)
, (3 ^ 2), (3 ^ undefined)
, (4 ^ 2), (4 ^ undefined)
, (4 ^ 2), (4 ^ undefined)
]

    Since undefined is forced by the (^) operator, it should crash after getting as far as 1 : _ in the evaluation process.

    Result:

    ·∾ [ x^y | x <- [1..5], y <- [2,undefined]]
[1,*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:2:30 in interactive:Ghci
1

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

    Prediction:

    [1]

    We’re only taking one element of that expanded expression, so the second element won’t be forced, meaning no exception is thrown.

    Result:

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

  3. sum [1, undefined, 3]

    Prediction: Sum forces evaluation of all elements in a list, in order to sum them, so this should throw an exception.

    Result:

    ·∾ sum [1, undefined, 3]
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:6:9 in interactive:Ghci2

  4. length [1, 2, undefined]

    Prediction: Because length counts the cons constructors, but does not force evaluation of the elements, it will return 3.

    Result:

    ·∾ length [1,2,undefined]
3

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

    Prediction: Length will force the spine, and undefined is part of the spine due to (++ undefined), so it will throw an exception.

    Result:

    ·∾ length $ [1,2,3] ++ undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:21 in interactive:Ghci1

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

    Prediction: [2].

    Result:

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

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

    Prediction: Since we don’t encounter any even numbers before the undefined element the list will continue to be evaluated by filter even, throwing an exception when we get to undefined.

    Result:

    ·∾ take 1 $ filter even [1,3,undefined]
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:27 in interactive:Ghci1

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

    Prediction: This should evaluate to [1].

    Result:

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

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

    Prediction: [1,3].

    Result:

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

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

    Prediction: Take requires three elements, so undefined will be reached and an exception will be thrown.

    Result:

    ·∾ take 3 $ filter odd [1,3,undefined]
[1,3*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:26 in interactive:Ghci1

9.8.3.2 Intermission: Is it in normal form?

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:

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

    NF and WHNF.

  2. 1 : 2 : 3 : 4 : _

    WHNF, but not NF. We reach the outermost data constructor, the rightmost cons.

  3. enumFromTo 1 10

    Neither. This is a fully applied function that has not been reduced. There is no data constructor here, yet, until further reduction happens.

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

    Neither. Fully applied, but not reduced.

  5. sum (enumFromTo 1 10)

    Neither. Same as above.

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

    Neither? It’s fully applied, but not reduced, and it’s not a constructor or lambda awaiting an argument.

  7. (_, 'b')

    WHNF, but not NF. We only need the data constructor (_,_) to be evaluated for WHNF.

9.9 Transforming lists of values

Map doesn’t traverse the whole list and apply the function immediately. The function is applied to the values you force out of the list one by one.

Exercises: More Bottoms

  1. Will the following expression return a value or be bottom?

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

    Because we’re forcing map (+1) on the first element, this will evaluate to bottom and throw an exception.

    Let’s find out:

    ·∾ take 1 $ map (+1) [undefined,2,3]
[*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:80:14 in base:GHC.Err
  undefined, called at <interactive>:231:20 in interactive:Ghci40

  2. Will the following expression return a value?

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

    The result should be [2].

    Let’s find out:

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

  3. Will the following expression return a value

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

    Since we’re taking two elements, this should attempt to apply (+1), and throw an exception.

    Let’s test it:

    ·∾ take 2 $ map (+1) [1,undefined,3]
[2,*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:80:14 in base:GHC.Err
  undefined, called at <interactive>:237:22 in interactive:Ghci41

  4. Describe what this function does in English, then run it.

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

    This function checks for vowels. If an element of the list is a vowel, it’s replaced with True. Otherwise, it’s replaced with False. The result is a list of Boolean values.

    Let’s test it!

    ·∾ itIsMystery "This sentence"
{- This     -} [ False, False, True , False
{- ' '      -} , False
{- sentence -} , False, True , False, False, True, False, False, True
               ]

    (The results are formatted, but it did come from a real GHCi session.)

  5. What will be the result of the following functions:

    1. map (^2) [1..10]

      This should expand to the expression [1^2,2^2,3^2,4^2,5^2,6^2,7^2,8^2,9^2,10^2]. When you press enter in GHCi to evaluate map (^2) [1..10] GHCi will run print it to display the output in the REPL session, forcing the expressions evaluation to [1,4,9,16,25,36,49,64,81,100]. This is the same value as the mySqr list comprehension from previous exercises in this chapter.

      Time to test.

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

·∾ [x^2 | x <- [1..10]]
[1,4,9,16,25,36,49,64,81,100]

    2. map minimum [[1..10],[10..20],[20..30]]

      The GHCi command :doc minimum says it returns the least element of a non-empty Foldable structure. So this should return [1,10,20], I think.

      Let’s find out:

      ·∾ map minimum [[1..10],[10..20],[20..30]]
[1,10,20]

    3. map sum [[1..5],[1..5],[1..5]]

    This should evaluate to [15,15,15].

    ·∾ map sum [[1..5],[1..5],[1..5]]
[15,15,15]

  6. Back in … Wait, what? What are you asking me to do?

    The function to modify, from figure 22 in section 9.9.

    ite x = map (\x -> if x == 3 then (-x) else (x))

    Write this function in terms of Data.Bool (bool), instead of the if-then-else expression.

    Ok, here is the function rewrittten to use bool.

    ·∾ eti = map (\x -> bool x (negate x) (x == 3))

·∾ eti [1..10]
[1,2,-3,4,5,6,7,8,9,10]

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

·∾ ite [1..10] == eti [1..10]
True

9.10 Filtering lists of values

filter :: (a -> Bool) -> [a] -> [a]
filter _ []        = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

9.10.1 Exercises: Filtering

  1. Given the following example, from figure 5:

    ·∾ filter (\x -> x `elem` "aeiou") "abracadabra"
"aaaaa"

·∾ [ x | x <- "abracadabra", x `elem` "aeiou" ]
"aaaaa"

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

    A quick attempt in GHCi:

    ·∾ filter (\x -> x `mod` 3 == 0) [1..30]
[3,6,9,12,15,18,21,24,27,30]

  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?

    A quick attempt in GHCi:

    ·∾ length $ filter (\x -> x `mod` 3 == 0) [1..30]
10

  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"
]

    You may recall that earlier in this chapter, we asked you to write a function that separates a string into a list of strings by separating them at spaces. That is a standard library function called words. You may consider starting this exercise by using words (or your own version, of course).

    A super quick implementation in GHCi:

    ·∾ :{
 ⋮ myFilter l =
 ⋮   filter (not . flip elem articles) w
 ⋮   where
 ⋮     w = words l
 ⋮     articles = ["the","a","an"]
 ⋮ :}

·∾ myFilter "the brown dog was a goof"
["brown","dog","was","goof"]

    I’m in a rush today. I’ll have to make a stack project with a more complete solution for this later. Actually, nevermind, this is enough.

9.11 Zipping lists

9.11.1 Zipping exercises

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

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

    Here is my attempt:

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

  2. Do what you did for zip but now for zipWith:

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

    Here is my attempt:

    
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f [] _ = []
zipWith' f _ [] = []
zipWith' f (x:xs) (y:ys) = (f x y) : zipWith' f xs ys
-- zipWith' f xs ys = [ f x y | x <- xs, y <- ys]

  3. Rewrite your zip in terms of the zipWith you wrote.

    Here is my attempt:

    
zip'Refactored :: [a] -> [b] -> [(a,b)]
zip'Refactored = zipWith' (,)

9.12 Chapter Exercises

9.12.1 Data.Char

  1. Query the types of isUpper and toUpper:

    ·∾ :type isUpper
isUpper :: Char -> Bool

·∾ :type toUpper
toUpper :: Char -> Char

  2. Write a function that filters for uppercase letters.

    
onlyUpper = filter isUpper

  3. Write a function that capitalizes the first letter of a string.

    
capFirstLetter [] = []
capFirstLetter (x:xs) = toUpper x : xs

  4. Make a recursive version that capitalizes all the letters.

    
{-# ANN capAll ("HLint: Ignore all" :: String) #-}
capAll [] = []
capAll (x:xs) = toUpper x : capAll xs

  5. Write a function that will capitalize the first letter of a string and return only that letter.

    
firstCapCh [] = error "cannot convert empty string to char"
firstCapCh x = toUpper $ head x

-- Another version, using Maybe to represent the
-- possiblity of failure instead of execptions.
-- firstCapChMaybe :: String -> Maybe Char
-- firstCapChMaybe  [] = Nothing
-- firstCapChMaybe (x:_) = Just (toUpper x)

  6. Now rewrite it as a composed function.

    
firstCapChPointfree = toUpper . head

9.12.2 Ciphers

Your goal in this exercise is to write a basic Caesar cipher that shifts rightward.

You want your shift to wrap back around to the beginning of the alphabet, so that if you have a rightward shift of three from ‘z’, you end up back at ‘c’ and not somewhere in the vast Unicode hinterlands.

You should include an unCaesar function that will decipher your text, as well. In a later chapter, we will test it.

Here is my attempt:

module Lib where
import Data.Char (ord, chr, toLower, toUpper, isUpper)
import Data.Maybe (fromJust)
import Data.List (elemIndex)


alpha = "abcdefghijklmnopqrstuvwxyz"


shift :: Int -> Char -> Char
shift n c
  | toLower c `elem` alpha && isUpper c =  toUpper (alpha !! newIndex)
  | toLower c `elem` alpha              =  (alpha !! newIndex)
  | otherwise                           =  c
  where
    newIndex = (oldIndex + n) `mod` 26
    oldIndex = fromJust (elemIndex (toLower c) alpha)


unshift :: Int -> Char -> Char
unshift n c = shift (-n) c

Here are some tests:

import Test.Hspec
import Lib

main = hspec $ do

  describe "shift" $ do
    it "zero" $ do
      shift 0 'a' `shouldBe` 'a'
    it "positive" $ do
      shift 1 'a' `shouldBe` 'b'
    it "positive from 'z'" $ do
      shift 3 'z' `shouldBe` 'c'
    it "negative" $ do
      shift (-5) 'a' `shouldBe` 'v'
    it "non alpha character" $ do
      shift 8 '.' `shouldBe` '.'
    it "uppercase character" $ do
      shift 3 'A' `shouldBe` 'D'
    it "w ==> x" $ do
      shift 1 'w' `shouldBe` 'x'
    it "sentence" $ do
      map (shift 1) "Attack at dawn." `shouldBe` "Buubdl bu ebxo."
      map (shift 2) "Attack at dawn." `shouldBe` "Cvvcem cv fcyp."

  describe "unshift" $ do
    it "1 a ==> z" $ do
      unshift 1 'a' `shouldBe` 'z'
    it "sentence" $ do
      map (unshift 9) "Attack at dawn." `shouldBe` "Rkkrtb rk urne."
      map (unshift 1) "Buubdl bu ebxo." `shouldBe` "Attack at dawn."
      map (unshift 2) "Cvvcem cv fcyp." `shouldBe` "Attack at dawn."

9.12.3 Writing your own standard functions

Below are the outlines of some standard functions. The goal here is to write your own versions of these to gain a deeper understanding of recursion over lists and how to make functions flexible enough to accept a variety of inputs. You could figure out how to look up the answers, but you won’t do that, because you know you’d only be cheating yourself out of the knowledge. Right?

Let’s look at an example of what we’re after here. The and function takes a list of Bool values and returns True if and only if no values in the list are False. Here’s how you might write your own version of it:

-- direct recursion, not using (&&)
myAnd :: [Bool] -> Bool
myAnd [] = True
myAnd (x:xs) =
  if    x == False
  then  False
  else  myAnd xs


-- direct recursion, using (&&)
myAnd :: [Bool] -> Bool
myAnd [] = True
myAnd (x:xs) = x && myAnd xs

And now the fun begins:

  1. myOr returns True if any Bool in the list is True:

    myOr :: [Bool] -> Bool
myOr = undefined

    Here is my attempt:

    
myOr :: [Bool] -> Bool
myOr [] = False
myOr (x:xs) = x || myOr xs

  2. myAny returns True if a -> Bool applied to any of the values in the list returns True:

    myAny :: (a -> Bool) -> [a] -> Bool
myAny = undefined

    Example for validating myAny:

    Prelude> myAny even [1, 3, 5]
False

Prelude> myAny odd [1, 3, 5]
True

    Here is my attempt:

    
myAny :: (a -> Bool) -> [a] -> Bool
myAny p [] = False
myAny p (x:xs) = p x || myAny p xs

  3. After you write the recursive myElem, write another version that uses any. The built-in version of elem in GHC 7.10 and newer has a type that uses Foldable instead of the list type, specifically.

    You can ignore that and write the concrete version that works only for lists:

    myElem :: Eq a => a -> [a] -> Bool

    Here’s an example of myElem’s use in GHCi:

    Prelude> myElem 1 [1..10]
True

Prelude> myElem 1 [2..10]
False

    Here is my attempt:

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

  4. Implement myReverse:

    Function stub:

    myReverse :: [a] -> [a]
myReverse = undefined

    Example use:

    Prelude> myReverse "blah"
"halb"

Prelude> myReverse [1..5]
[5,4,3,2,1]

    Here is my attempt:

    
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x:xs) = myReverse xs ++ [x]


-- Question 4, take two.
myRev :: [a] -> [a]
myRev l  = go l []
  where
    go [] new = new
    go (x:xs) new = go xs (x:new)

  5. squish flattens a list of lists into a list:

    squish :: [[a]] -> [a]
squish = undefined

    Here is my attempt:

    
squish :: [[a]] -> [a]
squish [] = []
squish (x:xs) = x ++ squish xs

  6. squishMap maps a function over a list and concatenates the results.

    Function stub:

    squishMap :: (a -> [b]) -> [a] -> [b]
squishMap = undefined

    Demonstration of use in GHCi:

    Prelude> squishMap (\x -> [1, x, 3]) [2]
[1,2,3]
Prelude> squishMap (\x -> "WO "++[x]++" HOO ") "123"
"WO 1 HOO WO 2 HOO WO 3 HOO "

    Here is my attempt:

    
squishMap :: (a -> [b]) -> [a] -> [b]
squishMap f [] = []
squishMap f l  = (squish . map' f) l
  where
    map' g [] = []
    map' g (x:xs) = g x : map' g xs

  7. squishAgain flattens a list of lists into a list. This time, re-use the squishMap function:

    squishAgain :: [[a]] -> [a]
squishAgain = undefined

    Here is my attempt:

    
squishAgain :: [[a]] -> [a]
squishAgain = squishMap id

  8. myMaximumBy takes a comparison function and a list and returns the greatest element of the list based on the last value that the comparison returns GT for. If you import maximumBy from Data.List, you’ll see that the type is:

    Foldable t => (a -> a -> Ordering) -> t a -> a

    Rather than:

    (a -> a -> Ordering) -> [a] -> a

    Here is your starting point:

    myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy = undefined

    Demonstration:

    Prelude> xs = [1, 53, 9001, 10]
Prelude> myMaximumBy compare xs
9001

    Here is my attempt:

    
myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy _ [] = error "myMaximumBy does not work on empty lists"
myMaximumBy p (e:l)
  | all (\x -> x == GT || x == EQ) (map (e `p`) l) = e
  | otherwise = myMaximumBy p l

  9. myMinimumBy takes a comparison function and a list and returns the least element of the list based on the last value that the comparison returns LT for.

    Function stub:

    myMinimumBy :: (a -> a -> Ordering) -> [a] -> a
myMinimumBy = undefined

    Demonstration:

    Prelude> xs = [1, 53, 9001, 10]
Prelude> myMinimumBy compare xs
1

    Here is my attempt:

    
myMinimumBy :: (a -> a -> Ordering) -> [a] -> a
myMinimumBy p [] = error "myMinimumBy only works on nonempty finite lists"
myMinimumBy p (e:l)
  | all (\x -> x == LT || x == EQ) (map (e `p`) l) = e
  | otherwise = myMinimumBy p l

  10. Using the myMinimumBy and myMaximumBy functions, write your own versions of maximum and minimum. If you have GHC 7.10 or newer, you’ll see a type constructor that wants a Foldable instance instead of a list, as has been the case for many functions so far:

    myMaximum :: (Ord a) => [a] -> a
myMaximum = undefined

myMinimum :: (Ord a) => [a] -> a
myMinimum = undefined

    Here is my attempt:

    
myMaximum :: (Ord a) => [a] -> a
myMaximum = myMaximumBy compare


myMinimum :: (Ord a) => [a] -> a
myMinimum = myMinimumBy compare