Haskell Basics #3

Tuples and Lists

We have already encountered tuples prior, albeit very briefly. Now we will introduce them alongside their cousin, lists.

Tuples are hereogenous, meaning that their elements may be of different types.

aTuple = (1, 2, 34)
anotherTuple = (1, "two", (3, "four"))
main = print $ (aTuple, anotherTuple)

The latter anotherTuple consists of an integer, a string, and even another tuple.

In fact the value passed tot he print statement is itself a tuple consisting of two tuples, both of which are of different constituent types.

Lists, on the other hand, are homogenous, menaing that all of their lements must be of the same type.

aList = [1, 2, 34]
anotherList = [1, "two", [3, "four"]]
main = print $ (aList, anotherList)

This fails to evaluate, because all elements need to be the same.

aList = [1, 2, 34]
anotherList = ["one", "two", "thirty four"]
yetAnotherList = [(1, 1), (2, 3), (5, 8)]
main = print $ (aList, anotherList, yetAnotherList)

Now this works, because all of the values within the lists are of the same type.

How do you tell a list apart from a tuple?

aListHasSquareBrackets = [1, 2, 3]
aTupleHasRoundParentheses = (1, 2, 3)

List operations

Prepending an element to a list

anElement = (-22)
anotherElement = 2
aList = [1, 2, 34]
yetAnotherList = anElement:anotherElement:aList
main = print $ (anElement, anotherElement, aList, yetAnotherList)

Prepending a list to another list

anotherList = [(-22), 2]
aList = [1, 2, 34]
yetAnotherList = aList ++ anotherList
main = print $ (anotherList, aList, yetAnotherList)

String concatenation

aStr = "Hello"
bStr = " World!"
concatenatedStr = aStr ++ bStr
main = print $ (aStr, bStr, concatenatedStr)

Turns out that strings are lists of characters: [Char] So strings can be concatenated the same way lists are, pretty cool, eh?

Accessing a list by index

anotherList = [(-22), 2]
aList = [1, 2, 34]
yetAnotherList = aList ++ anotherList
thirdElement = yetAnotherList !! 2
main = print $ (yetAnotherList, thirdElement)

Note that, as with almost all other programming languages, indices start at zero.

Other miscellaneous functions - explore the following: length, head, last, tail, init,

m = [1..7]
--m = []

--x = length m
--x = head m
--x = tail m
--x = last m
--x = init m
--x = reverse m
--x = sum m
--x = product m
--x = minimum m
--x = null m
--x = maximum m

main = print $ (x)

Remove the -- one line at a time to uncomment. Be sure to try each function on both empty and non-empty lists.

Now it is time for an exercise!

Above, we have the function maximum. I want you to define your own function that accomplishes the exact same thing: return the element of the input list which is the largest. We shall call it listMax

listMax m
  -- your code goes here

aList = [(-3)..2]
bList = [1,(-17),3,(-3),(-10),0]
main = do
  print $ listMax aList
  print $ listMax bList

Clues:

Answer (not quite):

listMax m
  | length m == 1 = head m
  | otherwise = max (head m) (listMax (tail m))

aList = [(-3)..2]
bList = [1,(-17),3,(-3),(-10),0]
main = do
  print $ listMax aList
  print $ listMax bList

Congratulations, on making it this far, for you have understood recursion. If you have not done so already, expand the clues above, and have a read of them.

The key idea to formulating this solution is to decompose the problem.

In this case, one would think along the lines of: "The largest element in any list, is the largest element between its first element, and the largest element of the rest of the list"

Thus, you express this in Haskell, as such:

listMax m = max (head m) (listMax (tail m))

What has happened here is that you have expressed the problem using recursion, where the function calls itself on a smaller portion of the original problem.

... and then you think, "What if the list has only got one element, as there will be no rest of the list?" So you extend your expression above, to include: "Except when the list has only got one element, the largest element of this list is its solo element."

listMax m
  | length m == 1 = head m
  | otherwise = max (head m) (listMax (tail m))

What has happened here is that you have thought of a base case for the recursion. Above, the function would call itself recursively, on successively smaller sections of the problem. However, it does not know when to stop - and what you have told it to do here is simply to stop at the last element.

Great, now you have conquered recursion, including an understanding of base cases. There is one more base case that you will need to add.

A clue to get you to the final answer:

cList = [] :: [Int]

You will need to modify listMax to be able to handle empty lists. Why we need :: [Int] at the end of our definition: - The Haskell compiler cannot infer the type of an empty list, as there are no values within it. Thus, when we attempt to pass it into a function containing max it will fail - because max needs to know the type of its input. - The reason why it works for the other lists is because Haskell does type inference, which is, as the name suggests, inferring the types based on their contents. This is useful, because you do not need to declare all your types in the general case - just the ones which need to be explicitly stated.

  print $ cList

Add this print statement to your implementation to test it.

Answer:

listMax m
  | null m = error "No maximum in empty list"
  | length m == 1 = head m
  | otherwise = max (head m) (listMax (tail m))

aList = [(-3)..2]
bList = [1,(-17),3,(-3),(-10),0]
cList = [] :: [Int]
main = do
  print $ listMax aList
  print $ listMax bList
  print $ listMax cList

Another exercise!

Now that you have got your your brain muscles flexing, time to try another - just to get used to the concept of recursion.

Write a minList function, which is exactly the same as maxList, except that it finds the smallest element in a list.

Answer:

listMin m
  | null m = error "No minimum in empty list"
  | length m == 1 = head m
  | otherwise = min (head m) (listMin (tail m))

aList = [(-3)..2]
bList = [1,(-17),3,(-3),(-10),0]
cList = [] :: [Int]
main = do
  print $ listMin aList
  print $ listMin bList
  print $ listMin cList

This time around it should have been much easier. In fact, all you really had to do, besides changing the name of the function, was to swap max for min!

Note that these implementations still leave a lot to be desired. If you so wish, take a look at Haskell's own implementation of minimum and maximum.

Sections

Tuples and Lists

List operations