Chp 9 Functions

The Unit Test

The unit test is found both at CodeHS and at GitHub.

A Challenge

Before I begin with the functions, let me issue you a challenge. This isn't mandatory, but I know you're up to it.

What's the challenge? Write each of the functions for the chapter in a single line of code.

That means of course that all your functions will be written by means of the lambda operator. So for instance, if I asked for a square root function, you'd do this (or something like it):

sq_rt = lambda x: x**(1/2)

Let me add a bit of challenge to the challenge: do not make use of any helper functions. So all your one-line functions should be self-contained; that is, if any of your one-line functions were to be copied and pasted into another program, they'd work just fine.

To complete this challenge, you'll need to make use of both list comprehensions and Python's ternary operator. I'll give a few examples of each. Do a Google search if you want to know more.

>>> [n for n in [2, 3, 5, 7, 8] if n % 2 == 0]

[2, 8]

>>> [char for char in 'spam and eggs' if char in 'aeiou']

['a', 'a', 'e']

>>> f = lambda x: 2*x if x % 2 == 0 else 3*x 

>>> f(2)

4

>>> f(3) 

9

>>> g = lambda n: [a**2 for a in range(1, n+1)]

>>> g(12)

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144]

The first two input lines are list comprehensions. f is constructed by means of the ternary operator. g is constructed by means of the ternary operator and a list comprehension.

Greater Value

Assume that f and g are two functions that take a number and return a number; assume too that f and g are defined for any input we send them.

Write a function named greater_value that takes the functions f and g and some number x and returns the greater of f(x) and g(x). If f and g return the same value for some input x, of course return that value.

Add these three functions to your function set.

def a_quadratic(x): 

    return 3*(x**2) - 2*x + 1

def a_cubic(x):

    return x**3 - 2*(x**2) + 5*x - 3

def rat_power(x):

    return x**(5/2)

Test cases:

>>> greater_value(a_quadratic, a_cubic, 0)

1

>>> greater_value(a_quadratic, a_cubic, 12)

1497

>>> greater_value(a_quadratic, rat_power, 3)

22

>>> greater_value(a_quadratic, rat_power, 15)

871.4212528966688

Greater Function

Once again assume that f and g are two functions that take a number and return a number, and assume that both f and g are defined for any number we send them.

Now write me a function named greater_func that takes a pair of functions f and g and returns a function h that, for any number x, returns the greater of f(x) and g(x).

Note that, unlike greater_value, greater_func returns a function. This means that its output is callable.

Test cases:

>>> h = greater_func(a_quadratic, a_cubic)

>>> h(0)

1

>>> h(12)

1497

>>> h = greater_func(a_quadratic, rat_power)

>>> h(3)

22

>>> h(15)

871.4212528966688

Map

The map function takes a function f and a list S and returns a new list T that results from the successive application of f to each member of S. In particular, if i is the index of a member of S, then T also has a member at that index and T[i] = f(S[i]).

Write me such a function. Call it map. It should take a function and a list and return a list. Also add the functions below to your function set.

def square(x):

    return x**2

def mod_2(x):

    return x % 2

Test cases:

>>> map(square, [1, 2, 3, 4])

[1, 4, 9, 16]

>>> map(square, [])

[]

>>> map(mod_2, range(1, 11))

