Functional Python

Functional Python

Due September 23rd by midnight

Objectives

Practice functional programming with Python. Write concise and efficient algorithms in Python and package them together as a function library.

Description

Your job is to code up a library of handy mathematical functions in a module called mathtools. The specifications for all the functions have already been entered in the file mathtools.py in which your code should replace the pass statement in each function body. The first line of each function is a documentation string used by Python's help function. At the interactive prompt try import mathtools and then help(mathtools). One function, a decorator function called accept_sequence, does not and should not have its own documentation string for reasons that will become apparent if you do the extra credit part of this assignment. At the end of the file is a place for your testing code. This code will only execute if mathtools is run as the main program, not when it is imported. Testing your functions thoroughly before you submit them is extremely important and the quality of your test code will affect your score.


If you are not already familiar with the Factorial function, Fibonaci numbers, and Pascal's triangle, you should look at these links for the specifications.


Other Requirements

  • Included in the documentation strings are the required time and space complexity of each function.
  • Single line functions (functions whose name ends with '1'):
    • Write and test the multiline version first, and only then think about how to shorten it to one line of code which must:
      • Be less than 80 characters wide
      • Not include semi-colons
      • Not call any additional functions you have written (but may call built-ins) unless stated otherwise
    • lambda, reduce, zip, and list comprehensions may all be useful
  • getCombinationsFunc:
    • Must not perform any multiplications
    • Must return a function that does not perform any multiplications
    • Will find Pascal's triangle very helpful
  • EXTRA CREDIT
    • permuteSet and permuteSetR:
      • There are n! permutations of a set of size n. 10! = 3628800, so the permutations of a set with as few as 10 elements can use a significant amount of memory if computed with permuteSetR
      • Writing permuteSet as an iterative generator function avoids this problem but requires a tricky implementation of depth first search. My implementation is 16 lines long and by far the longest function in mathtools
    • Decorating the powerSet functions:
      • These functions accept a variable number of arguments *args.
      • The purpose of decorating them is for when they are passed just one argument which happens to be an iterable sequence. The decorator should unpack the sequence so it will be treated as if it were an argument tuple with each element of the sequence becoming a separate argument passed on to the decorated function.
      • The is_iterable function is helpful when writing the accept_sequence decorator.
      • (This is a lot easier than writing permuteSet or permuteSetR)

  • Below is an example trace of how the functions in mathtools.py should work when used in an interactive Python session.


    
    >>> from mathtools import *
    >>> fact(0)
    1
    >>> fact(5)
    120
    >>> fact(10)
    3628800
    >>> fact(100)
    93326215443944152681699238856266700490715968264381621
    46859296389521759999322991560894146397615651828625369
    7920827223758251185210916864000000000000000000000000L
    >>> factR(0)
    1
    >>> factR(100)
    93326215443944152681699238856266700490715968264381621
    46859296389521759999322991560894146397615651828625369
    7920827223758251185210916864000000000000000000000000L
    >>> fact2(0)
    1
    >>> fact2(100)
    93326215443944152681699238856266700490715968264381621
    46859296389521759999322991560894146397615651828625369
    7920827223758251185210916864000000000000000000000000L
    >>> fact1(0)
    1
    >>> fact1(100)
    93326215443944152681699238856266700490715968264381621
    46859296389521759999322991560894146397615651828625369
    7920827223758251185210916864000000000000000000000000L
    >>> fib(5)
    5
    >>> fib(0)
    0
    >>> fib(20)
    6765
    >>> fib(100)
    354224848179261915075L
    >>> fibR(20)
    6765
    >>> fibR(30)
    832040
    >>> fib(30)
    832040
    >>> for i in fibs(10): print i
    ...
    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    55
    >>> [i for i in fibs(20)]
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 
    610, 987, 1597, 2584, 4181, 6765]
    >>> rPascal([1])
    [1, 1]
    >>> rPascal1([1,1])
    [1, 2, 1]
    >>> rPascal1([1,2,1])
    [1, 3, 3, 1]
    >>> rPascal([1,3,3,1])
    [1, 4, 6, 4, 1]
    >>> tPascal(10)
    [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], 
    [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 
    21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], 
    [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 
    210, 252, 210, 120, 45, 10, 1]]
    >>> tPascal1(10)
    [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], 
    [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1], [1, 7, 
    21, 35, 35, 21, 7, 1], [1, 8, 28, 56, 70, 56, 28, 8, 1], 
    [1, 9, 36, 84, 126, 126, 84, 36, 9, 1], [1, 10, 45, 120, 
    210, 252, 210, 120, 45, 10, 1]]
    >>> c = getCombinationsFunc(100)
    >>> c(0,0)
    1
    >>> c(1,0)
    1
    >>> c(1,1)
    1
    >>> c(5,3)
    10
    >>> c(12,5)
    792
    >>> c(60,23)
    23385332420868600L
    >>> c(100,50)
    100891344545564193334812497256L
    >>> permutations(7,5)
    2520
    >>> permutations(7,1)
    7
    >>> powerList(1,2,3)
    [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]
    >>> powerList1(1,2,3)
    [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]
    >>> powerList1(1.2, 'hello', False)
    [(), (1.2,), ('hello',), (1.2, 'hello'), (False,), 
    (1.2, False), ('hello', False), (1.2, 'hello', False)]
    >>> powerList(1,2,3,4)
    [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3), 
    (4,), (1, 4), (2, 4), (1, 2, 4), (3, 4), (1, 3, 4), (2, 3, 4), 
    (1, 2, 3, 4)]
    >>>
    >>>
    >>> # AND NOW FOR EXTRA CREDIT
    ...
    >>> permuteSetR([1,2,3])
    [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
    >>> [x for x in permuteSet([1,2,3])]
    [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
    >>> permuteSetR([1,2,3,4])
    [(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), 
    (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), 
    (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), 
    (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), 
    (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), 
    (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]
    >>> for t in permuteSet([1,2,3,4]):
    ...     print t
    ...
    (1, 2, 3, 4)
    (1, 2, 4, 3)
    (1, 3, 2, 4)
    (1, 3, 4, 2)
    (1, 4, 2, 3)
    (1, 4, 3, 2)
    (2, 1, 3, 4)
    (2, 1, 4, 3)
    (2, 3, 1, 4)
    (2, 3, 4, 1)
    (2, 4, 1, 3)
    (2, 4, 3, 1)
    (3, 1, 2, 4)
    (3, 1, 4, 2)
    (3, 2, 1, 4)
    (3, 2, 4, 1)
    (3, 4, 1, 2)
    (3, 4, 2, 1)
    (4, 1, 2, 3)
    (4, 1, 3, 2)
    (4, 2, 1, 3)
    (4, 2, 3, 1)
    (4, 3, 1, 2)
    (4, 3, 2, 1)
    >>> powerList('abcd')
    [(), ('a',), ('b',), ('a', 'b'), ('c',), ('a', 'c'), 
    ('b', 'c'), ('a', 'b', 'c'), ('d',), ('a', 'd'), ('b', 'd'), 
    ('a', 'b', 'd'), ('c', 'd'), ('a', 'c', 'd'), ('b', 'c', 'd'), 
    ('a', 'b', 'c', 'd')]
    >>> powerList([1,2,3,4])
    [(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3), 
    (4,), (1, 4), (2, 4), (1, 2, 4), (3, 4), (1, 3, 4), (2, 3, 4), 
    (1, 2, 3, 4)]
    >>> powerList1(xrange(5))
    [(), (0,), (1,), (0, 1), (2,), (0, 2), (1, 2), (0, 1, 2), (3,), 
    (0, 3), (1, 3), (0, 1, 3), (2, 3), (0, 2, 3), (1, 2, 3), (0, 1, 
    2, 3), (4,), (0, 4), (1, 4), (0, 1, 4), (2, 4), (0, 2, 4), (1, 
    2, 4), (0, 1, 2, 4), (3, 4), (0, 3, 4), (1, 3, 4), (0, 1, 3, 4), 
    (2, 3, 4), (0, 2, 3, 4), (1, 2, 3, 4), (0, 1, 2, 3, 4)]
    >>>
    
    

    Put your program in a file called mathtools.py. Advice: Keep an eye on the class discussion board for helpful hints on how to do this assignment!

Grading Criteria

Your functions will be graded on correctness, efficiency, and brevity of code. You should also attempt to make your code easy to read.

Submission Checklist

  • mathtools.py