(Higher-Order) Functions, Sequences, Recursion and TreeRecursion, Trees

( Higher - Order ) Functions

Functions

: a function is made up of a series of statements, and takes in an input and maps it to an output

How we descrive functions :

- domain : the set of possible inputs a function may take in

- range : the set of possible output values a function may return

- behavior : the relationship between input and output

EXAM _ pay close attention to the specified domain and range of a function on the exam. What do the parameters represent ? What should the function return ?

Higher Order Functions

a higher - order function is :

- a function that takes a function as an argument and / or

- a function that returns a function as a return value

Lambda Expressions

f = lambda x: x * x

a lambda expression is an expression that evaluates to a function

In the above example, the RHS is a lambda expression that evaluates to a function; and then we are binding it to f

- lambda functions have no intrinsic dame

- their parent frame is the frame in which they were defined

Functions in Environment Diagrams

- unlike primitive values, functions are written in the objects section

- we also write the parent of the function, the frame in which it was defined

- when a function is passed to another variable, we draw another arrow to the existing function object

Environment Diagram Tips

1. name of frame should be intrinsic name of function

2. parent frame of a function never changes once you write it down

3. don't conflate : function name vs. function call

4. remember evaluation procedure

 a. evaluate the operator ( usually a lookup )

 b. evaluate the operands ( may involve calling another function )

 c. apply the operator on the operands ( this is where you actually call the function and make a new frame )

 

Sequences

The basics

:   Definitions

- Sequence : a collection of values

- List : an ordered sequence of values of any data type

- Index : start from 0

:   Functions

- len ( lst ) : returns number of elements in the list

- range ( start, end ) : function creates a sequence containing the values within a specified range

Box and Pointer Diagram

: lists are drawn using boxes and pointers in environment diagrams

For loop & List comprehension

: suppose that we're given a list and want to make a new one where we double all the even elements of the original

- For loops are a convenient way to iterate through a list

- List comprehensions are a compact way to create a new list

Mutating a list vs. Creating a list

 lst.append ( element )

 lst.extend ( sequence )

 lst.insert ( index, element )

 lst.remove ( element )

 lst.pop ( index )

 lst1 += lst2

 lst1 [0:1] = lst2 [0:5]

 All of above except pop return None

 slicing : lst [start:end:ste]

 shallow copying : lst [:]

 concatenating : lst1 = lst1 + lst2

 list constructor : lst2 = list(lst1)

 

Recursion and Tree Recursion

The basics

- Base case(s) : simplest possible inputs for the problem, may be more than one

- Shrinking the problem : call the function again with slightly smaller inputs

- Using the solved smaller problem : to write a working recursive function, you should assume that you can call it on smaller input and use this to solve the larger problem

Tree Recursion

- Recursive function with (potentially) more than one recursive call : rest is the same

- When you draw out the function calls, it forms a tree shape

- Usually split up into different cases : you take one of several options or explore all the different choices 

Revisiting Count Partition

: suppose we want to find all the sets of integer which sum to 4, where all the integers are positive and less than or equal to 3

two possibilities _ set has 3, it doesn't

- generally, many tree recursion problems have cases of the form "use this first one or don't", or "use one of these"

- why do we consider these two cases ?

 

Trees

The Tree Data Abstraction

-   Constructor

def tree ( label, branches = [] ) : pass in a value ( label ) for the root node, and a list of branches. Each branch must itself also be a tree

-   Selectors

def label ( tree ) : returns a value _ whatever is stored in the root node

def branches ( tree ) : returns a list of tree's subtrees

def is_leaf ( tree ) : returns a boolean _ true if tree has no children, false otherwise

General Structure for Tree Problems

- Base Case : smallest version of the problem _ no additional work needed to get answer ( usually if it's a leaf )

- Recursive call : do the same function on smaller parts of the tree ( usually on the branches )

- Final answer : put together resuls from all the branches

   _ aggregator functions ( max, min, sum, any, all )

   _ creating a new tree w/ updated label and branches