Lab 10 - Functional Programming

Due by 11:59pm on 2023-10-10.

In this lab, you're to look at some functional programming concepts using the Grid class you've been developing and random numbers.

Starter Files

Download lab10.zip. Inside the archive, you will find starter files for the questions in this lab.

Topics

Random numbers

Remember from lecture, we can use random numbers in our program by importing from the random library.
Some of the useful functions from this library include:

  • seed(n) – sets the initial seed value. If no argument given or n=None, uses the system time
  • randrange(stop) – generate a random number from 0 to stop-1
  • randrange(start,stop) – generate a random number from start to stop-1
  • randint(a,b) – generate a random number from a to b (inclusive)
  • random() – generate a floating-point number between 0.0 and 1.0
  • uniform(a, b) – generate a floating-point number between a and b
  • choice(seq) – randomly select an item from the sequence seq

Functional Programming

This lab is about functional programming and one of the ideas in that programming paradigm is to try to make our functions as "pure" as possible. And that means that the function should have no side effects or in other words, not change any of the object passed to it.

When we pass an object into a function, Python will pass in the literal object, not a copy of it, into the function. This allows the programmer to make changes to the object. For example, consider the function apply() that takes in a list lst and a function fn and applies fn to each element, mutating lst. Because this function changes the list, which is an object, it does not follow the functional programming paradigm.

def apply(lst, fn):
    """Applies `fn` to each element in `lst` and mutates `lst`
    >>> l = [1, 2, 3, 4, 5]
    >>> square = lambda x: x*x
    >>> apply(l, square)
    >>> l
    [1, 4, 9, 16, 25]
    """
    for i in range(len(lst)):
        lst[i] = fn(lst[i])

In this case, if we wanted to follow the functional programming paradigm, we would have to create a new list where fn was applied onto each of the elements. Doing so will allow us to get the list we want, but without mutating the list passed in. As such, there will be no side effects. Here are two ways of doing it:

def apply(lst, fn):
    """Applies `fn` to each element in `lst` and mutates `lst`
    >>> l = [1, 2, 3, 4, 5]
    >>> square = lambda x: x*x
    >>> modified_l = apply(l, square)
    >>> l
    [1, 2, 3, 4, 5]
    >>> modified_l
    [1, 4, 9, 16, 25]
    """
    modified_lst = []
    for i in range(len(lst)):
        modified_lst.append(fn(lst[i]))

    return modified_lst
def apply(lst, fn):
    """Applies `fn` to each element in `lst` and mutates `lst`
    >>> l = [1, 2, 3, 4, 5]
    >>> square = lambda x: x*x
    >>> modified_l = apply(l, square)
    >>> l
    [1, 2, 3, 4, 5]
    >>> modified_l
    [1, 4, 9, 16, 25]
    """
    modified_lst = lst.copy()
     # copies the list - modified_lst has the same contents as lst but is its own list

    for i in range(len(lst)):
        modified_lst[i] = fn(lst[i])

    return modified_lst

Copying and returning the modified object is what we will use in this lab to follow the functional programming paradigm.

Required Questions

Q1: Printing the Grid

In your lab10.py file, there is a print_grid() function that takes as input a Grid object and prints it out row by row. Take a look at this function and discuss the following with your lab group:

  1. There is a conditional statement in the print() statement in the innermost for loop.
grid.get(x,y) if grid.get(x,y) is not None else 0

Do you understand what it is doing?

  1. Is this function a pure or non-pure function? Why?

If you need, recall that grid.get(x,y) if grid.get(x,y) is not None else 0 is the equivalent to

if grid.get(x,y) is not None:
    grid.get(x,y)
else:
    0

Q2: Random Rocks and Bubbles

Write a function random_rocks which takes a Grid object and chance_of_rock where chance_of_rock is floating point number between 0 and 1 that represents the probability that a rock should be placed in any given location. The function will return a new Grid object with rocks placed in it.

def random_rocks(grid, chance_of_rock):
    '''Take a grid, loop over it and add rocks randomly 
    then return the new grid. If there is something already
    in a grid position, don't add anything in that position.'''
    "*** YOUR CODE HERE ***"

By default when we pass in our Grid object, any set() operation we perform on it will change the original Grid that we pass in. So if we want this to be a pure function, we need to start by making a complete copy of the Grid. Use the copy() method you implemented in Homework 3.