[1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

Filter

The filter function takes a Boolean-valued function f and a list S and returns a list T of elements of S for which f returns True. In particular, t is a member of T if and only if t is a member of S and f(t) returns True. Note that order is preserved.

Write me such a function. Call it filter. Also add the functions below to your function list.

import math

def is_thodd(n):

    if n % 3 == 1:

        return True

    else:

        return False

def is_prime(n):

    if n < 2:

        return False

    for f in range(2, int(math.sqrt(n)) + 1):

        if n % f == 0:

            return False

    return True

Test cases:

>>> A = [2, 3, 4, 5, 6, 7, 8, 9]

>>> filter(is_thodd, A)

[4, 7]

>>> filter(is_prime, A)

[2, 3, 5, 7]

>>> filter(is_prime, [])

[]

Fold Left

The foldLeft function takes an initial value i, a two-parameter function f and a list S. foldLeft then calls f on i and the first member of S; and the result then becomes the new value of i. This continues (that is, we call f on i and the next member of S and makes this the new i) until the whole lists has been traversed. The return value will be the final value of i.

We call it foldLeft because we, as it were, fold up the list from left to right.

Let's have an example. Let i be 0, f the addition function and S the list [1, 2, 3, 4].

1. Apply f to i and the first element of S . 1 results.

2. Now apply f to that 1 and the next element of the list. 1 + 2 = 3 results.

3. Now apply f to that 3 and the next element of the list. 3 + 3 = 6 results.

4. Finally apply f to that 6 and the final element of the list. 6 + 4 = 10 is the final result.

Write me such a function. Also add the functions below to your function list. (Modification: the first of the two functions below is no longer defined by use of the lambda operator.)

def sum_two(x, y):

    return x + y

def longer(s, t):

    # Parameters: strings s and t

    # If unequal in length, return the longer.

    # If equal in length, return the first.

    if len(s) >= len(t):

        return s

    else:

        return t

Test cases:

>>> foldLeft(0, sum_two, [1, 2, 3, 4, 5])

15

>>> foldLeft('', longer, ['aa', 'bb', 'cccc', 'd'])

cccc

The second one is pretty cool, isn't it? To get the longest string in a list of strings, we fold with longer.

Factorial

Implement the factorial function as a fold of the product function (which you'll need to write) over the list of the first n positive integers . Call it factorial. Recall that the expression range(1, n + 1) returns a list of the first n positive integers.

Your factorial function can (should really) be a two-liner. If you iterate within it or have it call itself (recursion), you haven't understood.

Test cases:

>>> factorial(5)

120

>>> factorial(1)

1

Repeat

The repeat function takes a function f, an argument x and a positive integer n and returns f(f(f ... (x) ... )), where the number of occurrence of f equals n. For instance, if f is the square root function, x is 2 and n is 3, the repeat function returns the square root of the square root of the square root of 2. Repeat thus repeats the application of f n times, where each new output becomes the input for the next application.

Write me such a function. Call it repeat. It should have three parameters - a function, an initial argument, and the number of times to repeat the application of the function. Also add the function below to your function list. (Modification: the function below is no longer defined by use of the lambda operator.)

def sqrt(x):

    return x**(1/2)

Test cases:

>>> repeat(sqrt, 2, 0)

2

>>> repeat(sqrt, 2, 1)

1.4142135623730951

>>> repeat(sqrt, 2, 2)

1.189207115002721

Harmonic Series

The Harmonic Series is the sum that begins 1/1 + 1/2 + 1/3 + 1/4 + ... . Write a function named harmonic_series takes a positive integer n and finds the value of the Harmonic Series out to 1/n. For instance, if n = 5, the function should return the sum 1/1 + 1/2 + 1/3 + 1/4 + 1/5.

Implement harmonic_series as a fold of a map. You'll likely need a function that I named sum_two. (It does what its names says. It takes two numbers and returns their sum.) You'll also likely need a reciprocal function that takes n and returns 1/n.

Test cases:

>>> harmonic_series(1)

1.0

>>> harmonic_series(2)

1.5

>>> harmonic_series(12)

3.103210678210678

>>> harmonic_series(100)

5.1873775176396215

Find Max, Find Min

Write two functions, one that finds the maximum element of a list and a second that finds the minimum element of a list. Call them find_max and find_min. Implement each as a fold. You'll need two helper functions, one that takes two arguments and returns the larger of the two and another that takes two arguments and returns the smaller of the two.

Flatten

Write a function that takes a list of lists and flattens it into a list. Call it flatten. Write it as a fold. You'll need a helper function that takes two lists and returns their concatenation. (The concatenation of two lists is one list that contains the elements of the two. Thus the concatenation of [1, 2] and [3, 4] is [1, 2, 3, 4]. Lists are concatenated with the + operator.)

Test cases:

>>> flatten([[1, 2], [3, 4]])

[1, 2, 3, 4]

Square of a Sum, Sum of Squares

Go grab the compose function defined in the discussion of higher-order functions and add it to your function set.

Now define two functions called square_lst and sum_lst. The first should take a list of numbers and return a list of the squares of those numbers. Use map in its definition. The second should take a list of numbers and return their sum. Use fold in its definition.

Now use your compose, square_lst and sum_lst functions to create two functions named sq_sum and sum_sq. The first  should take a list of numbers and return the square of their sum. The second should take a list of numbers and return the sum of their squares. (Hint: for these last two functions you will not use the keyword def. You'll use compose instead, which returns a function.)

Test cases:

>>> A = [1, 2, 3]

>>> sum_sq(A)

14

>>> sq_sum(A)

36

(I admit that I have an ulterior motive with this one. Students of mathematics so very often assume that (x + y)²  = x²  + y² . That is, they assume that the square of a sum equals a sum of squares. This is false, and you now have a handy-dandy counterexample generator.) 

Self-Composition

Write a function named self_compose that takes a function and a positive integer n and returns a function that is f composed with itself n times. So if n is 2, self_compose should return f(f(x)), and if n is 3 self_compose should return f(f(f(x))). Etc.

Use compose in its definition. Don't simply recycle your repeat code from above.

Though it is not necessary, foldLeft can certainly be used here. Recall that, if we wish to produce a list n long of some item t, [t] * n will do that.

Test cases:

>>> f = self_compose(sqrt, 3)

>>> f(2)

1.0905077326652577

Build a Quadratic

Write a function named eq_quadratic with parameters a, b and c that returns the quadratic function f(x) = ax²  + bx + c. (Refer to my discussion of the equation of a line in the chapter if you're lost.)

Test cases:

>>> this_quad = eq_quadratic(1, -2, 3)

>>> this_quad(0)

3

>>> this_quad(1)

2

>>> this_quad(-7)

66

>>> this_quad(11)

102

Graph (EC)

• Function name: graph

• Parameters: a function f that takes and returns floats, minimum and maximum x-coordinates xmin and xmax (both positive), step size s (again positive)

• Return value: None

• Function action: draw a graph of f from xmin to xmax where that interval has been divided into s-sized chunks

I suggest you use matplotlib. It's immensely powerful. Below is my graph for graph(lambda x: x**2, -12, 12, 1). Pretty, isn't it?

This function will not be unit tested. Instead, I'll attempt to call it in the console.

How to Curry

I'll need to teach a little before I describe the function I wish you to write.

You know what a function is. Functions take a value or values, use that value or values in some computation, and then when done returns a value.

You know the mathematical notation for  functions. For instance, in f(x) = 2x -3, f is the function, x is the parameter, 2x - 3 is the computation rule, and f(x) is the output of f when a value is given to the parameter x. (The value given to a parameter is often called an "argument" or an "input".) Thus f(5) = 2·5 - 3 = 7. 5 is the argument (or input), the computation rule has us perform 2·5 - 3, and 7 is the output.

Of course some functions take multiple arguments. For instance, the function g(x, y, z) = x + 2y - 3z has three parameters.

Now, here's a curious question. What if we sent the function g above only one number? I'd understand if you said that the result isn't defined; it seems that to get a value out of g, we need to send it three numbers, not one. But Haskell Curry  had a brilliant idea. He said that if we send g less than three numbers, it returns not a number but a function. For instance, if we send it a 2, we get the function h(y, z) = 2 + 2y - 3z. (I kept the variable names from above, since I didn't want to confuse you. But I could have said that if we send g the argument 2, we get h(x, y) = 2 + 2x - 3y. The actual letters used doesn't matter.) In general, if we call a function but send it fewer arguments that it has parameters, we get a function back; in particular, if we send m arguments to a function with n parameters where m < n, we get back a function with n - m parameters.

Let's have a name for this. We curry a function when we send it fewer arguments than it has parameters and get a function back out.

Now of course the question for us is this: Can we curry in Python? Answer: Yep! The function curry_one below takes a function of two parameters and one argument and returns a function of one parameter. (I've included a sum_squares function so we could experiment a little.)

def curry_one(f, a):

   return lambda b: f(a, b)

def sum_squares(a, b):

   return a**2 + b**2

So curry_one takes a function f and an argument a and returns a function that takes an argument b and returns f(a, b). Let's experiment.

>>> h = curry_one(sum_squares, 3)

>>> h(4)

>>> 25

The second line makes clear that h (which was the output of curry_one) is a function; we call it with argument 4. What function is it? Well, we curried sum_squares with 3, and the result was the function h(x) = 9 + x**2. The 3**2 got literally imbedded in the function! It's there whenever we call it!

Now here's what I want you to do. Write me a function named curry_many that takes a function f and some numbers of arguments and curries f with those arguments. So for instance if f(x, y, z) = x + 2y - 3z, then f(2, 5) = h(x) = 12 - 3x. (The 12 of course is the value of 2 + 2·5.)

Do note that I say nothing about how many parameters f has or how many values we send it. It should work for any number of parameters and any number of arguments (as long, of course, as the number of arguments sent is less than or equal to the number of parameters).

Below is a little sample code. I (of course) didn't include my curry_many function. Write your own!

f = lambda w, x, y, z: w**2 - x + 3*y - 2*z

g = curry_many(f, 5, 1)

h = curry_many(g, 3)

i = curry_many(h, 7)

Now let's hop into the console:

>>> g(2, 7)

16

>>> h(11)

11

>>> i()

19

Let me help you make sense of this:

1. g is the function that results when we curry f with 5 and 1. Since f had four parameters, g has two. In particular g(x, y) = 5**2 - 1 + 3*x - 2*y= 24 + 3*x - 2*y. So g(2, 7) = 24 + 3*2 - 2*7 = 24 + 6 - 14 = 16.

2. h is the function that results when we curry g with 3. So h(x) = 24 + 3*3 - 2*x = 33 - 2*x. So h(11) = 33 - 2*11 = 33 - 22 = 11.

3. Finally, i is the function that results when h is curried with 7. But this means that i has no parameters, since h had only one! i is what is often called a "constant" function. It takes no arguments and always returns 19.

This is a hard problem. It took me much time and thought to solve it (though my code is only a few lines long). If you solve it like I did, you'll need a few resources from Python that I haven't mentioned. You'll need to learn how to pack and unpack arguments.

Let's say that we have a function that takes three arguments. Like this one:

def linear_eq(a, b, c):

    return 2*a + 5*b - c

Of course to call it we send three values.

>>> linear_eq(1, 2, 3)

9

But we could also send it one tuple that consists of three numbers is tell Python to unpack that tuple. How? Use the star!

>>> three_nums = (1, 2, 3)

>>> linear_eq(*three_nums)

9

The star before three_nums in the function call split it into three values, sent the first to a, the second to b and the third to c.

If we had omitted the star, three_nums would be sent to a but b and c would not have had values.

>>> linear_eq(three_nums)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

TypeError: linear_eq() missing 2 required positional arguments: 'b' and 'c'

So, that's how we unpack a tuple when we send that tuple to a multi-parameter function. But a function can also pack multiple inputs into a single tuple. To do so, we use the star again but now place it in front of a parameter. Here's an example:

def num_sum(*args):

   s = 0

   for arg in args:

       s += arg

   return s

What does this do? It packs up all the arguments we send to num_sum into a single tuple named "args". (The name "args" isn't mandatory. But it's what everyone uses. Don't buck tradition!) We can then call num_sum we as many arguments as we choose.

>>> num_sum(1, 2, 3)

6

>>> num_sum(1, 2, 3, 4, 5, 6, 7, 8, 9)

45

For the first, args became the tuple (1, 2, 3); and for the second, it became the tuple (1, 2, 3, 4, 5, 6, 7, 8, 9). Neat, huh? This means that we can write functions that can take as many arguments as we like. Just use a star to bundle them all up into a tuple!

Build a Polynomial

Above you wrote a function that took three numbers a, b and c and returned  the quadratic function a*x**2 + b*x + c.

Let's generalize. Write a function that takes a variable number of numbers a, b, c, ... and returns the polynomial function:

a*x**(n-1) + b*x**(n-2) + c*x**(n-3) + ...

where n is the number of numbers sent to the function. So for instance if the function is sent 2, 3, 5 and 7, it will return the polynomial function:

2*x**3 + 3*x**2 + 5*x**1 + 7*x**0.

In my description of the curry function above, I explained how a function can take a variable number of arguments.

Call your function poly_maker.

Test cases:

>>> p = poly_maker(2, 3, 1)

>>> p(0)

1

>>> p(1)

6

>>> p(2)

15

>>> q = poly_maker(2, 3, 1, 4, 7)

>>> q(0)

7

>>> q(1)

17

>>> q(-1)

3

>>> q(2)

75

>>> q(-2)

11

Find Degree

The degree of a polynomial is the highest power of the variable. So for instance the degree of x**2 + 2*x - 3 is 2, and the degree of 7*x**5 - 3*x**3 + 1 is 5.

Write a function named find_degree that takes a polynomial (which of course will be a function) and returns its degree. You may assume that the coefficient of each term will be in the range 1 - 100 and that the polynomial will have degree 100 or less.

>>> f = lambda x: 0

>>> find_degree(f)

0

>>> g = lambda x: 7*x**5 - 3*x**3 + 1

>>> find_degree(g)

5