{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,1,2,3,5,8,13,21,34,55]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fibs :: [Integer]\n",
    "fibs = go 1 1\n",
    "  where\n",
    "    go a b = a : go b (a + b)\n",
    "\n",
    "print (take 10 fibs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,1,2,3,5,8,13,21,34,55]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib :: Int -> Integer\n",
    "fib n = go n 1 1\n",
    "  where\n",
    "    go 0 a _ = a\n",
    "    go n a b = go (n - 1) b (a + b)\n",
    "\n",
    "print (map fib [0..9])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,1,2,3,5,8,13,21,34,55]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "type Mat44 a = (a, a, a, a)\n",
    "\n",
    "mmul :: Num a => Mat44 a -> Mat44 a -> Mat44 a\n",
    "mmul (a, b, c, d) (a', b', c', d') = (a*a'+b*c', a*b'+b*d', c*a'+d*c', c*b'+d*d')\n",
    "\n",
    "mpow :: Num a => Int -> Mat44 a -> Mat44 a\n",
    "mpow x m\n",
    "  | x <= 1         = m\n",
    "  | x `rem` 2 == 1 = mmul m n2\n",
    "  | otherwise      = n2\n",
    "  where\n",
    "    n  = mpow (x `div` 2) m\n",
    "    n2 = mmul n n\n",
    "\n",
    "fib :: Int -> Integer\n",
    "fib n = let (a, _, _, _) = mpow n (1, 1, 1, 0) in a\n",
    "\n",
    "print (map fib [0..9])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}