Haskell/Solutions/Lists and tuples

From Wikibooks, open books for an open world
Jump to: navigation, search

← Back to Lists and tuples


Building lists[edit]

Exercises
  1. Would the following piece of Haskell work: 3:[True,False]? Why or why not?
  2. Write a function cons8 that takes a list and conses 8 on to it. Test it out on the following lists by doing:
    1. cons8 []
    2. cons8 [1,2,3]
    3. cons8 [True,False]
    4. let foo = cons8 [1,2,3]
    5. cons8 foo
  3. Adapt the above function in a way that 8 is at the end of the list
  4. Write a function that takes two arguments, a list and a thing, and conses the thing onto the list. You should start out with:
     let myCons list thing =
  1. This won't work. [True, False] is a list of booleans, 3 is an integer.
  2. let cons8 list = 8:list, let cons8 = (:) 8 and let cons8 list = (:) 8 list are all valid functions.
    1. cons8 [] returns [8]
    2. cons8 [1,2,3] returns [8,1,2,3]
    3. cons8 [True,False] gives a type error. This is the same mistake as in exercise 1.
    4. let foo = cons8 [1,2,3] gives no output message, but foo is [8,1,2,3]. Try it!
    5. cons8 foo (assuming you did 2.4) returns [8,8,1,2,3]
  3. As recognized let cons8 list = list:8 does not work, cause 8 is not a list, but let cons8 list = list ++ [8] will work since (++) concatenates 2 lists
  4. let myCons list thing = thing : list, let myCons list thing = (:) thing list are both valid functions.

Lists within lists[edit]

Exercises
  1. Which of these are valid Haskell and which are not? Rewrite in cons notation.
    1. [1,2,3,[]]
    2. [1,[2,3],4]
    3. [[1,2,3],[]]
  2. Which of these are valid Haskell, and which are not? Rewrite in comma and bracket notation.
    1. []:[[1,2,3],[4,5,6]]
    2. []:[]
    3. []:[]:[]
    4. [1]:[]:[]
    5. ["hi"]:[1]:[]
  3. Can Haskell have lists of lists of lists? Why or why not?
  4. Why is the following list invalid in Haskell?
    1. [[1,2],3,[4,5]]
  1. 1 and 2 aren't valid Haskell, 3 is valid:
    1. 1:2:3:[]:[]. 1, 2 and 3 are integers, while [] is a list.
    2. 1:(2:3:[]):4:[]. Again, 1 and 4 are integers, and 2:3:[] is a list of integers.
    3. (1:2:3:[]):[]:[]. This is valid Haskell, as 1:2:3:[] is a list of integers, and [] is an empty list (of any type).
  2. The first four are valid Haskell. The fifth is not.
    1. [[],[1,2,3],[4,5,6]]. Both [1,2,3] and [4,5,6] are lists of integers. The whole list is a list of lists of integers. We can cons an empty list (of any type) in front of it.
    2. [[]]. Not the empty list!. This is a list containing an empty list. The list itself is not empty, because it has one element!
    3. [[],[]]. This is a list containing two empty lists.
    4. [[1],[]]. This is the same list as the previous, but with a [1] as the first element instead of []. Since the list was a lists of lists, it now has become a list of list of integers.
    5. [["hi"], [1]]. ["hi"] is a list of Chars while [1] is a list of integers.
  3. Yes, this is possible. For example: [[[1],[2],[3]],[[4],[5],[6]],[[7],[8],[9]]]. Why? You can make a list of anything! If you already have a list of some type, then you can make a list of lists of that type. The example list would be written as: ((1:[]):(2:[]):(3:[]):[]):((4:[]):(5:[]):(6:[]):[]):((7:[]):(8:[]):(9:[]):[]):[]
  4. The list [[1,2],3,[4,5]] is not valid because it is equivalent to (1:2:[]):3:(4:5:[]):[], where we try to cons elements that have different types (i.e. list and numeric). Lists in Haskell must be type-homogeneous. A valid list would be [[1,2],[3],[4,5]], equivalent to (1:2:[]):(3:[]):(4:5:[]):[].

