{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import Prelude hiding (foldr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "함수형 언어는 '고차 함수'와 '지연 연산' 이라는 강력한 모듈화 도구를 제공해준다.\n",
    "이 둘은 glue 역할을 하여 새로운 형태의 모듈화를 가능하게 한다.\n",
    "\n",
    "어떻게 glue 역할을 하는지 살펴보자."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 함수 수준에서의 glue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 리스트 예제"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data List a = Nil | Cons a (List a) deriving (Show, Eq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "타입변수(`a`)로 정의된 리스트 타입이다. 단일연결리스트(singly linked list)이며, 빈 경우(`Nil`)와 머리-꼬리를 나타내는 `Cons` 중 하나(`|`)라는 의미이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nil"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Nil -- []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cons 1 (Cons 2 (Cons 3 Nil))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Cons 1 (Cons 2 (Cons 3 Nil)) -- [1, 2, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "리스트 요소들의 합을 구하는 함수 `sum`는 각각의 경우에 대해 정의되어야 한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sum Nil = 0\n",
    "sum (Cons num rest) = num + sum rest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "빈 리스트의 합은 0이고, `Cons`의 경우에는 머리(`num`)를 나머지 합(`sum rest`)에 더하면 된다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sum (Cons 1 (Cons 2 (Cons 3 Nil)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "이 정의에서 `0`과 `+`만 빼면 리스트 요소들로 무언가를 할 수 있는 재사용 가능한 패턴이 만들어진다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sum = foldr (+) 0\n",
    "\n",
    "(foldr f x) Nil = x\n",
    "(foldr f x) (Cons a l) = f a ((foldr f x) l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sum (Cons 1 (Cons 2 (Cons 3 Nil)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "하스켈에서 리스트는 이미 정의되어 있으며 `Nil`은 `[]`, `Cons`는 `(:)`를 사용할 수 있다. 이제부터는 하스켈의 리스트를 직접 이용한다. (`sum`과 `foldr`도 이미 정의되어 있지만, 이건 이 글에서 설명하려는 내용이니 재정의하겠다.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "foldr f x [] = x\n",
    "foldr f x (a:as) = f a (foldr f x as)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`((foldr f x) as)`나 `(foldr f x as)`는 같다. 하스켈에서는 함수에 인자를 하나씩 적용하며, 인자가 2개 필요한 함수에 하나만 적용하면 그 결과는 인자를 하나 필요로 하는 함수가 된다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`sum`을 `foldr`, `(+)`, `0`의 결합으로 표현하는 과정에서 `foldr`이라는 부산물이 나왔는데, 이는 다양하게 활용된다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sum = foldr (+) 0\n",
    "product = foldr (*) 1      -- 리스트 요소 곱\n",
    "anytrue = foldr (||) False -- 리스트 요소 중 True가 있나?\n",
    "alltrue = foldr (&&) True  -- 리스트 요소 중 False가 있나?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`foldr f x`는 `Cons`를 `f`로, `Nil`을 `x`로 대체하는 것. `Cons a (Cons b Nil)`은 `f a (f b x)`와 같다. 따라서 `foldr (:) []`는 원래의 리스트를 그대로 복사하는 함수가 된다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "원래의 리스트 요소들에 모두 2를 곱하는 함수 `doubleall`을 정의해보자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "doubleall = foldr f []\n",
    "             where f a x = (a*2) : x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "그런데...\n",
    "\n",
    "```haskell\n",
    "f a x = (a*2) : x\n",
    "f a x = (:) (a*2) x\n",
    "f a   = (:) (a*2)\n",
    "f a   = (:) ((*2) a)\n",
    "f a   = ((:) . (*2)) a\n",
    "f     = (:).(*2)\n",
    "```\n",
    "여기서 `(.)`는 함수 합성 연산자. `(f . g) x = f (g x)`이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "doubleall = foldr ((:).(*2)) []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "doubleall [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`sum`에서 `(+)`과 `0`을 추출하여 일반화한 것처럼, `doubleall`에서도 곱하기 2 부분(`(*2)`)만 추출하여 일반화하면 `map`이란 함수를 얻을 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "doubleall = map (*2)\n",
    "map f = foldr ((:).f) []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2,4,6]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "doubleall [1,2,3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "행렬 요소들의 합을 구하는 함수를 보자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "summatrix = sum . map sum\n",
    "summatrix [[1,2,3],\n",
    "           [4,5,6],\n",
    "           [7,8,9]]   -- 행렬을 리스트의 리스트로 표현."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "하스켈에는 이미 `foldr`과 `map`이 정의되어 있다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 트리 예제"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "여기서 다룰 트리 예제는 자식을 여럿 가질 수 있는 트리다. 각 노드에는 `a`값의 레이블이 있고, 자식 트리는 리스트로 표현된다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data Tree a = Node a [Tree a] deriving (Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "다음의 트리는 ..\n",
    "\n",
    "![](tree.svg)\n",
    "\n",
    "아래의 코드로 표현된다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "t1 = Node 1 \n",
    "         [Node 2\n",
    "               [],\n",
    "          Node 3\n",
    "               [Node 4\n",
    "                     []]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "트리에 대해서도 리스트의 `foldr`과 `map`에 해당하는 함수들을 만들어 볼 수 있다. 리스트에서는 `sum` 함수에서부터 일반화하는 방향으로 출발했지만 이번에는 `foldr`을 참고하여 바로 만들어보겠다.\n",
    "\n",
    "`foldr`이 `Nil`과 `Cons`에 대해 각각 대체 값을 인자로 받은 것과 마찬가지로 `foldtree`는 `Node`와 `Nil`과 `Cons`을 대체하는 인자가 3개 필요하다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "foldtree f g a (Node label subtrees)= f label (foldr g a (map (foldtree f g a) subtrees))\n",
    "maptree f = foldtree (Node . f) (:) []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "이 함수들을 이용하면 리스트에서와 마찬가지로 트리를 처리하는 함수를 쉽게 만들 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sumtree = foldtree (+) (+) 0\n",
    "labels = foldtree (:) (++) []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sumtree t1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,2,3,4]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "labels t1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "어떤 데이터 타입을 만들더라도 `foldr`이나 `foldtree`와 같은 '고차 함수'를 만들면 쉽게 새로운 함수를 만들어낼 수 있다."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "version": "7.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}