{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fibonacci\n",
    "\n",
    "Calculate the *Fibonacci number* $F_n$ in Haskell. Some solutions from the [Haskell Wiki](https://wiki.haskell.org/The_Fibonacci_sequence).\n",
    "\n",
    "## Standard solution\n",
    "\n",
    "This get's slow pretty quickly. The runtime complexity is $\\cal O(fib(n))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "fibG n \n",
    "  | n == 0 = 0\n",
    "  | n == 1 = 1\n",
    "  | otherwise = fibG (n-1) + fibG (n-2)\n",
    "  \n",
    "fib 0 = 0\n",
    "fib 1 = 1\n",
    "fib n = fib (n-1) + fib (n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works only for very small values of `n`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib 10\n",
    "fibG 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accumulator\n",
    "\n",
    "The state of the calculation is passed in a tuple. Uses pattern matching with guards. The accumulator helps to make this $\\cal O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib n = go n (0,1)\n",
    "  where\n",
    "    go 0 (a, _) = a\n",
    "    go n (a, b) = go (n-1) (b, a+b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12586269025"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib 50"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Infinite sequence\n",
    "\n",
    "Calculates the infinite sequence of Fibonacci numbers. Then picks the nth element. Relies on *lazy evaluation* to prevent endless recursion. Also $\\cal O(n)$. Can be considered the most idiomatic Haskell version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "fib n = fibs !! n\n",
    "fibs = 0 : 1 : zipWith (+) fibs (tail fibs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12586269025"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib 50"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}