#functions that take other functions as args, lambda terms.
f = lambda x: x*x
print f(5)

def thereexist(P, A):
    answer = False
    i = 0
    while i<len(A) and answer==False:
        if P(A[i]): answer = True
        i += 1
    return answer
# thereexists

# filter elements of A that satisfy P (non-destructive)
def filterout(P,A):
    B =[]
    i = 0
    while i<len(A):
        if P(A[i]): B.append(A[i])
        i +=1
    return B
# filterout

def f1(x):
    return x>10
print filterout(f1, [3,6,14,56,2,11])

# same as above:
print filterout(lambda x:x>10, [3,6,14,56,2,11])



# Recursive functions in Python:

#### Recursion as a simple "goto" type of operation:

def loop():
    x = input("enter a number, 0 to quit: ")
    if (x!=0):
        print "the square root is",(x**0.2)
        loop()  # go back and do it again
# Goto as tail-recursive function call.
loop()

# similar example: print the numbers from 10 to 1 backwards:
def g(n):
    print n
    if (n>1): g(n-1)
# myloop
g(10) # starts loop

#### CAVEAT: the max recursion depth is usually as low as 1000
#### Other languages (C) implement tail-recursion optimization.


# More interesting recursion, here recursion allow us to define a program
# *inductively* - i.e. define the solution to a large problem by reducing
# the size of the problem.

def factorial(n):
    if (n<2) : return 1
    else: return n*factorial(n-1)
# factorial

def fib(n,a,b):
    if (n<2): return b
    else: return fib(n-1,b,a+b)
# tail-recursive fibonacci

## another recursive version of fib:
def fib2(n):
    if (n<2): return 1
    else: return fib2(n-2) + fib2(n-1)
# fib2

## fib2 is horibly inefficient running on most current machines, yet
# it is mathematically elegant.  The inefficiency comes from redundant
# computation.  Recursion is a very powerful programming tool, but it needs
# to be used very carefully.

## Don't make simplistic generalizations of recursion like "two recursive
#  calls are always inefficient".  Yes, fib2 has two recursive calls, but
#  the quicksort program, which is VERY efficient, also make two recursive
#  calls.  There is no simple generalization that can describe how to use
#  (or not to use) recursion. 


# Recursive function to compute the gcd of two numbers:
def gcd(a,b):
    if a==0: return b
    else: return gcd(b%a,a)
# recursive gcd

## function to determine number of times an element x occurs in list A:


# A[1:len(A)] is A without the first element. In general, A[start:end] is
# the subarray from A[start] to A[end-1]

def occurs(x,A):
    if A==[]: return 0
    n = occurs(x, A[1:len(A)])
    if x==A[0]: return 1+n
    else: return n
# occurs

def forall(P,A):
    if A==[]: return True
    return ( P(A[0]) and forall(P,A[1:len(A)]) )
#forall

def exists(P,A):
    if A==[]: return False
    return ( P(A[0]) or exists(P,A[1:len(A)]) )
#exists

print forall(lambda x: x%2==0, [4,8,2,10,12,6])
print exists(lambda x: x<0, [4,5,8,10,11])


# non-recursive version of binary search
def bsearch1(x,A):
    min = 0
    max = len(A)-1
    answer = -1  # there exists problem, -1 means doesn't exist
    while min<=max and answer==-1:
        i = (min+max)/2
        if A[i]==x: answer = i
        if x<A[i]: max = i-1
        if x>A[i]: min = i+1
    # while
    return answer
#bsearch1 - end of non-recursive version


# recursive version of binary search : returns index of found element

def bsearch(x,A):

    def search(min,max):  # note this function has access to variables x, A
        if (min>max): return -1  # -1 means doesn't exist
        i = (min+max)/2
        if x == A[i]: return i
        if x < A[i] : return search(min,i-1)
        if x > A[i] : return search(i+1,max)
    # inner search function

    return search(0,len(A)-1)
#bsearch

print bsearch1(14,[2,4,6,8,9,10,15,16,27,29])
print bsearch(4,[2,4,6,8,9,10,15,16,27,29])