solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# First part: Weave insert first list into second\n",
    "\n",
    "### usage\n",
    "```\n",
    "weave [11,12] [0,1,2,3]\n",
    "```\n",
    "\n",
    "### output\n",
    "```\n",
    "[0,11,1,12,2,11,3]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**What we want to do here** is interleave the first list into the second, until the _second_ one runs out. Well, the runtime `zip` function says it will, given 2 lists as input, return a list of the corresponding pair, with the first element of the pair being from the first list. Well, we want it the other way around and, even though we could simply invert the order when feeding them to the function, we'll use `zipWith` with our own function just to keep the input intact. So let's try the following:\n",
    "\n",
    "## Function: `weave`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0,11],[1,12],[2,11],[3,12]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "la = [11,12]\n",
    "lb = [0,1,2,3]\n",
    "zipWith (\\x y -> [y, x]) (cycle la) lb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just to clarify, we `cycle` the first list to make sure we stop just after the end of the second one. So, that gave us something good to start with. First of all, we don't want the pairs organized into sublists of their own, so we can `concat` that:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0,11,1,12,2,11,3,12]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concat $ zipWith (\\x y -> [y, x]) (cycle la) lb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool, we're almost there. We just need to get rid of the trailing element which shouldn't be there; remember that the head and last elements of the second list must enclose the resulting list. So we can just pick the `init` of the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0,11,1,12,2,11,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "init $ concat $ zipWith (\\x y -> [y, x]) (cycle la) lb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Got'em. So our only function effectively becomes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "weave a b = init $ concat $ zipWith (\\x y -> [y, x]) (cycle a) b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looks elegant. We use it like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0,11,1,12,2,11,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "weave la lb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Different inputs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"[a]\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "weave \"abcd\" \"[]\" -- first longer than the second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"(2+3)\",\"*\",\"(4-5)\",\"*\",\"(3+7)\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "weave [\"*\"] [\"(2+3)\", \"(4-5)\", \"(3+7)\"] -- second longer than the first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"(2+3)*(4-5)*(3+7)\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concat $ weave [\"*\"] [\"(2+3)\", \"(4-5)\", \"(3+7)\"] -- same thing, more readable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Second part: Bracket insert first list into second\n",
    "\n",
    "### usage\n",
    "```\n",
    "bracket \"abc\" \"()\"\n",
    "```\n",
    "\n",
    "### output\n",
    "```\n",
    "[\"(a)\", \"(b)\", \"(c)\"]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**We can already see** that a simple `zip` won't do. But we _do_ know that a tuple is one thing and a list of tuples is still a list of those one things... If you didn't get the hint, just bear with me for a moment. Let's first try to generate a list of tuples containing pairs of element from a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "let { zipPairs [xa, xb]   = [(xa, xb)];\n",
    "        zipPairs (xa:xb:xs) = (xa, xb):zipPairs xs }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remember that `[xa, xb]` is just syntax candy for `xa:xb:[]`. Let's try it out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('(',')'),('[',']')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "zipPairs \"()[]\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Awesome.\n",
    "\n",
    "**Yes**, it'll have to be an even number of elements, but that's a natural implication. We'll assume the input will respect these guidelines, there's no need for robustness here. Notice that now, having a list of tuples, we can, again, capitalize on the functionality of `zipWith`, with a lil' modification to our lambda function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"(a)\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "lx = \"abc\"\n",
    "ly = \"()\"\n",
    "zipWith (\\x (ya, yb) -> [ya, x, yb]) lx (zipPairs ly)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmm, close. It looks like we're a few elements short. The reason why we didn't simply `cycle` the first list is that the function must run until _both_ lists exhaust. That means that if the first is bigger than the half of the second, we cycle the first until we end the second and vice-versa. This is somewhat simple, but we need to know which list is bigger to do the right thing. A little `if&else` will do the trick:\n",
    "\n",
    "## Function: `bracket`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bracket a b = if length a >= (length b `div` 2) then\n",
    "                            zipWith (\\x (ya, yb) -> [ya, x, yb]) a (cycle (zipPairs b))\n",
    "                        else\n",
    "                            zipWith (\\x (ya, yb) -> [ya, x, yb]) (cycle a) (zipPairs b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's give it a go:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"(a)\",\"(b)\",\"(c)\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bracket lx ly"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beautiful. Let's try a few variations of inputs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"(a)\",\"(b)\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bracket \"ab\" \"()\" -- both lists the same size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"1+2\",\"3-4\",\"5+6\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bracket \"+-\" \"123456\" -- second longer than first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[\"(\",\"2+3\",\")\"],[\"(\",\"4-5\",\")\"],[\"(\",\"6+7\",\")\"]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "bracket [\"2+3\", \"4-5\", \"6+7\"] [\"(\", \")\"] -- fisrt longer than second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"(2+3)(4-5)(6+7)\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concatMap concat $ bracket [\"2+3\", \"4-5\", \"6+7\"] [\"(\", \")\"] -- same thing, more readable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## e l e g a n c e\n",
    "\n",
    "This oughta' do the trick! Plus, the complete program, with a few checks for blank inputs (which we didn't include here)  is about 8~10 lines long. If you found this hard to follow, you should check out [lambdas](http://learnyouahaskell.com/higher-order-functions#lambdas) and [function application](http://learnyouahaskell.com/higher-order-functions#function-application). The [list functions library](https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-List.html) documents all the functions used here, if you felt unsure at some point."
   ]
  }
 ],
 "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
}