#!/usr/bin/env python
# coding: utf-8

# # 函数进阶：参数传递，高阶函数，lambda 匿名函数，global 变量，递归

# ## 函数是基本类型

# 在 `Python` 中，函数是一种基本类型的对象，这意味着
# 
# - 可以将函数作为参数传给另一个函数
# - 将函数作为字典的值储存
# - 将函数作为另一个函数的返回值

# In[1]:


def square(x):
    """Square of x."""
    return x*x

def cube(x):
    """Cube of x."""
    return x*x*x


# 作为字典的值：

# In[2]:


funcs = {
    'square': square,
    'cube': cube,
}


# 例子：

# In[3]:


x = 2

print square(x)
print cube(x)

for func in sorted(funcs):
    print func, funcs[func](x)


# ## 函数参数

# ### 引用传递

# `Python` 中的函数传递方式是 `call by reference` 即引用传递，例如，对于这样的用法：
# 
#     x = [10, 11, 12]
#     f(x)
# 
# 传递给函数 `f` 的是一个指向 `x` 所包含内容的引用，如果我们修改了这个引用所指向内容的值（例如 `x[0]=999`），那么外面的 `x` 的值也会被改变。不过如果我们在函数中赋给 `x` 一个新的值（例如另一个列表），那么在函数外面的 `x` 的值不会改变：

# In[4]:


def mod_f(x):
    x[0] = 999
    return x

x = [1, 2, 3]

print x
print mod_f(x)
print x


# In[5]:


def no_mod_f(x):
    x = [4, 5, 6]
    return x

x = [1,2,3]

print x
print no_mod_f(x)
print x


# ### 默认参数是可变的！

# 函数可以传递默认参数，默认参数的绑定发生在函数定义的时候，以后每次调用默认参数时都会使用同一个引用。
# 
# 这样的机制会导致这种情况的发生：

# In[6]:


def f(x = []):
    x.append(1)
    return x


# 理论上说，我们希望调用 `f()` 时返回的是 `[1]`， 但事实上：

# In[7]:


print f()
print f()
print f()
print f(x = [9,9,9])
print f()
print f()


# 而我们希望看到的应该是这样：

# In[8]:


def f(x = None):
    if x is None:
        x = []
    x.append(1)
    return x

print f()
print f()
print f()
print f(x = [9,9,9])
print f()
print f()


# ## 高阶函数

# 以函数作为参数，或者返回一个函数的函数是高阶函数，常用的例子有 `map` 和 `filter` 函数：
# 
# `map(f, sq)` 函数将 `f` 作用到 `sq` 的每个元素上去，并返回结果组成的列表，相当于：
# ```python
# [f(s) for s in sq]
# ```

# In[9]:


map(square, range(5))


# `filter(f, sq)` 函数的作用相当于，对于 `sq` 的每个元素 `s`，返回所有 `f(s)` 为 `True` 的 `s` 组成的列表，相当于：
# ```python
# [s for s in sq if f(s)]
# ```

# In[10]:


def is_even(x):
    return x % 2 == 0

filter(is_even, range(5))


# 一起使用：

# In[11]:


map(square, filter(is_even, range(5)))


# `reduce(f, sq)` 函数接受一个二元操作函数 `f(x,y)`，并对于序列 `sq` 每次合并两个元素：

# In[12]:


def my_add(x, y):
    return x + y

reduce(my_add, [1,2,3,4,5])


# 传入加法函数，相当于对序列求和。
# 
# 返回一个函数：

# In[13]:


def make_logger(target):
    def logger(data):
        with open(target, 'a') as f:
            f.write(data + '\n')
    return logger

foo_logger = make_logger('foo.txt')
foo_logger('Hello')
foo_logger('World')


# In[14]:


get_ipython().system('cat foo.txt')


# In[15]:


import os
os.remove('foo.txt')


# ## 匿名函数

# 在使用 `map`， `filter`，`reduce` 等函数的时候，为了方便，对一些简单的函数，我们通常使用匿名函数的方式进行处理，其基本形式是：
# 
#     lambda <variables>: <expression>
# 
# 例如，我们可以将这个：

# In[16]:


print map(square, range(5))


# 用匿名函数替换为：

# In[17]:


print map(lambda x: x * x, range(5))


# 匿名函数虽然写起来比较方便（省去了定义函数的烦恼），但是有时候会比较难于阅读：

# In[18]:


s1 = reduce(lambda x, y: x+y, map(lambda x: x**2, range(1,10)))
print(s1)


# 当然，更简单地，我们可以写成这样：

# In[19]:


s2 = sum(x**2 for x in range(1, 10))
print s2


# # global 变量

# 一般来说，函数中是可以直接使用全局变量的值的：

# In[20]:


x = 15

def print_x():
    print x
    
print_x()


# 但是要在函数中修改全局变量的值，需要加上 `global` 关键字：

# In[21]:


x = 15

def print_newx():
    global x
    x = 18
    print x
    
print_newx()

print x


# 如果不加上这句 `global` 那么全局变量的值不会改变：

# In[22]:


x = 15

def print_newx():
    x = 18
    print x
    
print_newx()

print x


# ## 递归

# 递归是指函数在执行的过程中调用了本身，一般用于分治法，不过在 `Python` 中这样的用法十分地小，所以一般不怎么使用：
# 
# Fibocacci 数列：

# In[23]:


def fib1(n):
    """Fib with recursion."""

    # base case
    if n==0 or n==1:
        return 1
    # recurssive caae
    else:
        return fib1(n-1) + fib1(n-2)

print [fib1(i) for i in range(10)]


# 一个更高效的非递归版本：

# In[24]:


def fib2(n):
    """Fib without recursion."""
    a, b = 0, 1
    for i in range(1, n+1):
        a, b = b, a+b
    return b

print [fib2(i) for i in range(10)]


# 速度比较：

# In[25]:


get_ipython().run_line_magic('timeit', 'fib1(20)')
get_ipython().run_line_magic('timeit', 'fib2(20)')


# 对于第一个递归函数来说，调用 `fib(n+2)` 的时候计算 `fib(n+1), fib(n)`，调用 `fib(n+1)` 的时候也计算了一次 `fib(n)`，这样造成了重复计算。
# 
# 使用缓存机制的递归版本，这里利用了默认参数可变的性质，构造了一个缓存：

# In[26]:


def fib3(n, cache={0: 1, 1: 1}):
    """Fib with recursion and caching."""

    try:
        return cache[n]
    except KeyError:
        cache[n] = fib3(n-1) + fib3(n-2)
        return cache[n]

print [fib3(i) for i in range(10)]

get_ipython().run_line_magic('timeit', 'fib1(20)')
get_ipython().run_line_magic('timeit', 'fib2(20)')
get_ipython().run_line_magic('timeit', 'fib3(20)')