{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Seasoned Schemer\n",
    "\n",
    "## 11. Welcome Back to the Show"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    ";; 回忆member?函数\n",
    "(define member?\n",
    "  (lambda (a lat) \n",
    "    (cond\n",
    "     [(null? lat) #f]\n",
    "     [else \n",
    "       (or (eq? a (car lat))\n",
    "           (member? a (cdr lat)))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(member? 'a '(c d b a f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    ";; 定义two-in-a-row?, 一行中连续两个元素\n",
    "(define is-first?\n",
    "  (lambda (a lat)\n",
    "    (cond\n",
    "     [(null? lat) #f]\n",
    "     [else (eq? a (car lat))])))\n",
    "\n",
    "(define two-in-a-row?\n",
    "  (lambda (lat)\n",
    "    (cond\n",
    "     [(null? lat) #f]\n",
    "     [else\n",
    "      (or (is-first? (car lat) (cdr lat))\n",
    "          (two-in-a-row? (cdr lat)))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(two-in-a-row? '(italian sardines sardines spaghetti parsley))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    ";; 计算前缀和\n",
    "(define sum-of-prefixes-b\n",
    "  (lambda (sonssf tup)\n",
    "    (cond\n",
    "     [(null? tup) '()]\n",
    "     [else\n",
    "      (cons (+ sonssf (car tup))\n",
    "            (sum-of-prefixes-b \n",
    "             (+ sonssf (car tup))\n",
    "             (cdr tup)))])))\n",
    "\n",
    "(define sum-of-prefixes\n",
    "  (lambda (tup)\n",
    "    (sum-of-prefixes-b 0 tup)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 5)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(sum-of-prefixes '(1 1 1 1 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Use additional arguments when a function needs to known what other arguments to the function have been like so far.\n",
    "\n",
    "The function `scramble` takes a non-empty tup in which no number is greater than its own index, and returns a tup of the same "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    ";; pick函数\n",
    "(define pick\n",
    "  (lambda (n xs)\n",
    "    (cond \n",
    "     [(= n 1) (car xs)]\n",
    "     [else (pick (- n 1) (cdr xs))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(pick 3 '(1 2 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    ";; rev-pre: reversed prefix\n",
    "(define scramble-b\n",
    "  (lambda (tup rev-pre)\n",
    "    (cond\n",
    "     [(null? tup) '()]\n",
    "     [else \n",
    "      (cons (pick (car tup)\n",
    "                  (cons (car tup) rev-pre))\n",
    "            (scramble-b (cdr tup)\n",
    "                        (cons (car tup) rev-pre)))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 1 1 1 1 4 1 1 1 9)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(scramble-b '(1 1 1 3 4 2 1 1 9 2) '())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define scramble \n",
    "  (lambda (tup)\n",
    "    (scramble-b tup '())))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 1 1 1 1 4 1 1 1 9)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(scramble '(1 1 1 3 4 2 1 1 9 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 12. Take Cover\n",
    "\n",
    "```scheme\n",
    "> (multirember 'tuna '(shrimp salad tuna salad and tuna))\n",
    "(shrimp salad saladd and)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember\n",
    "  (lambda (a tup)\n",
    "    (cond\n",
    "     [(null? tup) '()]\n",
    "     [else \n",
    "      (cond\n",
    "       [(eq? a (car tup)) (multirember a (cdr tup))]\n",
    "       [else (cons (car tup) (multirember a (cdr tup)))])])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(shrimp salad salad and)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember 'tuna '(shrimp salad tuna salad and tuna))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define Y\n",
    "  (lambda (X)\n",
    "    ((lambda (p)\n",
    "       (X (lambda (arg) ((p p) arg))))\n",
    "     (lambda (p)\n",
    "       (X (lambda (arg) ((p p) arg)))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember1\n",
    "  (lambda (a tup)\n",
    "    ((Y (lambda (mr)\n",
    "          (lambda (tup)\n",
    "            (cond\n",
    "             [(null? tup) '()]\n",
    "             [(eq? a (car tup)) (mr (cdr tup))]\n",
    "             [else \n",
    "              (cons (car tup)\n",
    "                    (mr (cdr tup)))]))))\n",
    "     tup)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(shrimp salad salad and)"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember1 'tuna '(shrimp salad tuna salad and tuna))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "利用`Y`组合子,避免了命名的递归."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember2\n",
    "  (lambda (a tup)\n",
    "    ((letrec \n",
    "       ((mr (lambda (tup)\n",
    "              (cond \n",
    "               [(null? tup) '()]\n",
    "               [(eq? a (car tup)) (mr (cdr tup))]\n",
    "               [else \n",
    "                (cons (car tup)\n",
    "                      (mr (cdr tup)))]))))\n",
    "        mr)\n",
    "     tup)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(shrimp salad salad and)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember2 'tuna '(shrimp salad tuna salad and tuna))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`letrec`表达式`((letrec ((mr ...)) mr) tup)`的值, 就是函数`mr`应用到`tup`的值. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember-f\n",
    "  (lambda (test?)\n",
    "    (letrec \n",
    "        ((mr \n",
    "          (lambda (a tup) \n",
    "            (cond\n",
    "              [(null? tup) '()]\n",
    "              [(test? a (car tup)) (mr a (cdr tup))]\n",
    "              [else\n",
    "               (cons (car tup)\n",
    "                     (mr a (cdr tup)))]))))\n",
    "      mr)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(shrimp salad salad and)"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((multirember-f eq?) 'tuna '(shrimp salad tuna salad and tuna))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember3\n",
    "  (letrec \n",
    "      ((mr \n",
    "        (lambda (a tup) \n",
    "          (cond\n",
    "            [(null? tup) '()]\n",
    "            [(test? a (car tup)) (mr a (cdr tup))]\n",
    "            [else\n",
    "             (cons (car tup)\n",
    "                   (mr a (cdr tup)))]))))\n",
    "    mr))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观察`multirember3`的结构, 区分`(letrec ...)`和`(define ...)`定义递归函数的异同.\n",
    "\n",
    "12th commandment\n",
    "\n",
    "> 使用`letrec`移除不变化的参数.\n",
    "\n",
    "13th commandment\n",
    "\n",
    "> 使用`letrec`来隐藏/保护函数.一种抽象的手段\n",
    "\n",
    "```scheme\n",
    "(letrec \n",
    "  ((U (...))\n",
    "   (member? (...)))\n",
    "  (body))\n",
    "   \n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define union\n",
    "  (lambda (s1 s2)\n",
    "    (letrec\n",
    "      ((U (lambda (set)\n",
    "            (cond\n",
    "             [(null? set) s2]\n",
    "             [(M? (car set) s2)\n",
    "              (U (cdr set))]\n",
    "             [else\n",
    "              (cons (car set)\n",
    "                    (U (cdr set)))])))\n",
    "       (M? (lambda (a lat)\n",
    "             (cond\n",
    "              [(null? lat) #f]\n",
    "              [(eq? a (car lat)) #t]\n",
    "              [else\n",
    "               (M? a (cdr lat))]))))\n",
    "      (U s1))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(tomatos casserole macaroni and cheese)"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(union '(tomatos and macaroni casserole) '(macaroni and cheese))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 13. Hop,Skip, and Jump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`intersect`函数.\n",
    "\n",
    "`intersectall`函数.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define intersect0\n",
    "  (lambda (s1 s2)\n",
    "    (cond \n",
    "     [(null? s1) '()]\n",
    "     [(member? (car s1) s2)\n",
    "      (cons (car s1)\n",
    "            (intersect0 (cdr s1) s2))]\n",
    "     [else\n",
    "      (intersect0 (cdr s1) s2)])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(and macaroni)"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersect0 '(tomatoes and macaroni) '(macaroni and cheese))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define intersect1\n",
    "  (lambda (s1 s2)\n",
    "    (letrec\n",
    "      ((I (lambda (s)\n",
    "            (cond\n",
    "             [(null? s) '()]\n",
    "             [(member? (car s) s2)\n",
    "              (cons (car s)\n",
    "                    (I (cdr s)))]\n",
    "             [else\n",
    "              (I (cdr s))]))))\n",
    "      (I s1))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(and macaroni)"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersect1 '(tomatoes and macaroni) '(macaroni and cheese))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define intersectall0\n",
    "  (lambda (lset)\n",
    "    (cond\n",
    "     [(null? lset) '()]\n",
    "     [(null? (cdr lset)) (car lset)]\n",
    "     [else\n",
    "      (intersect0 (car lset) \n",
    "                  (intersectall0 (cdr lset)))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a)"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersectall0 '((a b c) (a c d) (a e f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define intersectall1\n",
    "  (lambda (lset)\n",
    "    (letrec \n",
    "      ((A (lambda (lset)\n",
    "            (cond\n",
    "             [(null? (cdr lset)) (car lset)]\n",
    "             [else\n",
    "              (intersect0 (car lset)\n",
    "                          (A (cdr lset)))]))))\n",
    "      (cond\n",
    "       [(null? lset) '()]\n",
    "       [else (A lset)]))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a)"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersectall1 '((a b c) (a c d) (a e f)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "添加一个优化, 当`lset`包含空集合时,直接返回`'()`.\n",
    "\n",
    "`letcc`不支持.\n",
    "\n",
    "14th commandment\n",
    "\n",
    "> use (letcc ...) to return values abruptly and promptly.\n",
    "\n",
    "\n",
    "使用`call/cc`做跳转.\n",
    "\n",
    "`(rember-upto-last a lat)`从最后一次出现的位置截取,如果没有找到,返回全集. 有一定难度."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define intersectall2\n",
    "  (lambda (lset)\n",
    "    (call/cc\n",
    "     (lambda (hop)\n",
    "       (letrec\n",
    "         ((A (lambda (lset)\n",
    "               (cond\n",
    "                [(null? (car lset)) (hop '())]\n",
    "                [(null? (cdr lset)) (car lset)]\n",
    "                [else \n",
    "                 (intersect0 (car lset)\n",
    "                             (A (cdr lset)))]))))\n",
    "         (cond\n",
    "          [(null? lset) '()]\n",
    "          [else (A lset)]))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a)"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersectall2 '((a b c) (a c d) (a e f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersectall2 '((a b c) () (a e f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define rember-upto-last\n",
    "  (lambda (a lat)\n",
    "    (call/cc\n",
    "     (lambda (hop)\n",
    "       (letrec\n",
    "         ((R (lambda (lat)\n",
    "               (cond \n",
    "                [(null? lat) '()]\n",
    "                [(eq? (car lat) a) \n",
    "                 (hop (R (cdr lat)))]\n",
    "                [else\n",
    "                 (cons (car lat)\n",
    "                       (R (cdr lat)))]))))\n",
    "         (R lat))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(g k l)"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember-upto-last 'a '(a b c d e a g k l))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 14. Let There Be Names"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(rember1* a l)`移除`l`中出现的第一个`a`, 然后返回.\n",
    "\n",
    "使用`equal?`代替`eqlist?`.\n",
    "\n",
    "15th commandment\n",
    "\n",
    "> use (let ...) to name the values of repeated expressions in a function definition if they may be evaluated twice for one and the same use of the function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define rember1* \n",
    "  (lambda (a l)\n",
    "    (letrec \n",
    "      ((R (lambda (l)\n",
    "            (cond\n",
    "             [(null? l) '()]\n",
    "             [(atom? (car l)) \n",
    "              (cond\n",
    "               [(eq? (car l) a) (cdr l)]\n",
    "               [else \n",
    "                (cons (car l)\n",
    "                      (R (cdr l)))])]\n",
    "             [else\n",
    "              (cond\n",
    "               [(equal? (R (car l)) (car l))\n",
    "                (cons (car l) (R (cdr l)))]\n",
    "               [else \n",
    "                (cons (R (car l)) (cdr l))])]))))\n",
    "      (R l))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((pasta) pasta (noodles meat sauce) meat tomatoes)"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember1* 'meat '((pasta meat) pasta (noodles meat sauce) meat tomatoes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(equal? '(1 2 3) '(1 2 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 15. The Difference Between Men and Boys ... "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(define)`和`(set! )`区别,求值环境相关."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Scheme 3",
   "language": "scheme",
   "name": "calysto_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}