{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 函数式编程中的数据结构\n",
    "在函数式编程中，往往大量使用一些核心的数据结构和算法。相比于面向对象编程利用代码复用来减少冗余，函数式编程更倾向于编写简洁易复用的代码，因为语言将重点放在使用核心数据结构和算法实现业务逻辑上。\n",
    "\n",
    "函数式语言中每种集合类型都支持同一批无副作用的高阶函数，称为组合器（combinator），如map、filter、fold等。一旦你了解了这些组合器，你就可以根据自身对数据访问的需求及性能要求，选用合适的集合类型，用同样的组合器函数去操作数据。在所有的软件开发工作中，这些集合类型是代码复用与组合的最有效工具。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 1 序列\n",
    "序列的元素时可以按特定的顺序访问的，scala.collection.Seq是一个trait，是所有可变或不可变序列类型的抽象，其子trait对应scala.collection.mutable.Seq和scala.collection.immutable.Seq。\n",
    "\n",
    "**推荐将Seq作为序列型数据结构的参数或作为返回值，因为这样，Seq的任何子类型都可以使用。**Seq使用+:方法来构造新的序列，使用++连接两个序列。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mseq1\u001b[0m: \u001b[32mSeq\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"Programming\"\u001b[0m, \u001b[32m\"Scala\"\u001b[0m)\n",
       "\u001b[36mseq2\u001b[0m: \u001b[32mSeq\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"People\"\u001b[0m, \u001b[32m\"should\"\u001b[0m, \u001b[32m\"read\"\u001b[0m)\n",
       "\u001b[36mseq3\u001b[0m: \u001b[32mSeq\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\n",
       "  \u001b[32m\"People\"\u001b[0m,\n",
       "  \u001b[32m\"should\"\u001b[0m,\n",
       "  \u001b[32m\"read\"\u001b[0m,\n",
       "  \u001b[32m\"Programming\"\u001b[0m,\n",
       "  \u001b[32m\"Scala\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val seq1 = Seq(\"Programming\", \"Scala\")\n",
    "val seq2 = \"People\" +: \"should\" +: \"read\" +: Seq.empty\n",
    "val seq3 = seq2 ++ seq1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以考虑用immutable.Vector代替List，因为不可变Vector的所有操作都是O(1)，而List对于那些需要访问头部以外元素的操作，都需要O(n)操作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**有关预定义的讨论**\n",
    "\n",
    "为了鼓励程序员使用不可变的集合类型，Predef在暴露不可变集合类型时，不需要显示导入或使用全路径导入。但是Predef还将scala.collection.Seq导入到了当前作用域，该类型是可变集合类型和不可变集合类型共同的抽象特质，这使得传入的Seq类型实例可能是可变的，所以线程是不安全的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 运用包对象为Seq定义别名，覆盖原有别名定义\n",
    "为了使用scala.collection.immutable.Seq代替默认的scala.collection.Seq，使用包对象来解决：\n",
    "``` scala\n",
    "package fp\n",
    "package object datastructs {\n",
    "  type Seq[+A] = scala.collection.immutable.Seq[A]\n",
    "  val Seq = scala.collection.immutable.Seq\n",
    "}\n",
    "```\n",
    "package关键字也是包对象定义的一部分，在一个包中只能有一个包对象。最后，该文件的路径是src/main/scala/fp/datastructs/package.scala，这是一种常用的命名习惯。\n",
    "\n",
    "在包对象中，我们声明了**一个类型别名和一个val变量**。类型声明导入之后，使用Seq声明一个实例时，就需要使用scala.collection.immutable.Seq；val Seq的声明语句**将伴随对象引入作用域**，于是类似Seq(1,2,3,4)的语句就会触发scala.collection.immutable.Seq.apply方法的调用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 映射表\n",
    "映射表用来存储键值对，但不应将其余很多数据结构的map方法混淆。映射表与map方法有一定程度的相似，前者每个键都对应一个值，后者每个输入元素都产生一个输出元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mstateCapitals\u001b[0m: \u001b[32mMap\u001b[0m[\u001b[32mString\u001b[0m, \u001b[32mString\u001b[0m] = \u001b[33mMap\u001b[0m(\n",
       "  \u001b[32m\"Alabama\"\u001b[0m -> \u001b[32m\"Montgomery\"\u001b[0m,\n",
       "  \u001b[32m\"Alaska\"\u001b[0m -> \u001b[32m\"Juneau\"\u001b[0m,\n",
       "  \u001b[32m\"Wyoming\"\u001b[0m -> \u001b[32m\"Cheyenne\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val stateCapitals = Map(\n",
    "    \"Alabama\" -> \"Montgomery\",\n",
    "    \"Alaska\" -> \"Juneau\",\n",
    "    \"Wyoming\" -> \"Cheyenne\"\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mlengths\u001b[0m: \u001b[32mMap\u001b[0m[\u001b[32mString\u001b[0m, \u001b[32mInt\u001b[0m] = \u001b[33mMap\u001b[0m(\n",
       "  \u001b[32m\"Alabama\"\u001b[0m -> \u001b[32m10\u001b[0m,\n",
       "  \u001b[32m\"Alaska\"\u001b[0m -> \u001b[32m6\u001b[0m,\n",
       "  \u001b[32m\"Wyoming\"\u001b[0m -> \u001b[32m8\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val lengths = stateCapitals map {\n",
    "    kv => (kv._1, kv._2.length)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mcaps\u001b[0m: \u001b[32mMap\u001b[0m[\u001b[32mString\u001b[0m, \u001b[32mString\u001b[0m] = \u001b[33mMap\u001b[0m(\n",
       "  \u001b[32m\"Alabama\"\u001b[0m -> \u001b[32m\"MONTGOMERY\"\u001b[0m,\n",
       "  \u001b[32m\"Alaska\"\u001b[0m -> \u001b[32m\"JUNEAU\"\u001b[0m,\n",
       "  \u001b[32m\"Wyoming\"\u001b[0m -> \u001b[32m\"CHEYENNE\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val caps = stateCapitals map {\n",
    "    case (k, v) => (k, v.toUpperCase)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mstateCapitals2\u001b[0m: \u001b[32mMap\u001b[0m[\u001b[32mString\u001b[0m, \u001b[32mString\u001b[0m] = \u001b[33mMap\u001b[0m(\n",
       "  \u001b[32m\"Alabama\"\u001b[0m -> \u001b[32m\"Montgomery\"\u001b[0m,\n",
       "  \u001b[32m\"Alaska\"\u001b[0m -> \u001b[32m\"Juneau\"\u001b[0m,\n",
       "  \u001b[32m\"Wyoming\"\u001b[0m -> \u001b[32m\"Cheyenne\"\u001b[0m,\n",
       "  \u001b[32m\"Virginia\"\u001b[0m -> \u001b[32m\"Richmond\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val stateCapitals2 = stateCapitals + (\"Virginia\" -> \"Richmond\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "key -> value的语法形式实际上用库中的隐式转换实现的，实际调用了Map.apply方法。Map.apply方法的参数为一个两元素的元组（键值对）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 集合\n",
    "集合是无序集合类型的一个例子，所以集合不是序列。集合要求元素具有唯一性。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mstates\u001b[0m: \u001b[32mSet\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mSet\u001b[0m(\u001b[32m\"Alabama\"\u001b[0m, \u001b[32m\"Alaska\"\u001b[0m, \u001b[32m\"Wyoming\"\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val states = Set(\"Alabama\", \"Alaska\", \"Wyoming\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mlengths\u001b[0m: \u001b[32mSet\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mSet\u001b[0m(\u001b[32m7\u001b[0m, \u001b[32m6\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val lengths = states map (st => st.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mstates2\u001b[0m: \u001b[32mSet\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mSet\u001b[0m(\n",
       "  \u001b[32m\"Alaska\"\u001b[0m,\n",
       "  \u001b[32m\"Alabama\"\u001b[0m,\n",
       "  \u001b[32m\"New York\"\u001b[0m,\n",
       "  \u001b[32m\"Illinois\"\u001b[0m,\n",
       "  \u001b[32m\"Wyoming\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val states2 = states + (\"New York\", \"Illinois\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala 2.11",
   "language": "scala211",
   "name": "scala211"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "pygments_lexer": "scala",
   "version": "2.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}