Introduction to Functional Programming – Lab 4TDA555 / DIT440, LP1 2015
Home | Schedule | Labs | Exercises | Exam | About | FAQFire | Forum | TimeEdit | Links
Introduction to Functional Programming – Lab 4TDA555 / DIT440, LP1 2015
Home | Schedule | Labs | Exercises | Exam | About | FAQFire | Forum | TimeEdit | Links
Some notes:

  • Remember that you have to work in pairs. Only groups of size 2 are allowed to submit! Submissions by only 1 person or 3 or more persons will not be accepted by the Fire system.

  • When you are done, please submit your solution using the Fire system.
  • Good luck!

    In this Lab Assignment, you will design and implement a very simple graphical calculator. For the graphical part we will use the Haste compiler which is able to compile Haskell code to an HTML file which can be run in a web browser.

    In this lab, you have a little bit more freedom than in the previous labs; we will not guide you towards a solution as much as in the previous lab assignments.

    Assignments and Deadlines

    The lab consists (again) of two parts.

    Part I of the lab needs to be submitted before Monday, October 19 at 12:00.

    Part II of the lab needs to be submitted before Monday, October 26 at 12:00.

    There are also extra assignments. You can choose freely whether you want to do these.

    The final deadline for the lab is on Wednesday, November 4 at 23:59.



    Before starting on this lab, make sure that you have understood the material from the lectures in week 5.

    Note that Part I is mainly about extending the data type and functions from these lectures. That is, you are not supposed to invent new methods here. Rather, the point is to be able to read and understand the lecture material well enough to do some useful extensions/adjustments to it.

    Some assignments have hints. Often, these involve particular standard Haskell functions that you could use. Some of these functions are defined in modules that you have to import yourself explicitly. You can use the following resources to find more information about those functions:

  • Hoogle, the library function search engine

  • Haskell Library Structure, many standard modules for you to browse.

  • Haste library documentation
  • We encourage you to actually go and find information about the functions that are mentioned in the hints!


    A Graphical Calculator

    The graphical calculator will be implemented as a web page that might look like this:

    The page consists of a drawing area and a text entry field below it. The user can type mathematical expressions in the text entry, which, after pressing the Draw graph button, will be graphically shown on the drawing area.

    The lab assignment consists of two parts. In Part I, you will implement the parts of your program that have to do with expressions. In part II, you will implement the graphical part of your program.


    Part I

    In this part, you are going to design a datatype for modelling mathematical expressions containing a variable x. For example:
  • 3*x + 17.3
  • sin x + cos x
  • sin (2*x + 3.2) + 3*x + 5.7
  • In other words, an expression consists of:
  • Numbers; these can be (positive) integers as well as floating point numbers
  • Variables; there is only one variable, x
  • Operators; for now it is enough with + and *
  • Functions; for now it is enough with sin and cos
  • You will also implement a number of useful functions over this datatype.

    Put the answers for Part I in a module called Expr.hs.

    Note: Don't forget to read the hints below before starting to work on these tasks.


    A. Design a (recursive) datatype Expr that represents expressions of the above kind.

    You may represent integer numbers by floating point numbers; it is not necessary to have two different constructor functions for this.

    B. Implement a function
      showExpr :: Expr -> String
    that converts any expression to string. Use as few parentheses as possible. The strings that are produced should look something like the example expressions shown earlier.

    It is not required to show floating point numbers that represent integer numbers without the decimal part. For example, you may choose to always show 2.0 as "2.0" and not as "2". (But you are free to handle integer numbers if you want.)

    If you want to, you can from now on use this function as the default show function by making Expr an instance of the class Show:

      instance Show Expr where
        show = showExpr
    But you do not have to do this. (Also: see the hint on testing below!)

    C. Implement a function
      eval :: Expr -> Double -> Double
    that, given an expression, and the value for the variable x, calculates the value of the expression.

    D. Implement a function
      readExpr :: String -> Maybe Expr
    that, given a string, tries to interpret the string as an expression, and returns Just of that expression if it succeeds. Otherwise, Nothing will be returned.

    The next assignment is about checking that your definition of readExpr matches up with your definition of showExpr. One could define a property that simply checks that, for any expression e1, if you show it, and then read it back in again as an expression e2, then e1 and e2 should be the same.

    However, this is too strict; there is certain information loss in showing an expression. For example, the expressions "(1+2)+3" and "1+(2+3)" have different representations in your datatype (and are not equal), but showing them yields "1+2+3" for both.

    The lecture notes from week 5 gives two methods for solving this problem – one using eval and one using assoc. In this lab you should only use the assoc method. The reason for not using the eval method is that this lab uses floating point numbers, and due to rounding errors eval may give different results for the expressions x+(y+z) and (x+y)+z.

    E. Write a property
      prop_ShowReadExpr :: Expr -> Bool
    that says that first showing and then reading an expression (using your functions showExpr and readExpr) should produce "the same" result as the expression you started with.

    Also define a generator for expressions:

      arbExpr :: Int -> Gen Expr
    Do not forget to take care of the size argument in the generator.

    Make Expr an instance of the class Arbitrary and QuickCheck the result!

      instance Arbitrary Expr where
        arbitrary = sized arbExpr


    * As stated above, you are not supposed to invent new things here. Just use the relevant bits of code from the lectures in week 5, and extend/adjust them as needed.

    * It is important that your datatype is simple and elegant; try not to use too many data constructors for example. If two different cases can be effectively expressed using one constructor, then do that.

    When designing your datatype Expr, think carefully about how you want to express the variable x. There is a difference between the Expr data type from the lectures: in your data type you only have to represent one variable, called x, whereas in the lectures we allowed for several different variables!

    * When showing and reading expressions, we have to decide where we allow and require parentheses. Parentheses are required only in the following cases:

  • When the arguments of a *-expression use +. For example: (3.1+4.2)*7
  • When the argument of sin or cos uses * or +. For example: sin (3.2*x)
  • In all other cases, you should not require parentheses. For example:
  • Allow 2*3+4*5 instead of 2*3+(4*5)
  • Allow sin x instead of sin(x)
  • Allow sin cos x instead of sin (cos x)
  • Allow sin x + cos x instead of (sin x) + (cos x)
  • Make sure that the above expressions are all parsed correctly by your program!

    * For the function readExpr, to allow spaces in the expression, simply filter out all spaces from the string before you use the parser. In this way, spaces will not mess up your parser and keep it nice and clean.

    * For the function readExpr, to be able to parse floating point numbers (Doubles) and sin and cos, you only have to change the parser for factors.

    To parse floating point numbers, do not try to use the function "number" from the lecture, instead take a look at the standard Haskell functions read and reads. Use it on the right type (Doubles), and see what happens!

      Main> read "17.34" :: Double
      Main> read "17.34cykel" :: Double
      Main> reads "17.34cykel" :: [(Double,String)]

    * When working with the property prop_ShowReadExpr, it might be a good idea to make sure that the property you define will not crash, even if there is something wrong with your functions! A common way for the property to crash is when the readExpr function (unexpectedly) delivers Nothing. Instead of crashing, your property should return False in that case. You can do this by doing a case expression on the result of readExpr, or by adding that the result of readExpr should not be equal to Nothing before you check that the result is of the shape Just e.

    * If you have a hard time understanding the generated counter examples for your property, it is probably a good idea to let Haskell derive the show function for your Expr datatype, instead of making your own instance of Show. So, use "deriving Show" on your expression datatype while testing!


    Part II

    In this part, you are going to implement the graphical part of the calculator. To do this, you need to install the Haste compiler: You can read more about how to use Haste in the material for the lecture Haskell in the Browser. That page introduces a number of helper functions which are available in the module Pages.hs. It is recommended that you use this module for your calculator web page. However, you are free to design the web page as you want, and it is not required to use the helper functions.

    The graphical interface consists of two parts: (1) the drawing area, where the function is going to be drawn, and (2) the text entry field.

    The drawing area is a "canvas" element of a certain size (you decide yourself, but let us suppose it has width and height of 300). A canvas has a coordinate system that works in pixels. Here is how it works:

    (0,0) (300,0)
    (0,300) (300,300)

    Perhaps surprising is that y-coordinates are upside down; they are 0 at the top, and 300 at the bottom.

    The tricky thing using this canvas to draw our functions is that the coordinate system we are used to in mathematics has (0,0) in the middle, and the y-coordinates are not upside down. For example, the coordinate system for our functions might work like this:

    (-6.0,6.0) (6.0,6.0)
    (-6.0,-6.0) (6.0,-6.0)

    So, some conversion is needed between pixels and mathematical coordinates. Note, though, that both coordinate systems are represented using the type Double.

    On the Chalmers computers, QuickCheck is installed together with Haste. On your personal computers, you can try to install QuickCheck in Haste by running

    > haste-cabal update
    > haste-cabal install QuickCheck
    If, for some reason, this doesn't work, you need to remove the testing code (assignment E) from Expr.hs and put it in a separate module ExprQC.hs. Then ExprQC.hs should not be imported by any code that is compiled by Haste.

    The answers for Part II should be put in a module called Calculator.hs. The modules Calculator and ExprQC should of course import the module Expr.

    In this lab you are free to be creative when designing the calculator. But for those who just want to focus on the important stuff, we have prepared a stub program that constructs the web page for you: Calculator.hs. This file makes use of Pages.hs which is mentioned above.


    F. Implement a function with the following type.
      points :: Expr -> Double -> (Int,Int) -> [Point]
    The function gets three arguments; points exp scale (width,height):
  • An expression exp
  • A scaling value scale
  • The width and height of the drawing area
  • The type Point is already defined in Haste, and is just a pair of floating-point values:
      type Point = (Double, Double)
    The idea is that points will calculate all the points of the graph in terms of pixels. The scaling value tells you the ratio between pixels and floating point numbers. The arguments width and height tell you how big the drawing area is. We assume that the origin (0,0) point is in the middle of our drawing area.

    For the canvas and function coordinate systems above, we would use 0.04 for the scale (since 1 pixel corresponds to 0.04 in the floating point world, this is (6.0 + 6.0) / 300), and (300,300) for the width and height.

    G. Implement the graphical user interface that connects assigments A–F into a web-based graphical calculator.

    If you are basing your code on the provided module Calculator.hs, this part only involves completing the function

    readAndDraw :: Elem -> Canvas -> IO ()
    which reads the expression from the given input element and draws the graph on the given canvas.

    When the user types in something that is not an expression, you may decide yourself what to do. The easiest thing is to draw nothing.


    To convert back and forth between Ints and Doubles, the following function might come in handy:

      fromIntegral :: Int -> Double
    This function has a more general type than the one given above. For other conversion functions, use Hoogle!

    To implement the function points, it is probably a good idea to define the following two local helper functions:

        pixToReal :: Double -> Double  – converts a pixel x-coordinate to a real x-coordinate
        pixToReal x = ...
        realToPix :: Double -> Double  – converts a real y-coordinate to a pixel y-coordinate
        realToPix y = ...

    The easiest way to draw the graph on the canvas is to use the function path,

    path :: [Point] -> Shape ()
    which makes a curve from a list of points.

    Another alternatives (which seems to give smother curves when there are sharp edges) is to draw the curve manually as a sequence of lines. To do this, you can define a helper function of type:

    linez :: Expr -> Double -> (Int,Int) -> [(Point,Point)]
    The function gets the same arguments as points, only it will calculate the lines that are going to be drawn between the points. So simply create a line (as a pair of points) between each consecutive point generated by points.

    The Haste page has several examples relevant for this assignment. In particular:

  • The Bouncing Balls example for the use of canvas
  • The Echo example for the use of text entries

    Extra Assignments

    You can choose freely whether to do one of these. You will learn more when you do!

    Extra Assignments

    X. Change the type and implementation of the readExpr function so that it produces a useful error message when something goes wrong. Use the function
      alert :: String -> IO ()
    to report the error in the browser.

    Hint: Change the result type from Maybe Expr to Either String Expr, where the string can hold an error message.

    Y. Implement some form of zooming. There are a number of ways to do this. Either the user clicks somehwere on the canvas, and the drawing function zooms around that point. Or there could be a text entry where the scaling factor can be given.

    Make sure you also add a way to zoom out after you have zoomed in.

    Z. Add a button "Differentiate" that calculates the derivative of the function, and displays that instead. You could also add a button "Integrate" that goes the other way. A good idea here would probably be to also simplify the produced results.

    P. Add a way for the user to enter multiple functions. These should all be drawn in a different colors.

    Q. Increase the expressiveness of the Expr datatype by adding more functions. Add at least -, / and tan. You have to deal with what happens when a function value is undefined! An example is the function 2/x, which is undefined in the point 0.



    Submit your solutions using the Fire system.

    Your submission should consist of the following files:

  • Expr.hs

  • ExprQC.hs

  • Calculator.hs

  • report.txt (optional), a text-file containing explanations and discussion, if you deem this neccessary. Note: You have to submit report.txt if your solution is incomplete! In this file, you describe how far you have come, what you have tried on the assignments you did not succeed on, and what you are stuck on. Also clearly describe what extra assignment you did.
  • Before you submit your code, Clean It Up! Remember, submitting clean code is Really Important, and simply the polite thing to do. After you feel you are done, spend some time on cleaning your code; make it simpler, remove unneccessary things, etc. We will reject your solution if it is not clean. Clean code:

  • Does not have long lines (< 78 characters), and no tab characters

  • Has a consistent layout

  • Has type signatures for all top-level functions

  • Has good comments

  • Has no junk (junk is unused code, commented code, unneccessary comments)

  • Has no overly complicated function definitions

  • Does not contain any repetitive code (copy-and-paste programming)
  • To the Fire System

    Good Luck!