Lecture 3

The third lecture covered up to slide 9 in the lecture slides.

You should have learnt about lists, list comprehensions, and QuickCheck and you should now be able to attempt the list comprehension parts of the tutorial exercise.

The required reading is chapters 4 to 7 in the textbook (pp. 67-176).

Today’s material was particularly important because lists are a fundamental data structure in Haskell. Understanding how lists, comprehensions, and recursion (to come in the next lecture) work are key to understanding the rest of the course. Much of the material to come will be built upon these concepts. So:

  • Keep on top of the reading! There is a lot of material in the textbook so reading small sections frequently will allow you to get through it all in time for the next class. Try the exercises!
  • Get started on the tutorial exercises! You must have these done ready for your tutorial class. The sooner  you start, the more time you’ll have to ask for help if you get stuck. And do ask for help.
  • There are no silly questions, only silly people who don’t ask questions!
  • Don’t forget that you can ask questions by posting comments on this blog. This is useful for your classmates as everyone will see the answers.

Extra notes:

Also in today’s lecture pairs were introduced. A pair (a,b) and in general an n-tuple (a,b,c,…) differs from a list in the following ways:

  1. Lists can hold an arbitrary number of items, but tuples contain a fixed number (e.g. a pair contains two items, a triple or 3-tuple contains three items, an n-tuple contains n items).
  2. The items in a list must all be of the same type, but in a tuple each item may have a different type.
This entry was posted in Uncategorized. Bookmark the permalink.

8 Responses to Lecture 3

  1. s1245688 says:

    Hi, I have a question about one of the optional problems (9). This is what I got:
    Non-exhaustive patterns in function crosswordFind’:
    ‘a’ 0 0 “”
    Should we look for a word of length 0 that has ‘a’ in any position? Is QuickCheck always a good way of checking?

    • Chris B says:

      Your first problem is that final argument of crosswordFind should be a [String], list of Strings, here you are giving it “” which is just a String (albeit an empty one). This should give a type error. I suspect your definition of crosswordFind is incorrect, but as you haven’t said what it is, then I can’t suggest where you might have gone wrong.

  2. s1245688 says:

    I didn’t know the way system posts comments here, I should’ve signed.
    Kuba Kowalski

  3. s1208447 says:

    It’s probably useless now, but lets say we take general example:
    crosswordFind ch n len words

    We have few corner cases now:
    The first one is n >= len. It is malformed input (e.g. we have a word of two symbols and willing to match the fourth symbol), so we can choose to either gracefully finish the computation (with the obvious answer []) or just do nothing and hope for the best (more on that later).
    Next, len should be positive integer and n should be non negative, it’s quite straightforward – we can’t have a string of negative length and we index list members from 0.
    We can just skip checking for words being an empty list in list comprehension task, as [x | x <- []] == []. (or at least on my machine it says so)

    Therefore one should either use guards to do a proper work in these cases or limit quickCheck property generators (I guess it’s written in a book somewhere or in documentation here)

    I suppose it is easier to just write a few guards turning down the invalid input. :)
    Then your case (‘a’ 0 0 []) would be resolved easily – we have empty words and we are trying to pick a first symbol, which obviously won’t work.

    As for quickCheck being a good way of testing – there’s a chapter about that in a course book (9.2 chapter, if I’m not mistaken), in short – it is not the best thing, but it is better than doing absolutely nothing and expecting that everything will work just fine.

    Regards,
    Andrius Ziukas

    • Chris B says:

      Quite correct. Your answer should deal directly with the corner cases you describe. You can include constraints in a comprehension:
      [x | x⟵y, x>3] where y is a list of Ints the result will be a list of Ints greater than 3.
      and likewise you can include a guard in your recursive version.

      When the corner cases are dealt with in the function any bad input given by quickCheck will be dealt with correctly and in the same way by both your comprehension and recursive versions.

    • Chris B says:

      Just a note that “” and [] are not the same.
      “” is the empty String, which has type String (or [Char]).
      [] is the empty list which has type [a] — this is a polymorphic type, the ‘a’ is a wildcard type so [a] is a list of any type.

      • s1208447 says:

        Yes, I supposed that Kuba meant to write crosswordFind ‘a’ 0 0 [],
        as it should get a [String] list (I am not sure whether we should use terminating cases such as func “” = “” if we have func :: String -> String or func [] = [])

        Actually it is fairly strange to see that there is no obvious way for quickcheck to say “a should be generated so that it is lower than b”. In normal circumstances we always should implement all the corner cases (and maybe even add exceptions/error messages/whatever), but I am not sure how much emphasis should we put on these things during the university course (at least in intro courses).

        P.S. I am not complaining about “why we should write corner cases when we can ask quickcheck to behave”, but more like “why should quickcheck test all these invalid inputs when the bug most likely replicates in correct input range”.

        Regards,
        Andrius

        • Chris B says:

          As your base case in list recursion is usually going to look like fun [] = [], then I’d suggest you stick to that. However, you’re right that if fun :: String -> String then you can use either.

          “why should quickcheck test all these invalid inputs when the bug most likely replicates in correct input range”

          I disagree. The most serious bugs in the wild tend to be the improper handling of exception cases and the lack of checking that a function’s input matched the thing it’s expecting. Strongly typed languages like Haskell go some way to making sure that a function can only take the correct input, but you still need to be careful if you want to restrict the values of a certain type that a function will take.
          In this course, the exception cases for functions will be kept fairly simple and you will be expected to deal with them properly to get full marks (and be a good programmer!).

Leave a Reply