USING STRUCTURED DATA

Review: using lists

List is a powerful generalization which enables us to store and process multiple values in a single container. We have managed to accomplish a great deal by using list, first, and rest only. For example:

    (define (listLength list)
        (cond
            ((empty? list) 0)
            (else (+ 1 (listLength (rest list))))))
    (check-expect (listLength (list 1 2 3)) 3)

    (define (listSum list)
        (cond
          ((empty? list) 0)
          (else (+ (first list) (listSum (rest list))))))
    (check-expect (listSum (list 1 2 3)) 6)

    (define (listAverage list)
      (/ (listSum list) (listLength list)))
    (check-expect (listAverage (list 1 2 3 4)) 2.5)

Using lists to store multiple values: address book

Now consider the problem of keeping an address book. We want to store people's name, phone, and email information. We can use a list to store a single address, by imposing and intended interpretation of the list:

    (list "Ali Ak" "02121111111" "ali@gmail.com")

We can then combine these lists to create an address book:

    (define myAddressBook
      (list 
        (list "Ali Ak" "02121111111" "ali@gmail.com")
        (list "Veli Gök" "02122222222" "veli@gmail.com")))

With the above structure, let's try to access the e-mail of one entry:

    (first (rest (rest (first (rest myAddressBook))))) ;returns "veli@gmail.com"

The need for structured data

The cumbersome and unreadable piece of program above exposes the need for a more appropriate mechanism to express problem specific structure of data. We use the lists to represent structured data items, each of which contains an address item, which is in turn an ordered list of a person's name, phone, and e-mail. While a list is sufficient to store information, it is not appropriate for expressing problems.

Similar problems arise if we wish to store, for example, storing student records in the university, storing courses taken by a student, or shapes in a drawing, etc.

Structure definition

Here we introduce the mechanism for creating data structures. For example we can define a structure to store a vector in a two dimensional coordinate space as follows:

    (define-struct Vector (x y))

In general, a structure type definition has the following form:

    (define-struct StructureName (FieldName ... FieldName))

Defining a structure automatically creates definitons of functions to operate on the structure, for three primitive operations:

Revisiting address book

With the structure mechanism we can express an adress book in an appropriate manner:

    (define-struct Address (name phone email))
    (define myAddressBook 
      (list
       (make-Address "Ali Ak" "02121111111" "ali@gmail.com")
       (make-Address "Veli Gök" "02122222222" "veli@gmail.com")))


    (Address-email (first myAddressBook))
    (Address-email (first (rest myAddressBook)))

Case study: Polygon

Case study: polygon

Now consider the problem of representing a polygon as a list of line segments. Each line segment has a length and an angle. We simply ignore whether these line segments, when appended, form a closed polygon or not.

We can represent a line segment as a structure:

    (define-struct LineSegment (length angle))

As a result a polygon becomes a list of line segments, e.g. a square (note that pi is a constant defined in Racket):

    (list (make-LineSegment 50 (/ pi 2))
          (make-LineSegment 50 0)
          (make-LineSegment 50 (/ pi -2))
          (make-LineSegment 50 pi)) 

Case study: drawing polygon

Now we can consider the problem of drawing this polygon at a given position, but it will be useful to define a position in the coordinate system as a new structure:

    (define-struct Point (x y))

We will also need a helper function to add a line segment to a point, to find the endpoint:

    (define (addLineToPoint point lineSegment)
      (make-Point
       (+ (Point-x point) (* (LineSegment-length lineSegment) (cos (LineSegment-angle lineSegment))))
       (+ (Point-y point) (* (LineSegment-length lineSegment) (sin (LineSegment-angle lineSegment))))))

Note how the return value of the function is a Point instance.

Following program uses these definitions, and the add-line function in Racket drawing library to accomplish the task of drawing a polygon:

    (define-struct Point (x y))
    (define-struct LineSegment (length angle))

    (define (addLineToPoint point lineSegment)
      (make-Point
       (+ (Point-x point) (* (LineSegment-length lineSegment) (cos (LineSegment-angle lineSegment))))
       (+ (Point-y point) (* (LineSegment-length lineSegment) (sin (LineSegment-angle lineSegment))))))

    (define (drawPolygon polygon shape startPoint)
      (cond
        ((empty? polygon) shape) 
         (else (add-line (drawPolygon (rest polygon) shape 
                                     (addLineToPoint startPoint (first polygon)))
                        (Point-x startPoint) (Point-y startPoint)
                        (Point-x (addLineToPoint startPoint (first polygon))) (Point-y (addLineToPoint startPoint (first polygon)))
                        "black"))))
    (drawPolygon (list (make-LineSegment 50 (/ pi 2))
                       (make-LineSegment 50 0)
                       (make-LineSegment 50 (/ pi -2))
                       (make-LineSegment 50 pi)) 
                 (empty-scene 400 400) (make-Point 200 200))