A different notion of many[edit]

Exercises
  1. Write down the 3-tuple whose first element is 4, second element is "hello" and third element is True.
  2. Which of the following are valid tuples ?
    1. (4, 4)
    2. (4, "hello")
    3. (True, "Blah", "foo")
  3. Lists can be built by consing new elements onto them: you cons a number onto a list of numbers, and get back a list of numbers. It turns out that there is no such way to build up tuples.
    1. Why do you think that is?
    2. Say for the sake of argument, that there was such a function. What would you get if you "consed" something on a tuple?
  1. (4,"hello",True)
  2. They all are! Tuples aren't restricted to types.
    1. A tuple of two integers.
    2. A tuple of an integer and a string.
    3. A tuple of a boolean and two strings.
    1. Maybe the creators of Haskell wanted to limit the functionality of tuples to discourage their overuse. The practice of feeding functions cons-able tuples, instead of lists and tuples, may have made functions more complex, therefore harder to read, write and maintain.
    2. Unlike lists, we would obtain a tuple with a different type, because the tuple size would be bigger.

Tuples within lists and other combinations[edit]

Exercises
  1. Which of these are valid Haskell, and why?
    • 1:(2,3)
    • (2,4):(2,3)
    • (2,4):[]
    • [(2,4),(5,5),('a','b')]
    • ([2,4],[2,2])
    • Not valid. (2,3) is a tuple, and cons, (:), only works with lists.
    • Not valid. (2,3) is a tuple, and cons, (:), only works with lists.
    • Valid. You'll get a list of tuples of an integer and an integer: [(2,4)]
    • Not valid. All elements of a list must be of the same type. (2,4) and (5,5) are tuples of an integer and an integer, but ('a','b') is a tuple of a character and a character.
    • Valid. This is a tuple of a list of integers and a list of integers.

Retrieving values[edit]

Exercises
  1. Use a combination of fst and snd to extract the 4 from the tuple (("Hello", 4), True).
  2. Normal chess notation is somewhat different to ours: it numbers the rows from 1-8 and the columns a-h; and the column label is customarily given first. Could we label a specific point with a character and a number, like ('a', 4)? What important difference with lists does this illustrate?
  3. Write a function which returns the head and the tail of a list as the first and second elements of a tuple.
  4. Use head and tail to write a function which gives the fifth element of a list. Then, make a critique of it, pointing out any annoyances and pitfalls you can identify.
  1. snd (fst (("Hello", 4), True)) returns 4.
  2. Yes, we can! The difference between a tuple and a list is that all elements of a list must be of the same type (integers, booleans, etc.), but you can add elements to the list. The elements of a tuple can be of any type you want, like a tuple of an integer and a character in (4, 'a'), but you can't change its size.
  3. headAndTail list = (head list, tail list)
    
  4. fifthElement list = head (tail (tail (tail (tail list))))
    
    Inconveniences of this implementation include the clunkiness of the definition, its lack of generality (what if we wanted to get the fourth or the sixth or the nineteenth element?), and the fact it will cause the program to crash whenever it is passed a list with less than five elements.

Polymorphic types[edit]

Exercises

Give type signatures for the following functions:

  1. The solution to the third exercise of the previous section ("... a function which returns the head and the tail of a list as the first and second elements of a tuple").
  2. The solution to the fourth exercise of the previous section ("... a function which gives the fifth element of a list").
  3. h x y z = chr (x - 2) (remember we discussed chr in the previous chapter).
  1. headAndTail :: [a] -> (a, [a])
    
  2. fifthElement :: [a] -> a
    
  3. h x y z :: Int -> a -> b -> Char -- y and z are not actually used, so their types could be anything