{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 04 - Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Jupyter notebooks\n",
    "\n",
    "This is a space where text and code come together to form a coherent document. Throughout the course, we will make use of Jupyter notebooks for illustration purposes and for experimentation. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "Functions are a set of code statements grouped together that get executed, often on specific inputs, to perform a specific task. So far, we have seen many **built-in** Python functions such as:\n",
    "- Input/Output: `input()`, `print()`\n",
    "\n",
    "- Type-casting: `int()`, `float()`, `str()`\n",
    "\n",
    "- Other: `type()`, `id()`, `len()`, `abs()`.\n",
    "\n",
    "All of the above are built-in for the Python interpreter. Accordingly, no `import` statements are needed. We have also seen other useful functions from the `math` module, such as `math.ceil()`, `math.sqrt()`, `math.log()`, etc.\n",
    "\n",
    "In general, a function is characterized by three things:\n",
    "\n",
    "1) Its name: usually a descriptive name of the task being performed,\n",
    "\n",
    "2) Its input parameters, and\n",
    "\n",
    "3) Its return value.\n",
    "\n",
    "Functions can return either a value or `None`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## Motivation\n",
    "The motivation behind the use of functions boils down to multiple reasons:\n",
    "\n",
    "1) **Code re-usability**: Often times, there is need to execute the same set of statements but at different stages within the same code. Defining the set of statements in a function simplifies the task of performing the same logic multiple times.\n",
    "\n",
    "2) **Decomposition**: In addition to the above, it is generally a good idea to decompose a problem into subproblems, each of which can be solved by calling a specific function. This helps greatly when debugging complex code, by isolating the independent parts.\n",
    "\n",
    "3) **Abstraction**: functions allow to hide implementation details from the user. For instance, one can simply use the `math.log()` function by understanding that it takes two input parameters, without the need to know its implementation details (the algorithm used).\n",
    "\n",
    "4) **Code Management**: dividing big program into blocks aids in the long run, and the reasons above usually lead to good code management."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calling a function (i.e., using a function)\n",
    "### Function with return value\n",
    "If a function is named `my_function()` and takes as input some parameter `x`, it can be used by writing:\n",
    "```\n",
    "y = my_function(x) # result is stored in 'y'\n",
    "```\n",
    "For instance, the `len()` function takes 1 object (e.g., `str`, `list`, etc.) as input and returns the number of items in said input (an `int`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "int"
      ]
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "source": [
    "s = \"CSC243\"\n",
    "n = len(s)\n",
    "type(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another example is the `input()` function, which takes a `str` message to display and returns the `str` representation of what the user typed in:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Please enter a something: hello\n"
     ]
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "str"
      ]
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "source": [
    "user_input = input(\"Please enter a something: \")\n",
    "type(user_input)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function without a return value\n",
    "A different function `another_function()` may also take as input `x`, but return nothing. In this case, the syntax for using it is:\n",
    "```\n",
    "another_function(x) # if it does not return a result\n",
    "```\n",
    "An example of a function that does not return a value is the `print()` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Output message\n"
     ]
    }
   ],
   "source": [
    "print(\"Output message\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that `print()` is used without being assigned a variable to store its result. If this is done, Python will not raise an error. \n",
    "\n",
    "In such cases, there is an implicit return value of type `NoneType`. Recall from topic 1 that `NoneType` is a built-in data type in Python like `int`, `float`, `str`, etc. \n",
    "Hence, for a function that does not return a result, assigning a return value to a variable will set it to the *value* `None`. Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "This message is printed to the console.\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "result = print(\"This message is printed to the console.\")\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When a function is called, the Python interpreter jumps to the function and executes statements\n",
    "in the body. When the function is done executing, the interpreter jumps back to the part of program that called the\n",
    "function. This happens when we reach the `return` statement or the end of the block of statements if no `return` is specified."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining a function\n",
    "In Python, we can define our own functions. The general 'recipe' for creating a function is to answer the following questions:\n",
    "\n",
    "|Question |Answer |\n",
    "| --- | --- |\n",
    "| What is the task to achieve?| Develop the main algorithm to complete the task|\n",
    "| What are the inputs to my function?| Determine these variables|\n",
    "| What is the return value of my function (if any)? | Determine this variable(s) |\n",
    "\n",
    "### Syntax\n",
    "We use the `def` keyword to begin defining our function. Then, we specify a name for the function and the list of **formal parameters** (i.e., inputs to the function). Finally, we use the `return` keyword to indicate what the function must give back from the main algorithm.\n",
    "```\n",
    "def function_name(input_1, input_2, ..., input_N):\n",
    "    \n",
    "    \n",
    "    block of statements\n",
    "    \n",
    "   \n",
    "    return value\n",
    "```\n",
    "\n",
    "#### Example: defining our own (approximate) square-root  function\n",
    "|Question |Answer |\n",
    "| --- | --- |\n",
    "| What is the task to achieve?| Approx. square-root via the Bisection Method|\n",
    "| What are the inputs to my function?| A number (`x >= 0`) and an error-tolerance (called `eps` or `epsilon`)|\n",
    "| What is the return value of my function (if any)? |The variable storing the result (`mid`) |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_sqrt(x, epsilon):\n",
    "    if x == 1 or x == 0:\n",
    "        return x\n",
    "    \n",
    "    elif x > 1:\n",
    "        low = 1\n",
    "        high = x\n",
    "    \n",
    "    else: # if 0 < x < 1\n",
    "        low = x\n",
    "        high = 1\n",
    "    \n",
    "    mid = (low + high)/2\n",
    "    while abs(mid*mid - x) > epsilon:\n",
    "        if mid*mid < x:\n",
    "            low = mid\n",
    "        else:\n",
    "            high = mid\n",
    "        mid = (low + high)/2\n",
    "    \n",
    "    return mid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since the `my_sqrt()` function defined above returns the (approximate) square-root, here is how we can call (use) it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Enter a non-negative number: 2\n",
      "1.414215087890625\n"
     ]
    }
   ],
   "source": [
    "a = float(input(\"Enter a non-negative number: \"))\n",
    "b = my_sqrt(a, 1E-5)\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Default parameters\n",
    "Functions can be defined to take default values for some parameters, if no values are provided to the function call for these parramters. For example, the `math.log(x, base)` which normally takes two arguments, will set the default value for `base` (the 2nd argument) to `math.e = 2.71828...`, if nothing is provided when the function is used. Accordingly, using `math.log(2)` will correspond to computing the natural logarithm of `2` or to `math.log(2, math.e)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Are the resuls equal? True\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "result = math.log(2, math.e)\n",
    "result_default = math.log(2) # calling function without 2nd argument\n",
    "\n",
    "print(\"Are the resuls equal?\", result == result_default)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example: setting default parameters in our (approximate) square-root function\n",
    "In our square-root function, we can pass a default value for `epsilon` by specifying it in the function header:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_sqrt(x, epsilon=1E-5):\n",
    "    if x == 1 or x == 0:\n",
    "        return x\n",
    "    elif x > 1:\n",
    "        low = 1\n",
    "        high = x\n",
    "    else: # if 0 < x < 1\n",
    "        low = x\n",
    "        high = 1\n",
    "    \n",
    "    mid = (low + high)/2\n",
    "    while abs(mid*mid - x) > epsilon:\n",
    "        if mid*mid < x:\n",
    "            low = mid\n",
    "        else:\n",
    "            high = mid\n",
    "        mid = (low + high)/2\n",
    "    \n",
    "    return mid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we may use `my_sqrt()` without a value for `epsilon`; the default value above (`1E-5`) will be assumed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "2.2360687255859375\n"
     ]
    }
   ],
   "source": [
    "x = 5\n",
    "result = my_sqrt(5)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Returning more than one value\n",
    "To return more than one value, we can use a `tuple` as a return value. Let's look at an example that defines a function to find both the minimum and maximum values in a list `L`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min_max(L):\n",
    "    if len(L) == 0:\n",
    "        return tuple() # return empty tuple\n",
    "    elif len(L) == 1:\n",
    "        return (L[0], L[0])\n",
    "    else:\n",
    "        # begin algorithm\n",
    "        # initializations\n",
    "        minimum = L[0]\n",
    "        maximum = L[0]\n",
    "        \n",
    "        for i in range(1, len(L)):\n",
    "            if L[i] < minimum:\n",
    "                minimum = L[i]\n",
    "            elif L[i] > maximum:\n",
    "                maximum = L[i]\n",
    "        # end of algorithm\n",
    "        \n",
    "        return (minimum, maximum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "minimum of [-1, -6, 0, 8, 10, 2, 5, 1] is -6\n",
      "maximum of [-1, -6, 0, 8, 10, 2, 5, 1] is 10\n"
     ]
    }
   ],
   "source": [
    "L = [-1, -6, 0, 8, 10, 2, 5, 1]\n",
    "(mini, maxi) = min_max(L)\n",
    "print(\"minimum of\", L, \"is\", mini)\n",
    "print(\"maximum of\", L, \"is\", maxi)\n",
    "\n",
    "#result = min_max(L)\n",
    "#print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Function namespace\n",
    "Each function defines a **namespace**, also called a **scope**. The **scope** of a variable is the part of a program where the variable can be accessed. A local variable is a variable that can be accessed only inside the scope of a function. Accordingly, initializing a variable in a function makes it local in the function’s scope. When a function is called, a new **stackframe** is created in the execution stack to keep track of all names defined within the function and their current bindings.\n",
    "\n",
    "Example (track on [Python Tutor](https://pythontutor.com)):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def max_val(x, y):\n",
    "    if x < y:\n",
    "        return y\n",
    "    else:\n",
    "        return x\n",
    "\n",
    "z = max_val(3, 5)\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functions handling lists\n",
    "In a function, a variable of type `list` can be:\n",
    "\n",
    "1) An input argument\n",
    "\n",
    "2) A local variable\n",
    "\n",
    "3) A return value\n",
    "\n",
    "Passing a `list` to a function and returning one from a function are done by assignment, which is efficient. This implies that if a `list` is passed as an input argument, changing the list in the function will change its actual values and not their copies. This is useful when we need to modify our list, for example when sorting it.\n",
    "\n",
    "Example (track on [Python Tutor](https://pythontutor.com)):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "A: [0, 5, 9]\n",
      "A: [-1, 5, 9]\n",
      "B: [-1, 5, 9, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def f(L, n, x):\n",
    "    L2 = [L[0]]*n\n",
    "    L[0] = x\n",
    "    L3 = L + L2\n",
    "    return L3\n",
    "\n",
    "A = [0, 5, 9]\n",
    "print(\"A:\", A)\n",
    "B = f(A, 2, -1)\n",
    "print(\"A:\", A)\n",
    "print(\"B:\", B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above example, we lose access to `L2` since it is local to the function `f`. The memory reserved for storing `L2` will be release back to the Operating System by the Python garbage collector. The garbage collector is a process that awakens to clean up objects in memory to which we don't have direct/indirect access."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Methods associated with data types\n",
    "### General Setup\n",
    "Types in Python have available methods associated with them. The general setup is the following: if `T` is a data type and `x` is an object of type `T`, then the method `f` is is a member function of `T`; possibly with input paramters and a return value. Since it's a member, it should be accessed using `.` which is the member access operator. \n",
    "\n",
    "Calling `T.f`:\n",
    "\n",
    "○ `v = x.f(input parameters)`, if `f` has a return value\n",
    "\n",
    "○ `x.f(input parameters)`, if `f` has no return value\n",
    "\n",
    "Calling `f(input parameters)` without `x.` gives an error. If `T` is mutable, `T.f` may modify `x` by design."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Methods associated with the `str` data type\n",
    "#### The `str.split` method\n",
    "Recall the `str.split()` method, which is meant to be called on a `str` object. If `s` is a string, `s.split(sep)` returns a `list` of words (substrings) in `s`, using `sep` as a separator.\n",
    "\n",
    "The default separator is \"` `\" (a whitespace). In other words, if we have a string which consists of words delimited by whitespaces \"` `\", we can decouple the words using the `split()` method without passing it any argument. \n",
    "\n",
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "['Lebanese', 'American', 'University']\n"
     ]
    }
   ],
   "source": [
    "my_string = \"Lebanese American University\"\n",
    "L = my_string.split() # calling the split method\n",
    "print(L) # printing the return value of the above "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As can be seen from the above, the return value of the `split()` method is a `list` of strings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The `str.join` method\n",
    "In the opposite direction, we have the `str.join()` method. If `sep` is a string, and `L` is a list (or tuple) of strings, `sep.join(L)` returns a string consisting of the elements in `L` joined by `sep`. Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "After joining: Hello | CSC | 243\n"
     ]
    }
   ],
   "source": [
    "my_string = \"Lebanese American University\"\n",
    "\n",
    "sep = \" | \"\n",
    "L = [\"Hello\", \"CSC\", \"243\"]\n",
    "my_string = sep.join(L)\n",
    "print(\"After joining:\", my_string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Methods associated with the `list` type\n",
    "#### The `list.append` method\n",
    "We have seen the method `list.copy()`, which returns another list. Another method is `list.append(e)`, which adds the object `e` to the end of a list. `L.append(e)` has the same effect on `L` as `L = L + [e]`. `L.append` modifies `L` and has no return a value.\n",
    "\n",
    "Example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "['Hello', 'CSC', '243']\n"
     ]
    }
   ],
   "source": [
    "L = [\"Hello\", \"CSC\"]\n",
    "L.append(\"243\")\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that lists are implemented using contiguous memory cells so that access\n",
    "to `L[i]` is very efficient, given `i`. If enough contiguous cells are available, `e` is added to the end of the list efficiently in memory. Otherwise, the whole list is copied to new place in memory and resized by appending enough contiguous cells. Thus, in the worst case, a single append takes in the order of the `len(L)` time, which is a lot for long lists. However, the overhead on a long sequence of `append` operations is not substantial; this an advantage over `L = L + [e]`, which always creates a new list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The `list.extend` method\n",
    "`L.extend(L2)`, where `L2` is a list, adds the items in `L2` to the end of `L`. Like `L.append()`, `L.extend()` mutates `L` and has no return value.\n",
    "\n",
    "`L.extend(L2)` has the same effect on `L` as `L = L + L2`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "L = [1, 2]\n",
    "L2 = [3, 4]\n",
    "L.extend(L2)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Useful references\n",
    "- For a list of built-in Python functions, visit the [official Python documentation](https://docs.python.org/3/library/functions.html).\n",
    "\n",
    "- To see other `list` methods, visit the [official Python Documentation](https://docs.python.org/3/tutorial/datastructures.html)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
