ch7-efficiency.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "hidden": false
   },
   "source": [
    "# Chapter 7 Efficiency\n",
    "\n",
    "미국의 컴퓨터 과학자인 Alan Perlis가 애기하기를...\n",
    "\n",
    "> A functional programmer was someone who knew the value of everything and the cost of nothing.\n",
    "\n",
    "functional programming의 **성능**과 **효율성**은?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.1 Lazy Evaluation\n",
    "\n",
    "\n",
    "## Lazy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2401"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sqr x = x * x\n",
    "\n",
    "sqr (sqr (3+4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<s>위 expression에 대해서 아래와 같이 lazy하게 reduction 된다.</s>\n",
    "\n",
    "    sqr (sqr (3+4))\n",
    "    = sqr (3+4) * sqr (3+4)\n",
    "    = ((3+4)*(3+4)) * ((3+4)*(3+4))\n",
    "    = ...\n",
    "    = 2401\n",
    "\n",
    "lazy evaluation은 아래와 같이 reduction된다.\n",
    "\n",
    "    sqr (sqr (3+4))\n",
    "    = let x = sqr (3+4) in sqr x\n",
    "    = let y = 3+4 in\n",
    "      let x = sqr y in sqr x\n",
    "    = let y = 7 in\n",
    "      let x = sqr y in sqr x\n",
    "    = let x = sqr 7 in sqr x\n",
    "    = let x = 7 * 7 in sqr x\n",
    "    = let x = 49 in sqr x\n",
    "    = 49 * 49\n",
    "    = 2401\n",
    "\n",
    "\n",
    "> <s>Lazy evaluation arguments는 필요한 시점에 단 한 번만 evaluate 된다.</s>\n",
    "\n",
    "보다 정확하게 얘기하면\n",
    "\n",
    "> Lazy evaluation에서 arguments는 **필요한 시점**에 단 **한 번만** **head normal form** 으로 evaluate 된다.\n",
    "\n",
    "## Head Normal Form\n",
    "\n",
    "(Weak) Head Normal Form은 top-level이 아래로 구성되어 있다.\n",
    "\n",
    " * data constructor\n",
    " * fully reduced lambda abstraction (weak: any lambda abstraction)\n",
    "\n",
    "NF는 HNF이나 HNF가 NF는 아니다.\n",
    "\n",
    " * NF: 42, (2,\"hello\"), \\x -> (x+1), e1, e2\n",
    " * HNF: (1+2,2+3), \\x -> 2+2, 'h':(\"e\"++\"llo\"), x, (e1, e2)\n",
    " * ???: 1+1, (\\x -> x+1) 2\n",
    "\n",
    "'sqr (head xs)'의 evaluation\n",
    "\n",
    "    sqr (head xs)\n",
    "    = let a = head xs in sqr a\n",
    "    = let b = xs in\n",
    "      let a = head xs in sqr a\n",
    "    = let b = y:ys in\n",
    "      let a = head xs in sqr a\n",
    "    = let a = head (y:ys) in sqr a\n",
    "    = let a = y in sqr a\n",
    "    = sqr y\n",
    "    = y * y\n",
    "\n",
    "## Common Subexpression elimination\n",
    "\n",
    "    subseqs (x:xs) = subseqs xs ++ map (x:) (subseqs xs)\n",
    "    subseqs' (x:xs) = xss ++ map (x:) xss\n",
    "                      where xss = subseqs' xs\n",
    "\n",
    "subseqs는 'subseqs xs'가 2번 evaluate된다. 이것을 where로 분리하는 경우 1번만 연산할 수 있으나 **haskell은 common subexpression elimination 을 자동으로 하지 않는다.**\n",
    "추가 공간을 사용하여 시간을 최적화하는 것이므로 프로그래머가 결정해야하는 사항임.\n",
    "\n",
    "## Binding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24133"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "foo1 n = sum (take n primes)\n",
    "         where\n",
    "           primes = [x | x <- [2..], divisors x == [x]]\n",
    "           divisors x = [d | d <- [2..x], x `mod` d == 0]\n",
    "foo1 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24133"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "foo2 n = sum (take n primes)\n",
    "primes = [x | x <- [2..], divisors x == [x]]\n",
    "divisors x = [d | d <- [2..x], x `mod` d == 0]\n",
    "\n",
    "foo2 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24133"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "foo3 = \\n -> sum (take n primes)\n",
    "       where\n",
    "         primes = [x | x <- [2..], divisors x == [x]]\n",
    "         divisors x = [d | d <- [2..x], x `mod` d == 0]\n",
    "\n",
    "foo3 100"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "primes, divisors의 binding\n",
    "\n",
    " * foo1: 'foo1 n'에 bind 됨\n",
    " * foo2: global에 bind 됨\n",
    " * foo3: 'foo3'에 bind 됨\n",
    "\n",
    "foo2, foo3의 경우 evaluation 결과를 재사용하나 공간 사용량이 증가함"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.2. Controlling space\n",
    "\n",
    "## lazy and space\n",
    "\n",
    "lazy evaluation\n",
    "\n",
    "    sum [1..1000]\n",
    "    = foldl (+) 0 [1..1000]\n",
    "    = foldl (+) (0+1) [2..1000]\n",
    "    = foldl (+) ((0+1)+2) [3..1000]\n",
    "    = ...\n",
    "    = 500500\n",
    "\n",
    "eager evaluation\n",
    "\n",
    "    sum [1..1000]\n",
    "    = foldl (+) 0 [1..1000]\n",
    "    = foldl (+) (0+1) [2..1000]\n",
    "    = foldl (+) 1 [2..1000]\n",
    "    = foldl (+) (1+2) [3..1000]\n",
    "    = ...\n",
    "    = 500500\n",
    "\n",
    "**space를 제어하기 위해서는 eager evaluation을 lazy evaluation과 함께 사용하는 것이 좋다.**\n",
    "\n",
    "## eager evaluation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- seq :: a -> b -> b\n",
    "\n",
    "-- Data.List.foldl'\n",
    "foldl' :: (b -> a -> b) -> b -> [a] -> b\n",
    "foldl' f e [] = e\n",
    "foldl' f e (x:xs) = y `seq` foldl' f y xs\n",
    "                    where y = f e x\n",
    "\n",
    "foldl' (+) 0 [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Data\\.List\\.sum과 foldl'은 위 방식으로 구현됨.\n",
    "\n",
    "lazy와 eager 구현은 strict function에 대해서는 동일하다. (f &perp; = &perp; 라면, f는 strict하다.)\n",
    "\n",
    "## mean 예제"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mean [] = 0\n",
    "mean xs = sum xs / fromIntegral (length xs)\n",
    "\n",
    "mean [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "xs의 순회가 2번 발생한다. tupling을 사용하여 1번 순회로 합과 길이를 구함."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(55.0,10)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sumlen :: [Float] -> (Float,Int)\n",
    "sumlen = foldr f (0,0)\n",
    "             where f x (s,n) = (s+x,n+1)\n",
    "\n",
    "sumlen [1..10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mean' [] = 0\n",
    "mean' xs = s / fromIntegral n\n",
    "          where (s,n) = sumlen xs\n",
    "mean' [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "space leak을 제거하기 위해서 foldl'을 사용"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(55,10)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sumlen = foldl' g (0,0)\n",
    "         where g (s,n) x = (s+x,n+1)\n",
    "\n",
    "sumlen [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "HNF인 (s+x,n+1)에 eager evaluation 적용"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(55,10)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sumlen = foldl' f (0,0)\n",
    "         where f (s,n) x = s `seq` n `seq` (s+x,n+1)\n",
    "\n",
    "sumlen [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "two more application operators\n",
    "\n",
    " * $: lazy evaluation\n",
    " * \\$\\!: eager evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.3 Controlling time\n",
    "\n",
    "## tips for time\n",
    "\n",
    "eager evalution을 사용하여 쉽게 제어할 수 있으나 속도는 그렇지 못 하다.\n",
    "\n",
    "GHC 문서가 제시하는 속도향상의 키 포인트 3가지\n",
    "\n",
    "1. GHC Profiling 도구를 사용해라\n",
    "2. 알고리즘을 개선해라\n",
    "3. 가능하면 제공되는 라이브러리를 사용하라. (매우 최적화되어 있고, 컴파일되어 있음.)\n",
    "\n",
    "추가적인 팁 2가지\n",
    "\n",
    "* 'Strict funcions are your dear friends': 보통 eager evaluation이 lazy evaluation보다 overhead가 적다.\n",
    "* 요구사항을 만족하는 최적의 type을 명시적으로 사용할 것: Integer보다는 Int가 좋다.\n",
    "\n",
    "이러한 방법들은 asymptotic time complexity을 변환시키지 못 하므로 효과가 작다. 그러나 잘못된 코드는 asymptotic complexity에 영향을 줄 수도 있다.\n",
    "\n",
    "## cartesian product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cp [] = [[]]\n",
    "cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss]\n",
    "\n",
    "cp [[1,2],[3,4],[5,6]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cp' = foldr op [[]]\n",
    "      where op xs yss = [x:ys | x <- xs, ys <- yss]\n",
    "\n",
    "cp' [[1,2],[3,4],[5,6]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "cp보다 cp'의 evaluation time이 훨씬 적다. cp는 cp xss를 xs의 길이만큼 반복 계산한다. cp의 list comprehension을 제거하면 아래 형태로 이해가 쉬워진다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cp [] = [[]]\n",
    "cp (xs:xss) = concat (map f xs)\n",
    "              where f x = [x:ys | ys <- cp xss]\n",
    "\n",
    "cp [[1,2],[3,4],[5,6]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "아래 cp''는 cp'와 동일한 성능을 가진다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cp'' [] = [[]]\n",
    "cp'' (xs:xss) = [x:ys | x <- xs, ys <- yss]\n",
    "                where yss = cp xss\n",
    "\n",
    "cp'' [[1,2],[3,4],[5,6]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.4 Analysing time\n",
    "\n",
    "* 시간 복잡도는 expression의 속성이지 value의 속성은 아니다.\n",
    "* GHCi에서는 reduction step이 아닌 소요시간만을 측정한다. reduction 단계는 소요 시간과 반드시 일치하지는 않는다.\n",
    "* 상황에 따라서 다른 측정 방법이 필요하다. 예를 들면 concat xss의 경우 n보다는 (m,n)이 적합하다.\n",
    "* 시간 복잡도 측정은 eager evaluation으로 행한다. lazy evaluation은 측정이 어려우며 일반적으로 eager evaluation의 time이 lazy evaluation의 time 보다 tight boundary를 가진다.\n",
    "\n",
    "## Concat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/*\n",
       "Custom IHaskell CSS.\n",
       "*/\n",
       "\n",
       "/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "    display: block;\n",
       "    padding-bottom: 1.3em;\n",
       "    padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "    display: block;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "    display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "    display: block;\n",
       "    margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "    font-weight: bold;\n",
       "    font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       "/* Styles used for basic displays */\n",
       ".get-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "    white-space: pre-wrap;\n",
       "}\n",
       "\n",
       ".show-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    margin-left: 1em;\n",
       "}\n",
       "\n",
       ".mono {\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".err-msg {\n",
       "    color: red;\n",
       "    font-style: italic;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       "#unshowable {\n",
       "    color: red;\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       ".err-msg.in.collapse {\n",
       "  padding-top: 0.7em;\n",
       "}\n",
       "\n",
       "/* Code that will get highlighted before it is highlighted */\n",
       ".highlight-code {\n",
       "    white-space: pre;\n",
       "    font-family: monospace;\n",
       "}\n",
       "\n",
       "/* Hlint styles */\n",
       ".suggestion-warning { \n",
       "    font-weight: bold;\n",
       "    color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "    font-weight: bold;\n",
       "    color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "    font-weight: bold;\n",
       "}\n",
       "</style> <div class=\"suggestion-name\" style=\"clear:both;\">Eta reduce</div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Found:</div>  <div class=\"highlight-code\" id=\"haskell\">concat xss = foldr (++) [] xss</div> </div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Why Not:</div>  <div class=\"highlight-code\" id=\"haskell\">concat = foldr (++) []</div> </div>  <div class=\"suggestion-name\" style=\"clear:both;\">Use concat</div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Found:</div>  <div class=\"highlight-code\" id=\"haskell\">foldr (++) []</div> </div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Why Not:</div>  <div class=\"highlight-code\" id=\"haskell\">concat</div> </div> "
      ],
      "text/plain": [
       "Line 1: Eta reduce\n",
       "Found:\n",
       "concat xss = foldr (++) [] xss\n",
       "Why not:\n",
       "concat = foldr (++) []Line 1: Use concat\n",
       "Found:\n",
       "foldr (++) []\n",
       "Why not:\n",
       "concat"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[1,2,3,4]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concat xss = foldr (++) [] xss\n",
    "\n",
    "concat [[1,2],[3,4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/*\n",
       "Custom IHaskell CSS.\n",
       "*/\n",
       "\n",
       "/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "    display: block;\n",
       "    padding-bottom: 1.3em;\n",
       "    padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "    display: block;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "    display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "    display: block;\n",
       "    margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "    font-weight: bold;\n",
       "    font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       "/* Styles used for basic displays */\n",
       ".get-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "    white-space: pre-wrap;\n",
       "}\n",
       "\n",
       ".show-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    margin-left: 1em;\n",
       "}\n",
       "\n",
       ".mono {\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".err-msg {\n",
       "    color: red;\n",
       "    font-style: italic;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       "#unshowable {\n",
       "    color: red;\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       ".err-msg.in.collapse {\n",
       "  padding-top: 0.7em;\n",
       "}\n",
       "\n",
       "/* Code that will get highlighted before it is highlighted */\n",
       ".highlight-code {\n",
       "    white-space: pre;\n",
       "    font-family: monospace;\n",
       "}\n",
       "\n",
       "/* Hlint styles */\n",
       ".suggestion-warning { \n",
       "    font-weight: bold;\n",
       "    color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "    font-weight: bold;\n",
       "    color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "    font-weight: bold;\n",
       "}\n",
       "</style> <div class=\"suggestion-name\" style=\"clear:both;\">Eta reduce</div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Found:</div>  <div class=\"highlight-code\" id=\"haskell\">concat' xss = foldl (++) [] xss</div> </div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Why Not:</div>  <div class=\"highlight-code\" id=\"haskell\">concat' = foldl (++) []</div> </div>  <div class=\"suggestion-name\" style=\"clear:both;\">Use concat</div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Found:</div>  <div class=\"highlight-code\" id=\"haskell\">foldl (++) []</div> </div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Why Not:</div>  <div class=\"highlight-code\" id=\"haskell\">concat</div> </div> "
      ],
      "text/plain": [
       "Line 1: Eta reduce\n",
       "Found:\n",
       "concat' xss = foldl (++) [] xss\n",
       "Why not:\n",
       "concat' = foldl (++) []Line 1: Use concat\n",
       "Found:\n",
       "foldl (++) []\n",
       "Why not:\n",
       "concat"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[1,2,3,4]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concat' xss = foldl (++) [] xss\n",
    "\n",
    "concat' [[1,2],[3,4]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "T(++)(n,m) = $Ө(n)$임\n",
    "\n",
    "* concat: 길이 n의 리스트를 m회 (++) 함 $\\Theta (mn)$\n",
    "* concat': mn으로 증가하는 accumulator를 n회 (++) 함. $\\Theta (m^2 n$)\n",
    "\n",
    "concat은 foldr로 구현하는 것이 더 효율적임. foldl/foldr/foldl'이 적합한 경우가 다르다.\n",
    "\n",
    "## subseq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "subseqs [] = [[]]\n",
    "subseqs (x:xs) = subseqs xs ++ map (x:) (subseqs xs)\n",
    "\n",
    "subseqs [1..3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "subseqs' [] = [[]]\n",
    "subseqs' (x:xs) = xss ++ map (x:) xss\n",
    "                  where xss = subseqs' xs\n",
    "\n",
    "subseqs' [1..3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "map (x:)는 $\\Theta (2^n)$이므로 \n",
    "\n",
    "* $T(subseqs)(n+1) = 2T(subseqs)(n) + \\Theta (2^n) \\rightarrow T(subseqs)(n) = \\Theta (n 2^n)$\n",
    "* $T(subseqs')(n+1) = T(subseqs')(n) + \\Theta (2^n) \\rightarrow T(subseqs')(n) = \\Theta (2^n)$\n",
    "\n",
    "subseqs'가 logarithmic factor로 더 빠르다. 속도가 중요한 경우 common subexpression elimination을 잘 활용하자.\n",
    "\n",
    "## cartesian product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1,3],[1,4],[2,3],[2,4]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cp [] = [[]]\n",
    "cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss]\n",
    "\n",
    "cp [[1,2],[3,4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1,3],[1,4],[2,3],[2,4]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cp' = foldr op [[]]\n",
    "      where op xs yss = [x:ys | x <- xs, ys <- yss]\n",
    "\n",
    "cp' [[1,2],[3,4]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "cp에서 cp xss가 $\\Theta (n^m)$ 이고 m회만큼 반복하게 된다.\n",
    "\n",
    "* $T(cp)(m,n) = \\Theta (m n^m)$\n",
    "* $T(cp')(m,n) = \\Theta (n^m)$\n",
    "\n",
    "cp'가 logarithmic factor로 더 빠르다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.5 Accumulating Parameter\n",
    "\n",
    "argument를 추가로 사용하여 속도를 향상시키는 것을 accumulating parameter라고 한다.\n",
    "\n",
    "## reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10,9,8,7,6,5,4,3,2,1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "reverse [] = []\n",
    "reverse (x:xs) = reverse xs ++ [x]\n",
    "\n",
    "reverse [1..10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(++)가 $\\Theta (n)$이고 n번 재귀를 하므로 T(reverse)(n)은 $\\theta (n^2)$ 이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[10,9,8,7,6,5,4,3,2,1]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "revcat :: [a] -> [a] -> [a]\n",
    "revcat xs ys = reverse xs ++ ys\n",
    "\n",
    "revcat [1..10] []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "revcat은 accumulator를 사용해서 (++) 대신 (:) 을 사용한 것과 동일해짐. 따라서 $\\theta (n)$ 임\n",
    "\n",
    "    [x] ++ xs = x:xs\n",
    "\n",
    "## length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "length :: [a] -> Int\n",
    "length [] = 0\n",
    "length (x:xs) = length xs + 1\n",
    "\n",
    "length [1..10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "lenplus :: [a] -> Int -> Int\n",
    "lenplus [] n = n\n",
    "lenplus (x:xs) n = lenplus xs (1+n)\n",
    "\n",
    "lenplus [1..10] 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "time은 $\\Theta (n)$으로 동일하다. length는 space가 $\\Theta (n)$으로 증가하나 lenplus는 $\\Theta (1)$ 이다. (haskell의 length는 lenplus처럼 구현됨.)\n",
    "\n",
    "## tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data GenTree a = Node a [GenTree a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/*\n",
       "Custom IHaskell CSS.\n",
       "*/\n",
       "\n",
       "/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "    display: block;\n",
       "    padding-bottom: 1.3em;\n",
       "    padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "    display: block;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "    display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "    display: block;\n",
       "    margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "    font-weight: bold;\n",
       "    font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       "/* Styles used for basic displays */\n",
       ".get-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "    white-space: pre-wrap;\n",
       "}\n",
       "\n",
       ".show-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    margin-left: 1em;\n",
       "}\n",
       "\n",
       ".mono {\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".err-msg {\n",
       "    color: red;\n",
       "    font-style: italic;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       "#unshowable {\n",
       "    color: red;\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       ".err-msg.in.collapse {\n",
       "  padding-top: 0.7em;\n",
       "}\n",
       "\n",
       "/* Code that will get highlighted before it is highlighted */\n",
       ".highlight-code {\n",
       "    white-space: pre;\n",
       "    font-family: monospace;\n",
       "}\n",
       "\n",
       "/* Hlint styles */\n",
       ".suggestion-warning { \n",
       "    font-weight: bold;\n",
       "    color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "    font-weight: bold;\n",
       "    color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "    font-weight: bold;\n",
       "}\n",
       "</style> <div class=\"suggestion-name\" style=\"clear:both;\">Use concatMap</div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Found:</div>  <div class=\"highlight-code\" id=\"haskell\">concat (map labels ts)</div> </div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Why Not:</div>  <div class=\"highlight-code\" id=\"haskell\">concatMap labels ts</div> </div> "
      ],
      "text/plain": [
       "Line 2: Use concatMap\n",
       "Found:\n",
       "concat (map labels ts)\n",
       "Why not:\n",
       "concatMap labels ts"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[1,2,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "labels :: GenTree a -> [a]\n",
    "labels (Node x ts) = x:concat (map labels ts)\n",
    "\n",
    "labels (Node 1 [Node 2 [],Node 3 []])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "       1\n",
    "      / \\\n",
    "     2   3 labels = \"123\"\n",
    "\n",
    "> $T(labels)(1,k) = \\Theta(1)$\n",
    "> $T(labels)(h+1,k) = \\Theta(1) + T(concat)(k,s) + T(map labels)(h,k)$\n",
    "\n",
    "각 높이에서 k개의 subtree에 대해서 map labels가 수행되고 이것들을 concat해야됨. \n",
    "\n",
    "$$T(labels)(h+1,k) = \\Theta(k^{h+1}) + k T(labels)(h,k)$$\n",
    "\n",
    "따라서 $s = k^h$일때 $\\Theta (s \\log s)$ 임."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/*\n",
       "Custom IHaskell CSS.\n",
       "*/\n",
       "\n",
       "/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "    display: block;\n",
       "    padding-bottom: 1.3em;\n",
       "    padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "    display: block;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "    display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "    display: block;\n",
       "    margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "    font-weight: bold;\n",
       "    font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "    font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       "/* Styles used for basic displays */\n",
       ".get-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "    white-space: pre-wrap;\n",
       "}\n",
       "\n",
       ".show-type {\n",
       "    color: green;\n",
       "    font-weight: bold;\n",
       "    font-family: monospace;\n",
       "    margin-left: 1em;\n",
       "}\n",
       "\n",
       ".mono {\n",
       "    font-family: monospace;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       ".err-msg {\n",
       "    color: red;\n",
       "    font-style: italic;\n",
       "    font-family: monospace;\n",
       "    white-space: pre;\n",
       "    display: block;\n",
       "}\n",
       "\n",
       "#unshowable {\n",
       "    color: red;\n",
       "    font-weight: bold;\n",
       "}\n",
       "\n",
       ".err-msg.in.collapse {\n",
       "  padding-top: 0.7em;\n",
       "}\n",
       "\n",
       "/* Code that will get highlighted before it is highlighted */\n",
       ".highlight-code {\n",
       "    white-space: pre;\n",
       "    font-family: monospace;\n",
       "}\n",
       "\n",
       "/* Hlint styles */\n",
       ".suggestion-warning { \n",
       "    font-weight: bold;\n",
       "    color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "    font-weight: bold;\n",
       "    color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "    font-weight: bold;\n",
       "}\n",
       "</style> <div class=\"suggestion-name\" style=\"clear:both;\">Use concatMap</div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Found:</div>  <div class=\"highlight-code\" id=\"haskell\">concat (map labels ts)</div> </div>  <div class=\"suggestion-row\" style=\"float: left;\"> <div class=\"suggestion-error\">Why Not:</div>  <div class=\"highlight-code\" id=\"haskell\">concatMap labels ts</div> </div> "
      ],
      "text/plain": [
       "Line 2: Use concatMap\n",
       "Found:\n",
       "concat (map labels ts)\n",
       "Why not:\n",
       "concatMap labels ts"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[1,2,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "labcat :: [GenTree a] -> [a] -> [a]\n",
    "labcat ts xs = concat (map labels ts) ++ xs\n",
    "\n",
    "labcat [Node 1 [Node 2 [],Node 3 []]] []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    labcat (Node x us:vs) xs\n",
    "    = {definition}\n",
    "      concat (map labels (Node x us:vs)) ++ xs\n",
    "    = {definitions}\n",
    "      labels (Node x us) ++ concat (map labels vs) ++ xs\n",
    "    = {definiton}\n",
    "      x:concat (map labels us) ++ concat (map labels vs) ++ xs\n",
    "    = {definition of labcat}\n",
    "      x:concat (map labels us) ++ labcat vs xs\n",
    "    = {definition of labcat (again)}\n",
    "      x:labcat us (labcat vs xs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,2,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "labels' t = labcat' [t] []\n",
    "\n",
    "labcat' [] xs = xs\n",
    "labcat' (Node x us:vs) xs = x:labcat' us (labcat' vs xs)\n",
    "\n",
    "labcat' [Node 1 [Node 2 [],Node 3 []]] []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $T(labcat)(1,k,n) = \\Theta (n)$\n",
    "* $T(labcat)(h,k,n) = \\Theta (k^h n)$\n",
    "* tree size $s = k^h$\n",
    "\n",
    "따라서 $T(labels)(h,k) = T(labcat)(h,k,1) = \\Theta (s)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.6 Tupling\n",
    "\n",
    "# fibonacci\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib :: Int -> Integer\n",
    "fib 0 = 0\n",
    "fib 1 = 1\n",
    "fib n = fib (n-1) + fib (n-2)\n",
    "\n",
    "fib 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(fib)(n) = \\Theta (\\phi ^ n)$ 이며 golden ratio $\\phi = (1 + \\sqrt{5}) / 2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib' 0 = (0,1)\n",
    "fib' n = (b,a+b) where (a,b) = fib' (n-1)\n",
    "\n",
    "fst $ fib' 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "fib는 exponential time이나 fib'는 linear time임.\n",
    "\n",
    "## general law for tupling\n",
    "\n",
    "    (foldr f a xs, foldr g b xs) = foldr h (a,b) xs\n",
    "    h x (y,z) = (f x y, g x z)\n",
    "\n",
    "## leaf-labelled binary tree building"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data BinTree a = Leaf a | Fork (BinTree a) (BinTree a) deriving (Show)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "halve xs = (take m xs, drop m xs)\n",
    "           where m = length xs `div` 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fork (Leaf 1) (Fork (Leaf 2) (Leaf 3))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "build :: [a] -> BinTree a\n",
    "build [x] = Leaf x\n",
    "build xs = Fork (build ys) (build zs)\n",
    "           where (ys,zs) = halve xs\n",
    "\n",
    "build [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "halve는 xs에 대해서 총 3회 순회를 하도록 구현되어 있어서 비효율적임.\n",
    "$$ T(build)(n) = \\Theta(n \\log n)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fork (Leaf 1) (Fork (Leaf 2) (Leaf 3))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "build2 :: Int -> [a] -> (BinTree a,[a])\n",
    "build2 n xs = (build (take n xs), drop n xs)\n",
    "\n",
    "build' xs = fst (build2 (length xs) xs)\n",
    "\n",
    "build' [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "build2는 drop n xs 부분도 반환하여 tupling하도록 함"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Fork (Leaf 1) (Fork (Leaf 2) (Leaf 3)),[])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "build2 1 xs = (Leaf (head xs),tail xs)\n",
    "build2 n xs = (Fork (build (take m (take n xs)))\n",
    "                    (build (drop m (take n xs))),\n",
    "               drop n xs)\n",
    "              where m = n `div` 2\n",
    "\n",
    "build2 (length [1,2,3]) [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    take m . take n = take m\n",
    "    drop m . take n = take (n-m) . drop m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Fork (Leaf 1) (Fork (Leaf 2) (Leaf 3)),[])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "build2 1 xs = (Leaf (head xs),tail xs)\n",
    "build2 n xs = (Fork (build (take m xs))\n",
    "                    (build (take (n-m) (drop m xs))),\n",
    "               drop n xs)\n",
    "              where m = n `div` 2\n",
    "\n",
    "build2 (length [1,2,3]) [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "build2 1 xs = (Leaf (head xs),tail xs)\n",
    "build2 n xs = (Fork u v, drop n xs)\n",
    "              where (u,xs') = build2 m xs\n",
    "                    (v,xs'') = build2 (n-m) xs'\n",
    "                    m = n `div` 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    xs'' = drop  (n-m) xs'\n",
    "         = drop (n-m) (drop m xs)\n",
    "         = drop n xs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fork (Leaf 1) (Fork (Leaf 2) (Leaf 3))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "build2 1 xs = (Leaf (head xs),tail xs)\n",
    "build2 n xs = (Fork u v, xs'')\n",
    "              where (u,xs') = build2 m xs\n",
    "                    (v,xs'') = build2 (n-m) xs'\n",
    "                    m = n `div` 2\n",
    "                    \n",
    "fst $ build2 (length [1,2,3]) [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(build2)(1) = \\Theta (1)$\n",
    "\n",
    "$T(build2)(n) = T(build2)(m) + T(build2)(n-m) + \\Theta (1)$\n",
    "\n",
    "따라서 $T(build2)(n) = \\Theta (n)$ 임. logarithmic factor로 개선됨."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7.7 Sorting\n",
    "\n",
    "## Merge sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "merge :: (Ord a) => [a] -> [a] -> [a]\n",
    "merge [] ys = ys\n",
    "merge xs [] = xs\n",
    "merge xs'@(x:xs) ys'@(y:ys)\n",
    "      | x <= y    = x:merge xs ys'\n",
    "      | otherwise = y:merge xs' ys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "halve xs = (take m xs,drop m xs)\n",
    "           where m = length xs `div` 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "msort :: (Ord a) => [a] -> [a]\n",
    "msort [] = []\n",
    "msort [x] = [x]\n",
    "msort xs = merge (msort ys) (msort zs)\n",
    "           where (ys,zs) = halve xs\n",
    "\n",
    "msort [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1\\. take, drop을 splitAt으로 변경하여 순회를 줄인다. Prelude.splitAt은 아래와 같이 tupling을 이용하여 구현됨."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "splitAt :: Int -> [a] -> ([a],[a])\n",
    "splitAt 0 xs = ([],xs)\n",
    "splitAt n [] = ([],[])\n",
    "splitAt n (x:xs) = (x:ys,zs)\n",
    "                   where (ys,zs) = splitAt (n-1) xs\n",
    "\n",
    "halve xs = splitAt (length xs `div` 2) xs\n",
    "\n",
    "msort :: (Ord a) => [a] -> [a]\n",
    "msort [] = []\n",
    "msort [x] = [x]\n",
    "msort xs = merge (msort ys) (msort zs)\n",
    "           where (ys,zs) = halve xs\n",
    "\n",
    "msort [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2\\. 이전의 tree build와 유사하게 sort를 tupling 한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "msort2 0 xs = ([],xs)\n",
    "msort2 1 xs = ([head xs], tail xs)\n",
    "msort2 n xs = (merge ys zs, xs'')\n",
    "              where (ys,xs') = msort2 m xs\n",
    "                    (zs,xs'') = msort2 (n-m) xs'\n",
    "                    m = n `div` 2\n",
    "\n",
    "fst $ msort2 (length [10,8..1]) [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3\\. halve를 다른 방법으로 사람처럼 해봄"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([10,6,2],[8,4])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "halve2 [] = ([],[])\n",
    "halve2 [x] = ([x],[])\n",
    "halve2 (x:y:xs) = (x:ys,y:zs)\n",
    "                  where (ys,zs) = halve2 xs\n",
    "                  \n",
    "halve2 [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "위의 세 가지 방법들 모두 실행시간에 큰 차이를 만들지는 않는다. GHCi에서 위 세 가지 개선보다 컴파일을 하는 것이 훨씬 큰 성능향상을 만든다.\n",
    "\n",
    "logarithmic factor로 개선이면 큰 차이가 아닌가?\n",
    "\n",
    "## Quicksort\n",
    "\n",
    "haskell의 expression power를 보여주는 예로 자주 사용되는 quicksort 구현이나 매우 비효율적임."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "qsort :: (Ord a) => [a] -> [a]\n",
    "qsort [] = []\n",
    "qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++\n",
    "               qsort [y | y <- xs, x <= y]\n",
    "\n",
    "qsort [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$T(qsort)(n+1) = max [ T(qsort)(k) + T(qsort)(n-k) | k \\leftarrow[0..n]] + \\Theta (n)$$\n",
    "\n",
    "quicksort의 특징은\n",
    "\n",
    "* 최악의 경우 $\\Theta (n^2)$, 평균적으로 $\\Theta (n \\log n)$의 시간 복잡도를 가짐\n",
    "* list가 아닌 array로 주로 구현하며, 추가 space를 사용하지 않고 구현 가능\n",
    "\n",
    "function programming dptjsms $\\Theta (n \\log n)$ 에서 상수가 작지 않으므로 quick sort보다 다른 방법을 선호함\n",
    "\n",
    "우선, partitioning에서 2번의 순회를 줄이기 위해서 아래 partition함수를 만들고 foldr로 tupling하여 최적화함"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- partition p xs = (filter p xs, filter (not . p) xs)\n",
    "partition p = foldr op ([],[])\n",
    "              where op x (ys,zs) | p x = (x:ys,zs)\n",
    "                                 | otherwise = (ys,x:zs)\n",
    "\n",
    "qsort' [] = []\n",
    "qsort' (x:xs) = qsort' ys ++ [x] ++ qsort' zs\n",
    "                where (ys,zs) = partition (<x) xs\n",
    "\n",
    "qsort' [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "위 코드는 아직 space leak이 존재함"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sort (x:xs) = sort (fst p) ++ [x] ++ sort (snd p)\n",
    "              where p = partition (<x) xs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "위 코드에서 sort (fst p)가 완료되어도 sort (snd p)로 인하여 p 전체가 유지됨. (destructng한다고 실제 나눠지는 것은 아닌가?)\n",
    "이로 인하여 최악의 경우 $\\Theta (n^2)$의 space가 필요해짐.\n",
    "\n",
    "2개의 accumulating parameter를 사용하여 이를 분리함."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sortp x [] us vs = sort2 us ++ [x] ++ sort2 vs\n",
    "sortp x xs us vs = sort2 (us ++ ys) ++ [x] ++\n",
    "                   sort2 (vs ++ zs)\n",
    "                   where (ys,zs) = partition (<x) xs\n",
    "                   \n",
    "sort2 [] = []\n",
    "sort2 (x:xs) = sortp x xs [] []\n",
    "\n",
    "sort2 [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "sortp를 sort의 local로 만들고 정리하여 최종판"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6,8,10]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sort3 [] = []\n",
    "sort3 (x:xs) = sortp xs [] []\n",
    "               where sortp [] us vs = sort3 us ++ [x] ++ sort3 vs\n",
    "                     sortp (y:xs) us vs = if y < x\n",
    "                                          then sortp xs (y:us) vs\n",
    "                                          else sortp xs us (y:vs)\n",
    "\n",
    "sort3 [10,8..1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Conclusion\n",
    "\n",
    "* **lazy evaluation은 필요할 때만 사용하고, eager evaluation을 활용한다.**\n",
    "* **evaluation result의 binding을 인지하고, let/where를 사용해서 중복을 제거한다.**\n",
    "* **accumulator나 tupling을 사용한다.**\n",
    "* **binding과 reference를 정확히 파악하여 space leak을 제거한다.**\n",
    "* destructuring을 한다고 tuple의 값이 완전히 분리되는 것은 아니다.\n",
    "\n",
    "다른 언어도 공통인 것.\n",
    "\n",
    "* **알고리즘**\n",
    "* **인터프리터보다 컴파일러**\n",
    "* **프로파일링**\n",
    "\n",
    "functional programming에서 performance와 efficiency에 그 동안 궁금했던 것들을 조금은 해결할 수 있었다. 그러나 알면 알수록 functional programming으로 좋은 코드를 작성하는 것이 쉽지 않다는 생각이 든다.\n",
    "\n",
    "\n",
    "# Reference\n",
    "\n",
    "* Profiling\n",
    " * https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/profiling.html\n",
    " * http://book.realworldhaskell.org/read/profiling-and-optimization.html\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}