Thinking functionally with haskell Ch. 1

think.functionally.ch1.ipynb

{
 "metadata": {
  "language": "haskell",
  "signature": "sha256:ad4158bb5d12e61354af8d2cb0dbcbb921a8bb27ef163c818f19bdeab47236a0"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "-- imports\n",
      "import qualified Data.Char as Char\n",
      "import qualified Data.List as List"
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "# Chapter 1 What is functional programming?\n",
      "In a nutshell:\n",
      "\n",
      " * Functional programming is a method of program construction that emphasises functions and their application rather than commands and their execution.\n",
      " * Functional programming uses simple mathematical notation that allows prob- lems to be described clearly and concisely.\n",
      " * Functional programming has a simple mathematical basis that supports equa- tional reasoning about the properties of programs.\n",
      "\n",
      "## Example: common words\n",
      "\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "type Text = [Char]\n",
      "type Word = [Char]\n",
      "\n",
      "-- map :: (a->b) -> [a] -> [b] from Prelude\n",
      "-- toLower :: Char -> Char from Data.Char\n",
      "-- map toLower :: Text -> Text\n",
      "\n",
      "sortWords :: [Word] -> [Word]\n",
      "sortWords = List.sort\n",
      "\n",
      "countRuns :: [Word] -> [(Int,Word)]\n",
      "countRuns [] = []\n",
      "countRuns (x:xs) = (hl, x) : countRuns t\n",
      "                   where hl = 1 + (length . takeWhile (\\v -> x==v)) xs\n",
      "                         t = dropWhile (\\v -> x==v) xs\n",
      "                         \n",
      "sortRuns :: [(Int,Word)] -> [(Int,Word)]\n",
      "sortRuns = List.reverse . List.sort\n",
      "\n",
      "-- take :: Int -> [a] -> [a]\n",
      "\n",
      "showRun :: (Int,Word) -> String\n",
      "showRun (x,y) = concat [y, \"\\t\", show(x), \"\\n\"]\n",
      "\n",
      "-- map showRun :: [(Int,Word)] -> [String]\n",
      "\n",
      "-- concat :: [[a]] -> [a] from Prelude\n",
      "commonWords :: Int -> Text -> String\n",
      "commonWords n = concat . map showRun . take n . \n",
      "                sortRuns . countRuns . sortWords . \n",
      "                words . map Char.toLower\n",
      "\n",
      "sample = \"cc ba aa ba cc cc\"\n",
      "\n",
      "putStrLn $ commonWords 2 sample"
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "cc\t3\n",
        "ba\t2"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "## Common Words\n",
      "The definition of commonWords is given as a pipeline of eight component functions glued together by functional composition. Not every problem can be decomposed into component tasks in quite such a straightforward manner, but when it can, the resulting program is simple, attractive and effective."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "## numbers into words\n",
      "The example demonstrates another fundamental aspect of problem solving, namely that a good way to solve a tricky problem is to first simplify the problem and then see how to solve the simpler problem."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "## Exercise A"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "double :: Integer -> Integer\n",
      "double x = 2 * x\n",
      "\n",
      "map double [1,4,4,3]\n",
      "map (double . double) [1,4,4,3]\n",
      "map double []\n",
      "\n",
      "sample2 = [1,2,3,4]\n",
      "sample3 = [[1,2], [3,4], [5]]\n",
      "\n",
      "(List.sum . map double) sample2 == (double . List.sum) sample2\n",
      "(List.sum . map List.sum) sample3 == (List.sum . concat) sample3\n",
      "(List.sum . List.sort) sample2 == List.sum sample2"
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "[2,8,8,6]"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "[4,16,16,12]"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "[]"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "True"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "True"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "## Exercise D"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(words . map Char.toLower) sample\n",
      "(map (map Char.toLower) . words) sample"
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "[\"cc\",\"ba\",\"aa\",\"ba\",\"cc\",\"cc\"]"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "[\"cc\",\"ba\",\"aa\",\"ba\",\"cc\",\"cc\"]"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "## Exercise F"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "anagrams :: Int -> [Word] -> String\n",
      "anagrams n = List.concat . List.intersperse \"\\n\" . map showItem . groupItems . sortItems . map normalize . take n\n",
      "\n",
      "normalize :: Word -> (Word,Word)\n",
      "normalize w = (List.sort w, w)\n",
      "\n",
      "sortItems :: [(Word,Word)] -> [(Word,Word)]\n",
      "sortItems = List.sort\n",
      "\n",
      "groupItems :: [(Word,Word)] -> [(Word,[Word])]\n",
      "groupItems [] = []\n",
      "groupItems xxs@((n,w):xs) = (n, hl) : groupItems t\n",
      "                   where hl = (map snd . takeWhile (\\(v,vs) -> n==v)) xxs\n",
      "                         t = dropWhile (\\(v,vs) -> n==v) xs\n",
      "\n",
      "showItem :: (Word,[Word]) -> String\n",
      "showItem (x,xs) = show . List.concat $ x:\": \":(List.intersperse \",\" xs)\n",
      "\n",
      "putStr $ anagrams 5 [\"abc\", \"bca\", \"cab\", \"def\", \"fed\"]"
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "\"abc: abc,bca,cab\"\n",
        "\"def: def,fed\""
       ]
      }
     ],
     "prompt_number": 39
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "hidden": false
     },
     "source": [
      "## Exercise G"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "song :: Int -> String\n",
      "song n  = if n==0 then \"\"\n",
      "          else song (n-1) ++ \"\\n\" ++ verse n\n",
      "\n",
      "verse :: Int -> String\n",
      "verse n = line1 n ++ line2 n ++ line3 n ++ line4 n\n",
      "\n",
      "number = [\"\",\"one\",\"two\",\"three\",\"four\",\n",
      "          \"five\",\"six\",\"seven\",\"eight\",\"nine\"]\n",
      "\n",
      "man :: Int -> String\n",
      "man n = number !! n ++ if n == 1 then \" man\" else \" men\"\n",
      "\n",
      "mans :: Int -> String\n",
      "mans n = (concat . List.intersperse \", \" . map man . reverse)  [1..n]\n",
      "\n",
      "cap :: String -> String\n",
      "cap [] = []\n",
      "cap (x:xs) = Char.toUpper x : xs\n",
      "\n",
      "line1 :: Int -> String\n",
      "line1 n = cap $ man n ++ \" went to mow\\n\"\n",
      "\n",
      "line2 :: Int -> String\n",
      "line2 n = \"Went to mow a meadow\\n\"\n",
      "\n",
      "line3 :: Int -> String\n",
      "line3 n = cap $ mans n ++ \" and his dog\\n\"\n",
      "\n",
      "line4 :: Int -> String\n",
      "line4 n = \"Went to mow a meadow\\n\"\n",
      "\n",
      "putStr $ song 1\n",
      "putStr $ song 2"
     ],
     "language": "python",
     "metadata": {
      "hidden": false
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "\n",
        "One man went to mow\n",
        "Went to mow a meadow\n",
        "One man and his dog\n",
        "Went to mow a meadow"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "\n",
        "One man went to mow\n",
        "Went to mow a meadow\n",
        "One man and his dog\n",
        "Went to mow a meadow\n",
        "\n",
        "Two men went to mow\n",
        "Went to mow a meadow\n",
        "Two men, one man and his dog\n",
        "Went to mow a meadow"
       ]
      }
     ],
     "prompt_number": 32
    }
   ],
   "metadata": {}
  }
 ]
}