Start by making a copy of the input grid. Then loop over each slot in the grid copy. If there is nothing in a slot, randomly choose to add a rock, represented by the string 'r'. Since chance_of_rock will be a number between 0 and 1, generate a random number between 0 and 1 and add a rock if that number is less than or equal to chance_of_rock.

Note: You shouldn't call random.seed anywhere in your code, as the autograder will be calling it so that your modified grid matches the key. Additionally, to this end, you should iterate over the input grid row by row from top to bottom, left to right.

Once you're done, return the updated copy of the grid. You should test that you're not changing the original grid in your function.
Create a small grid, call your random_rocks() function and assign the return value to a new name, then call print_grid() to print the original and new grid. Are they the same? You might want to pass in a fairly large value for chance_of_rock to make sure some rocks are created.

Similarly write a function random_bubbles which takes a Grid. Loop over grid and if there is nothing there, randomly choose to add a bubble 'b' based on the chance_of_bubbles parameter.

def random_bubbles(grid, chance_of_bubbles):
    '''Take a grid, loop over it and add bubbles 'b' randomly 
    then return the new grid. If there is something already
    in a grid position, don't add anything in that position.'''
    "*** YOUR CODE HERE ***"

Take a minute and think about the two functions you just wrote. Discuss the following with your lab group and TA:

  • Are these pure functions?
    • Do they return a value of some sort?
    • Do they have side effects?
    • Are they affected by external state beyond the parameters passed in?
  • If they are not pure functions, can you think of any way to make them so?
  • Is there any penalty for writing these as pure functions? If so, what is it?

Q3: General grid modifications

Since these functions act almost the same, we can create a higher-order function that generalizes the behavior. Finish the modify_grid which can take in a Grid object grid, a function func, and a probability prob. func will and should be a function that takes in two variables representing the (x, y) coordinates in the grid to update.

It should loop through the grid like the previous functions. If the same conditions are true, call func to modify the grid then return it.

def modify_grid(grid, func, prob):
    """Write a function which can take in a grid, a function
    and a probablily as parameters and updates the grid using
    the function passed in."""
    "*** YOUR CODE HERE ***"

Notes:

  • Do not create a copy of the grid.
  • modify_grid() may not be a pure function. This is because variables in the expression part of lambda functions are bound in the frame where the lambda is defined. Thus, if I call modify_grid() from random_rocks() and the lambda function I pass in operates on a variable named grid it will look up the name grid in random_rocks()—not modify_grid()—even though the function is being executed in modify_grid().

Now modify random_bubbles() and random_rocks() so they both call modify_grid(). You will pass in the copy created in random_bubbles() and random_rocks(), a lambda function, and the probability passed in. Recall, for the lambda function it should be a function that takes in two variables representing the (x, y) coordinates in the grid to update. When you call this lambda function, it should set the item in the grid copy at the (x, y) coordinates to either a bubble or a rock.

Q4: Bubble Up

Write a function bubble_up which takes in a grid, x and y coordinate. The x and y coordinate should give you a bubble and moves the bubble one row up, replacing its former position with None. Then it returns the modified grid. (Remember to use the copy() function)

Note: You can assume the given x, y coordinate contains a bubble. Also, make sure you're not modifying the original grid.

def bubble_up(grid,x,y):
    """
    Write a function that takes a bubble that is known 
    to be able to bubble up and moves it up one row.
    """
    "*** YOUR CODE HERE ***"

Q5: Move Bubbles

Write a function move_bubbles that finds all the bubbles in a Grid object and checks if each bubble can move up. If it can, the function moves it up. After checking all the bubbles, the function returns the grid. Bubbles can only move up if the space above them is empty. Also, they cannot move out of the grid. (Remember to use the copy() function)

def move_bubbles(grid):
    """
    Write a function that loops over the grid, finds
    bubbles, checks if the bubble can move upward, moves
    the bubble up.
    """

Before you start implementing this, think about the code you've already written. Can you leverage any of those methods to simplify your work in this one?

Once this is done, you can call the animate_grid() function provided in lab10.py to see an animation of the bubbles floating up in your grid. You need to run this in the terminal to get the best effect.

Submit

If you are not in lab today, submit your lab10.py file along with your Grid.py file to Gradescope to receive credit. Submissions will be in Canvas.

Otherwise, thanks for coming to lab! You don't have to submit anything.

© 2023 Brigham Young University, All Rights Reserved