Animations revisited

We will now attempt to apply these ideas to animations.

Remember how we have created simple animations

    (define animationSizeX 400)
    (define animationSizeY 400)
    (define ballRadius 20)

    (define (animation1 frameNo)
       (place-image 
        (circle ballRadius "solid" "green")
        50 frameNo  ;note how the y-coordinate is related to frameNo
        (empty-scene animationSizeX animationSizeY)))
    (animate animation1)

A different mechanism for designing animations: using functions as values!

Racket provides a different mechanism to design animation, and have more control over how they work. An animation is constructed using big-bang function.

big-bang function takes at least three parameters: first is the initial state of the world (which is something we design), second and third are calls to on-draw and `ın-tick| functions. In these calls we provide some functions which we have defined, first for drawing given state of the world, and second for changing the state of the world at every time tick given the previous state of the world. Please take note that we provide functions as parameters to another function! Thus for Racket, a function is a valid parameter value just like a number.

The following example uses simply an integer (an integer representing the Y-coordinate of the ball as in our previous example) as the state of the world:

    (define animationSizeX 400)
    (define animationSizeY 400)
    (define ballRadius 20)

    ;changes the state of the world in each tick of clock
    ;in this particular design, the state of the world is simply an integer
    (define (changeWorld worldState)
          (+ worldState 1))

    ;actually draws the current frame of animation
    ;by placing the ball somewhere
    (define (drawFrame worldState)
         (place-image 
              (circle ballRadius "solid" "green")
              50 worldState
              (empty-scene animationSizeX animationSizeY)))

    (big-bang 1 ;;note that '1' is the initial state of the world
                  (on-draw drawFrame)
                  (on-tick changeWorld))

Interacting with the user

An advantage of using big-bang mechanism is ability to provide additional parameters to this function, for example to indicate what needs to be done when user click the mouse. All functions we design to handle such user interface events consume the state of the world as their parameter, and produce a new state of the world. The function to handle mouse clicks also consume the x and y position where mouse is clicked on, and type of event(single-click, double-click, left/right click et.) Our example here disregards some of these inputs:

    (define animationSizeX 400)
    (define animationSizeY 400)
    (define ballRadius 20)

    ;changes the state of the world in each tick of clock
    ;in this particular design, the state of the world is simply an integer
    (define (changeWorld worldState)
          (+ worldState 1))

    ;actually draws the current frame of animation
    ;by placing the ball somewhere
    (define (drawFrame worldState)
         (place-image 
              (circle ballRadius "solid" "green")
              50 worldState
              (empty-scene animationSizeX animationSizeY)))

    ;A simple function to react to mouse clicks,
    ;by resetting ball position
    (define (handleMouseClick worldState x y event)
       (cond
            ((string=? event "button-down") 1);reset worldState to '1'
            (else worldState)))  ;do nothing

    (big-bang 1
                  (on-draw drawFrame)
                  (on-tick changeWorld)
                  (on-mouse handleMouseClick))

Case study: Using a composite state of the world in animations

Now that we have lists and structures to store a set of values, we can actually design a more complex state of the world. In this example we will create an animation of a ball falling through the screen. We also want to reset ball position when mouse is clicked, and start falling from mouse position.

In this problem we need to represent ball position as x and y coordinates. Therefore the state of the world is a list of two numbers instead of a single number, and its velocity as a vector in two dimensional coordinate space. i.e. (list posX posY). In addition we will use a more capable tick function which bounces the ball from the walls:

    (define-struct Point (x y))
    (define animationSizeX 400)
    (define animationSizeY 400)
    (define ballRadius 20)

    ;changes the state of the world in each tick of clock
    ;in this particular design, the state of the world is simply an integer
    (define (changeWorld worldState)
          (make-Point (Point-x worldState) (+ (Point-y worldState) 1)))

    ;actually draws the current frame of animation
    ;by placing the ball somewhere
    (define (drawFrame worldState)
         (place-image 
              (circle ballRadius "solid" "green")
              (Point-x worldState) (Point-y worldState)
              (empty-scene animationSizeX animationSizeY)))

    ;A simple function to react to mouse clicks,
    ;by resetting ball position
    (define (handleMouseClick worldState x y event)
       (cond
            ((string=? event "button-down") (make-Point x y));reset worldState to '1'
            (else worldState)))  ;do nothing

    (big-bang (make-Point 100 10)
                  (on-draw drawFrame)
                  (on-tick changeWorld)
                  (on-mouse handleMouseClick))

Case study: bouncing ball

Here we want to take our animation further. This time the ball can mode in any direction, not just vertical, and also it must bounce from the walls.

Bouncing from the balls require one to check whether the ball position is off at either sides of both x and y directions.

Here we first need to represent position and velocity of the ball as structures. We will also need some helper functions to compute over vectors and positions, as in the polygon example:

    (define-struct Point (x y))
    (define-struct Velocity (x y))
    (define-struct Ball (raidus point velocity)) 
    ;add velocity to point
    (define (addVelocityToPosition position velocity)
      (make-Position (+ (Point-x point) (Velocity-x velocity)) (+ (Point-y point) (Velocity-y velocity))))
    ;negate X component of velocity
    (define (negateX velocity)
      (make-Velocity (- (Velocity-x velocity)) (Velocity-y velocity)))
    ;negate Y component of velocity
    (define (negateY velocity)
      (make-Velocity (Velocity-x velocity) (- (Velocity-y velocity))))
    ;a helper function to decide if number x is between y and z
    (define (between? x y z)
      (and (<= x z) (>= x y)))

The full program will need a few simple helper functions:

    (define animationSizeX 400)
    (define animationSizeY 400)

    (define-struct Point (x y))
    (define-struct Velocity (x y))
    (define-struct Ball (radius point velocity)) 
    ;add velocity to point
    (define (addVelocityToPosition position velocity)
      (make-Point (+ (Point-x position) (Velocity-x velocity)) (+ (Point-y position) (Velocity-y velocity))))
    ;negate X component of velocity
    (define (negateX velocity)
      (make-Velocity (- (Velocity-x velocity)) (Velocity-y velocity)))
    ;negate Y component of velocity
    (define (negateY velocity)
      (make-Velocity (Velocity-x velocity) (- (Velocity-y velocity))))
    ;a helper function to decide if number x is between y and z
    (define (between? x y z)
      (and (<= x z) (>= x y)))
    (define initialState (make-Ball 20 (make-Point 1 1) (make-Velocity 15 25)))
    (define (changeWorld worldState)
          (cond 
            ((not (between? (Point-x (Ball-point worldState)) 0 animationSizeX)) 
             (make-Ball 
              (Ball-radius worldState)
              (addVelocityToPosition (Ball-point worldState) (negateX (Ball-velocity worldState)))
              (negateX (Ball-velocity worldState))))
            ((not (between? (Point-y (Ball-point worldState)) 0 animationSizeY)) 
             (make-Ball 
              (Ball-radius worldState)
              (addVelocityToPosition (Ball-point worldState) (negateY (Ball-velocity worldState)))
              (negateY (Ball-velocity worldState))))
            (else
             (make-Ball 
              (Ball-radius worldState)
              (addVelocityToPosition (Ball-point worldState) (Ball-velocity worldState))
              (Ball-velocity worldState)))))


    ;actually draws the current frame of animation
    ;by placing the ball somewhere
    (define (drawFrame worldState)
         (place-image 
              (circle (Ball-radius worldState) "solid" "green")
              (Point-x (Ball-point worldState)) (Point-y (Ball-point worldState))
              (empty-scene animationSizeX animationSizeY)))

    ;A simple function to react to mouse clicks,
    ;by resetting ball position
    (define (handleMouseClick worldState x y event)
       (cond
            ((string=? event "button-down") initialState);reset worldState
            (else worldState)))  ;do nothing

    (big-bang initialState
                  (on-draw drawFrame)
                  (on-tick changeWorld)
                  (on-mouse handleMouseClick))