# function
def plus_one(x):
    return x + 1

# higher order function (takes a function f as an argument)
def repeat_twice(f):
    # use input function f to construct a new function g = f o f
    def g(x):
        return f(f(x))
    # return this function
    return g

plus_two = repeat_twice(plus_one) # plus_two is a function
plus_two(0)                       # == plus_one(plus_one(0)) == 2

# lambda functions (not how they are typically used)
plus_one = lambda x: x + 1
plus_two = lambda x: plus_one(plus_one(x))
plus_two(0)  # == plus_one(plus_one(0)) == 2

s    # pd.Series object
df   # pd.DataFrame object

# apply function to every series element
s.map(lambda x: x * x)      # a copy of s with every item squared

# apply function to every dataframe column
df.apply(lambda x: x.sum()) # a series containing the sum of each column

my_array = np.array([[1, 2, 3], [4, 5, 6])
my_list = [1, 2, 3]
my_float = 7.5
my_string = "HI THERE"
my_function = len

# methods
my_list.append(7)
my_number.hex()       # == 0x1.e000000000000p+2
my_string.lower()     # == "hi there"

# attributes
my_array.shape      # == (2, 3)
my_function.__doc__ # == 'Return the number of items in a container.'

# NOT PURE!!!!
def third_largest_item(list_of_nums):
   list_of_nums.sort()  # <-- Side effect: list_of_nums has been is modified
   global_variable = 5  # <-- Side effect: changing a global variable
   print("Hello")       # <-- Side effect: input/output operations

   return list_of_nums[-3] 

# Pure
def third_largest_item(list_of_nums):
   new_list = sorted(list_of_nums)  # list_of_nums is not changed
   return new_list[-3]

"""
find the minimum word (alphabetically) in a string
"""

# imperative (focused on steps)
def min_word(s):
    # make s lower case
    lower_s = ""
    for c in s:
        lower_s += c.lower()

    # split new_s into words
    words = []
    w = ""
    for c in new_s:
        if c == " ":
            words.append(w)
            w == ""
        else:
            w += c
    w += c

    # find lowest word alphabetically
    min_word = ""
    for w in words:
        if w < min_word:
            min_word = w

    return min_word

# declaritive (focused on results)
def min_words(s):
    return min(s.lower().split())

# imperative (steps)
y = f(x) # step 1
z = g(y) # step 2
w = h(z) # step 3

# declaritive (function composition)
w = h(g(f(x)))

# imperative (steps)
x = "This is a string"
y = x.lower()           # make lower case
z = y.split()           # split into a list of words
w = w.index("is")       # find the index of the first occurrence of the word "is"

# declarative (function composition)
w = ("This is a string"
        .lower()        # make lower case
        .split()        # split into a list of words
        .index("is"))   # find the index of the first occurrence of the word "is"

# imperative
def plot_number_of_rows_per_week(df):
    df1 = df.copy()                    # we don't want to change the original df
    
    weeks = df1['date_time'].dt.week() # get week of the year
    df1['week'] = weeks                # add column for the week of the year
    
    df2 = df1.groupby('week').size()   # count number of rows for each week
    df2.plot()                         # plot

# declarative
def plot_number_of_rows_per_week(df):
    (df.groupby(df.date_time.dt.week())  # group by week of the year
       .size()                           # count rows for each week
       .plot())                          # plot

class Tree:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

"""
Check if a certain value is in a tree
"""

# imperative (while loop + a stack)
def contains(tree, value):
    to_visit = [tree]  # list of nodes to visit
    while to_visit:
        node = to_visit.pop() # visit node
        
        if node is None:
            continue
        elif node.val == value:
            return True
        else:
            # explore child nodes
            to_visit.append(node.left)
            to_visit.append(node.right)
    
    return False

# declaritive (recursion)
def contains(tree, value):
    # base case
    if tree is None:
        return False
    
    # recursion
    return (tree.val == value 
              or contains(tree.left, val) 
              or contains(tree.right, val))

"""
Copy list and add one to every item.
"""

# imperative (for loop)
def add_one_to_each_item(old_list):
    new_list = old_list
    for n in old_list:
        new_list.append(n+1)
       
    return old_list
    
# declaritive (list comprehension)
def add_one_to_each_item(old_list):
    return [n + 1 for n in old_list] # list comprehension

"""
Divide all even numbers by 2.
"""

# imperative (for loop)
def divide_by_two_if_even(old_list):
    new_list = old_list
    for n in old_list:
        if n % 2 == 0: # even
            new_list.append(n // 2)
           
  return old_list
    
# declaritive (list comprehension)
def add_one_to_each_item(old_list):
    return [n // 2 for n in old_list if n % 2 == 0]

"""
Reverse each word in a string.
e.g. "This is a sentence." -> "sihT si a ecnetnes"
"""

# imperative (for loop)
def reverse_each_word(sentence):
    words = sentence.split() # split sentences
    s = ""
    for w in words:
        s += " " + w[::-1]  # add space and reversed word  
    return s[1:] # remove leading space
    
# declaritive (list comprehension and join)
def reverse_each_word(sentence):
    return " ".join([w[::-1]                       # reverse word 
                     for w in sentence.split()])   # for all words in the sentence

# list comprehension
[n for n in range(4) if n != 2]         # == [0, 1, 3]

# set comprehension
{n for n in range(4) if n != 2}         # == {0, 1, 3} 

# dictionary comprehension
{n:n+1 for n in range(4) if n != 2}     # == {0:1, 1:2, 3:4} 

# tuple comprehension
tuple(n for n in range(4) if n != 2)    # == (0, 1, 4)

# iterator comprehension
(n for n in range(4) if n != 2)         # an iterator (advanced concept)

sum(list_of_nums)              # sum numbers
min(list_of_nums)              # find smallest number
max(list_of_strings, key=len)  # find longest word
"".join(list_of_strings)       # concatenate strings
reversed(my_list)              # reverse the list
all(list_of_bools)             # True if all conditions are True
any(list_of_bools)             # True if at least one condition is True

# imperative
def sign(n):
    if n < 0:
        return -1
    elif n == 0:
        return 0
    else:
        return 1

# declaritive
def sign(n):
    return (-1 if n < 0 
               else (0 if n == 0 else 1))

def replace_negative_numbers_with_0(number_list):
    return [0 if x < 0 else x for x in number_list]

# pattern matching
x, _, y = [1, 2, 3]            # set x = 1 and y = 3 (ignore 2)
a, (b, c), d = (1, (2, 3), 4)  # set a = 1, b = 2, c = 3, d = 4

# swapping variables
a, b = b, a                    # swaps a and b
n_old, n = n, n + 1            # simaltaneously set n_old = n and n = n + 1

# cool iterators which loop over pairs
for index, item in enumerate(my_list):  # loop over index/items pairs
    pass 
    
for a, b in zip(list_a, list_b):        # loop over list_a and list_b in parallel
    pass 

for key, value in my_dict.items():      # loop over dictionary key/value pairs
    pass 

for i, (a, b) in enumerate(zip(list_a, list_b)):
    pass
    

# fast vectorized operations (declarative)
y = np.matmul(w, x) + b

def try_to_change_input(x):
    x += x  # will this change x?
    return x

# immutable
a = 1
try_to_change_input(a)   # == 2
a                        # == 1

b = "hello"
try_to_change_input(b)   # == "hellohello"
b                        # == "hello"

c = (1, 2, 3)
try_to_change_input(c)   # == (1, 2, 3, 1, 2, 3)
c                        # == (1, 2, 3)

# mutable
d = [1, 2, 3]
try_to_change_input(d)   # == [1, 2, 3, 1, 2, 3]
c                        # == [1, 2, 3, 1, 2, 3]   changed!

e = np.array([1, 2, 3])
try_to_change_input(e)   # == np.array([2, 4, 6])
e                        # == np.array([2, 4, 6])  changed!

# tuples of various lengths
(1, 2, 3)
(1, 2)
(1,)  # note the trailing comma; in Python: (1) == 1
()    # could also use tuple()

# An immutable linked list (built with 2-tuples)
my_list = (1, (2, (3, (4, (5, (6, None))

# even though it is immutable I can "change" the first element
my_list2 = (-1, my_list[1])  # == (-1, (2, (3, (4, (5, (6, None))

# but this doesn't change the original list
my_list                      # == (1, (2, (3, (4, (5, (6, None))

# an immutable tree (built with 3-tuples)
#     a
#    / \
#   b   e
#  / \   \ 
# c   d   f

t = ("a",                       # first element is the value
        ("b",                   # second element is the left child
            ("c", None, None), 
            ("d", None, None)), 
        ("e",                   # third element is the right child
            None, 
            ("f", None, None))

a = np.array([1, 2, 3])
a.setflags(write=False)  # makes immutable
a += 1                   # this will raise an error

d = {}

# tuples make good dictionary keys
d[1, 2] = 3  # key = (1,2) , value = 3
(1, 2) in d  # == True

# if you really need to use an immutable object as a key:

# convert lists to tuples
d[tuple(my_list)] = 3 

# convert sets and dictionaries to frozensets
d[frozenset(my_set)] = 3
d[frozenset(my_dict.items())] = 3

# convert numpy arrays to bytes
d[my_array.tobytes())] = 3

cache = {} # dict storing the results
def fib(n):
    """
    Computes nth Fibonacci number 
    0, 1, 1, 2, 3, 5, 8, ...
    """
    # check cache:
    if n in cache: return cache[n]
    
    # otherwise calculate result (and cache it)
    elif n == 0: result = cache[n] = 0
    elif n == 1: result = cache[n] = 1
    else: result = cache[n] = fib(n - 1) + fib(n - 2)
    
    return result

from functools import lru_cache

@lru_cache  # automatically memoizes this function
def fib(n):
    """
    Computes nth Fibonacci number 
    0, 1, 1, 2, 3, 5, 8, ...
    """
    if n == 0: return 0
    elif n == 1: return = 1
    else: return fib(n - 1) + fib(n - 2)

a      # type: A
b      # type: B
(a, b) # type: A x B

def add(a: int, b:int) -> int:  # type: (int x int) -> int
    return a + b

def add_curried(a: int):        # type: int -> (int -> int)
    return lambda b: a + b

add(2, 3)            # 5          type: int

add_curried(2)       # function   type: int -> int
add_curried(2)(3)    # 5          type: int

plus_one = add_curried(1)  # function (type: int -> int)