haskell_gentle.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "haskell_gentle.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPQi1kSHQtQWOWmHoTLoZD0",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kalz2q/mycolabnotebooks/blob/master/haskell_gentle.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W3PkoT_HorRB"
      },
      "source": [
        "# メモ\n",
        "\n",
        "a gentle introduction to haskell  \n",
        "https://www.sampou.org/haskell/tutorial-j/  \n",
        "https://www.haskell.org/tutorial/  \n",
        "を読む。ノート。"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1uIL6O97ZUVj"
      },
      "source": [
        "%%capture\n",
        "!apt install haskell-platform"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4mGx09C_ZeXG",
        "outputId": "f5d07261-ef9b-4888-aa55-8f49272b3356",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "!ghc --version"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The Glorious Glasgow Haskell Compilation System, version 8.0.2\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sxl3u4P4ohJ3"
      },
      "source": [
        "# 型付け\n",
        "%%script false\n",
        "                         5  :: Integer\n",
        "                        'a' :: Char\n",
        "                        inc :: Integer -> Integer\n",
        "                    [1,2,3] :: [Integer]\n",
        "                    ('b',4) :: (Char,Integer)\n",
        "\n",
        "# :: はなになにの型はなになに \"has type\" と読むことができる\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "4gEPgSXoUdSx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rTYlGnFKrEVV"
      },
      "source": [
        "# 関数定義\n",
        "%%script false\n",
        "\n",
        "inc n          = n+1\n",
        "\n",
        "inc            :: Integer -> Integer\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YHINhqE_xkS7"
      },
      "source": [
        "# e1 が評価され e2 になることを\n",
        "# e1 => e2\n",
        "# と書く。\n",
        "\n",
        "# 例えば\n",
        "%%script false\n",
        "\n",
        "inc (inc 3) => 5\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z5RsjAx-x-4Y"
      },
      "source": [
        "# list とは\n",
        "%%script false\n",
        "\n",
        "length                  :: [a] -> Integer\n",
        "length []               =  0\n",
        "length (x:xs)           =  1 + length xs\n",
        "\n",
        "length [1,2,3]\t=>\t3\n",
        "length ['a','b','c']\t=>\t3\n",
        "length [[1],[2],[3]]\t=>\t3"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lLgRxRVLh2D9"
      },
      "source": [
        "# head と tail\n",
        "%%script false\n",
        "\n",
        "head                    :: [a] -> a\n",
        "head (x:xs)             =  x\n",
        "\n",
        "tail                    :: [a] -> [a]\n",
        "tail (x:xs)             =  xs\n",
        "\n",
        "#  head と tail はカラのリストではエラーになる\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WoimBfFbrRTh"
      },
      "source": [
        "# 型の定義\n",
        "%%script false\n",
        "\n",
        "data Bool               = False | True\n",
        "\n",
        "# Bool, False, True は引数を持たないコンストラクタ nullary constructor\n",
        "# Bool が型の名前、型コンストラクタで、False, True がデータコンストラクタ\n",
        "\n",
        "data Color              = Red | Green | Blue | Indigo | Violet\n",
        "\n",
        "# Bool, Color は列挙型 enumerated type\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0Q-fYTMN38JL"
      },
      "source": [
        "# 次のは 1つだけデータコンストラクタ(Pt a a)を持つ型\n",
        "\n",
        "data Point a            = Pt a a\n",
        "\n",
        "# Point のような型はタプル型と呼ばれる。 なぜなら本質的に他の型の直積(デカルト積)だから。\n",
        "# Bool, Color のような複数のデータコンストラクタを持つ型は直和型((disjoint) union or sum types)と呼ばれる。\n",
        "\n",
        "# Point は多相型なので、次のは正しい。\n",
        "\n",
        "Pt 2.0 3.0 :: Point Float\n",
        "Pt 'a' 'b' :: Point Char\n",
        "Pt True False :: Point Bool\n",
        "\n",
        "# 多相型の型コンストラクタとして、[] や -> がある。\n",
        "\n",
        "# データコンストラクタを適用して値を得ることと、型コンストラクタを適用して型を得ることを区別する。\n",
        "# 名前空間が違うので、同じ名前が使える。\n",
        "data Point a = Point a a"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Jyuv8v8a8ZUD"
      },
      "source": [
        "# 再帰型\n",
        "%%script false\n",
        "\n",
        "data Tree a = Leaf a | Branch (Tree a) (Tree a)\n",
        "\n",
        "# ここで Tree は型コンストラクタで Branch や Leaf はデータコンストラクタなので\n",
        "\n",
        "Branch :: Tree a -> Tree a -> Tree a\n",
        "Leaf :: a -> Tree a\n",
        "\n",
        "# ということになる。\n",
        "\n",
        "# fringeという、木を左から右へたどって「葉」にある要素のリストを返す関数を定義したいとする。\n",
        "# その定義は次のようになる\n",
        "\n",
        "fringe :: Tree a -> [a]\n",
        "fringe (Leaf x) = [x]\n",
        "fringe (Branch left right) = fringe left ++ fringe right\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1pmHUaAQUMx7"
      },
      "source": [
        "# type synonym 型の同義名、シノニム\n",
        "%%script false\n",
        "\n",
        "type String = [Char]\n",
        "type Person = (Name, Address)\n",
        "type Name = String\n",
        "data Address = None | Addr String\n",
        "\n",
        "type AssocList a b = [(a,b)]\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "54rS1eZ8Uxs3"
      },
      "source": [
        "# Built-in 組み込みの型について\n",
        "# 例えば Char は\n",
        "%%script false\n",
        "data Char = \n",
        "    Ca | Cb | Cc | ...\n",
        "    | CA | CB | CC | ...\n",
        "    | C1 | C2 | C3 | ...\n",
        "    ...\n",
        "\n",
        "# 同様に\n",
        "\n",
        "data Int = -65532 | ... | -1 | 0 | 1 | ... | 65532\n",
        "\n",
        "data Integer = ... -2 | -1 | 0 | 1 | 2 ...\n",
        "\n",
        "# のように考えることができる。ここで、-65532と65532は、与えられた処理系における固定精度整数の最小値と最大値。\n",
        "\n",
        "# タプルもこのやりかたで定義できる。\n",
        "\n",
        "data (a,b) = (a,b)\n",
        "data (a,b,c) = (a,b,c)\n",
        "data (a,b,c,d) = (a,b,c,d)\n",
        "        . .\n",
        "        . .\n",
        "        . .\n",
        "\n",
        "# リストも同様に定義できる。リストの場合は再帰的になる。\n",
        "\n",
        "data [a] = [] | a : [a]\n",
        "\n",
        "# タプルとリストの違いから次のようなルールが明らかである。\n",
        "\n",
        "# (e1,e2,...,en), n>=2 に対して、もし、ti が ei の型であるとす るならば、タプルの型は (t1,t2,...,tn) \n",
        "# [e1,e2,...,en], n>=0 に対して各 ei が必ず同じ型 t であるなら、そのリストの 型は [t]\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T0-81qtasBS9"
      },
      "source": [
        "# リスト内包表記 List Comprehensions と 数列 Arithmetic Sequences\n",
        "%%script false\n",
        "\n",
        "[ f x | x <- xs ]\n",
        "\n",
        "[ (x,y) | x <- xs, y <- ys ]\n",
        "\n",
        "# xs = [1,2] 、ys = [3,4] ならば =>  [(1,3),(1,4),(2,3),(2,4)] となる。\n",
        "\n",
        "# ガード guard\n",
        "\n",
        "quicksort [] = []\n",
        "quicksort (x:xs) = quicksort [y | y <- xs, y<x ] ++ [x] ++ quicksort [y | y <- xs, y>=x]\n",
        "\n",
        "# 数列 Arithmetic Sequences\n",
        "\n",
        "[1..10] => [1,2,3,4,5,6,7,8,9,10] -- 10 も入ることに注意\n",
        "[1,3..10] => [1,3,5,7,9] -- 10 以下の奇数\n",
        "[1,3..] => [1,3,5,7,9, ...] -- 無限\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NXfjmS6J_sKc"
      },
      "source": [
        "# 文字列 String\n",
        "%%script false\n",
        "\n",
        "['h','e','l','l','o'] = \"hello\"\n",
        "\n",
        "type String = [Char]\n",
        "\n",
        "\"hello\" ++ \" world\" => \"hello world\"\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fzudYNjSSc1S"
      },
      "source": [
        "# 関数\n",
        "%%script false\n",
        "\n",
        "add :: Integer -> Integer -> Integer\n",
        "add x y = x + y\n",
        "\n",
        "# これは add (x,y) = x + y とは違う\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zzgGYrSuUqn-",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "647a3f00-1349-4817-8ff4-96bcece5909c"
      },
      "source": [
        "# 実験\n",
        "!ghc -e $'let {add x y = x + y; inc = add 1} in print (inc 4) '\n",
        "!ghc -e $'let {add (x y) = x + y; inc = add 1} in print (inc 4) ' #=> Parse error\n",
        "!ghc -e $'let {add x y = x + y; inc = add 1} in print (add 4 5) '\n",
        "!ghc -e $'let {add (x, y) = x + y} in print (add (4, 5)) '"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "5\n",
            "\n",
            "<interactive>:0:11: error: Parse error in pattern: x\n",
            "9\n",
            "9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HXzyrmrSUplh"
      },
      "source": [
        "# map 関数は関数を引数にとる\n",
        "%%script false\n",
        "\n",
        "map :: (a->b) -> [a] -> [b]\n",
        "map f [] = []\n",
        "map f (x:xs) = f x : map f xs\n",
        "\n",
        "map (add 1) [1,2,3] => [2,3,4]\n",
        "\n",
        "# この例は関数が第一級の対象 (first-class object) であることを示している。\n",
        "# このような使いかたをする関数は高階 (higher-order)関数とよばれる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UVud-SgCTuK-"
      },
      "source": [
        "# ラムダ抽象 (lambda abstraction) 無名関数\n",
        "# 例えば inc は  \\x -> x+1 と書く。\n",
        "# add は \\x -> \\y -> x + y と書く。\n",
        "# 簡略化して \\x y -> x + y と書く。\n",
        "%%script false\n",
        "\n",
        "inc x = x+1\n",
        "add x y = x+y\n",
        "\n",
        "# は次の等式と同等\n",
        "\n",
        "inc = \\x -> x+1\n",
        "add = \\x y -> x+y\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0vHy_7FYkFa5"
      },
      "source": [
        "# 中置演算子 infix operator\n",
        "# 中置演算子は関数なので、等式を使って定義\n",
        "%%script false\n",
        "\n",
        "# リストの連結演算子\n",
        "(++) :: [a] -> [a] -> [a]\n",
        "[] ++ ys = ys\n",
        "(x:xs) ++ ys = x : (xs++ys)\n",
        "\n",
        "# マイナス(-)は前置演算子にも、中置演算子にもなる。\n",
        "\n",
        "# 関数合成(function composition)演算子\n",
        "\n",
        "(.) :: (b->c) -> (a->b) -> (a->c)\n",
        "f . g = \\ x -> f (g x)\n",
        "\n",
        "# 中置演算子の部分適用は section と呼ばれる\n",
        "\n",
        "(x+) = \\y -> x+y\n",
        "(+y) = \\x -> x+y\n",
        "(+) = \\x y -> x+y\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rmHpY3dUdFXR",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4ad7e589-e0fe-4fc9-d6fa-a567117e302d"
      },
      "source": [
        "# 実験 中置演算子の部分適用が関数を返すことの確認\n",
        "# map (+) [1,2,3] は関数のリスト\n",
        "\n",
        "!ghc -e $'((map (+) [1,2,3])!!1) 5' #=> 7\n",
        "!ghc -e $'((map (/) [1,2,3])!!1) 5' #=> 0.4\n",
        "!ghc -e $'(map (5/) [1,2,3])!!1' #=> 2.5\n",
        "!echo\n",
        "!ghc -e $'map (/5) [1,2,3]'\n",
        "!ghc -e $'map (5/) [1,2,3]'\n",
        "!echo\n",
        "!ghc -e $'map (^2) [1,2,3]'\n",
        "!ghc -e $'map (2^) [1,2,3]'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "7\n",
            "0.4\n",
            "2.5\n",
            "\n",
            "[0.2,0.4,0.6]\n",
            "[5.0,2.5,1.6666666666666667]\n",
            "\n",
            "[1,4,9]\n",
            "[2,4,8]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eqqaVVQ9Tms2"
      },
      "source": [
        "# したがって\n",
        "%%script false\n",
        "\n",
        "inc = (+ 1)\n",
        "add = (+)\n",
        "\n",
        "# と書ける\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mMSn2u39e-I2"
      },
      "source": [
        "# 関数をバッククオートで括ると中置演算子になる\n",
        "%%script false\n",
        "\n",
        "x `elem` xs\n",
        "\n",
        "# は直感的に、x は xs の要素である (x is an element of xs)と読める。\n",
        "\n",
        "# (-) については特別なルールがある。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lMib8a4fTi8f"
      },
      "source": [
        "# 結合度 fixity の優先順位\n",
        "# fixity declaration では 0 から 9 を指定する。 9 が最強。\n",
        "# 一般の関数は 10 と仮定されている。\n",
        "# infixr は右結合、infixl は左結合\n",
        "%%script false\n",
        "\n",
        "infixr 5 ++\n",
        "infixr 9 .\n",
        "\n",
        "# デフォルトは infixl 9\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iwJlMBTTTfCA"
      },
      "source": [
        "# 関数は非正格 non-strict\n",
        "# bot が次のように定義されているとする。\n",
        "%%script false\n",
        "\n",
        "bot = bot\n",
        "\n",
        "# このような停止しない式の値を抽象的に _|_(ボトム)と表わす。\n",
        "# 1/0 もこの値を持ち、エラーは回復不可能で、プログラムはこれ以上継続することはできなくなる。\n",
        "# I/O のシステムのエラー(たとえば、EOFエラーなどの例外)は回復可能。\n",
        "\n",
        "# 関数 f が正格 strict であるとは、停止しない式に適用されれば、その適用式も停止しないこと。\n",
        "# ほとんどのプログラミング言語では、すべての関数が正格。Haskell では違う。\n",
        "\n",
        "const1 x = 1\n",
        "\n",
        "# のとき、const1 bot は 1 であり、引数は評価されない。 これを遅延評価と呼ぶ。\n",
        "\n",
        "const1 (1/0)\n",
        "\n",
        "# も 1 になる。\n",
        "\n",
        "# 遅延評価により、無限 infinite のデータ構造が扱える。\n",
        "\n",
        "# 別のやり方で説明すると、Haskell では代入 assignment ではなく、定義 definition を用いる。\n",
        "\n",
        "v = 1/0\n",
        "\n",
        "# は、v を 1/0と定義すると読む。vの値が必要になったときにのみゼロ除算エラーが発生する。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "q821gWlEjcxz"
      },
      "source": [
        "# 無限のデータ構造\n",
        "# データコンストラクタも非正格である。\n",
        "# リストのコンストラクタ、: も非正格。\n",
        "# 非正格の構築子で(概念的に)無限の infinite データ構造を 定義することができる。\n",
        "%%script false\n",
        "\n",
        "ones = 1 : ones\n",
        "\n",
        "numsFrom n = n : numsFrom (n+1)\n",
        "\n",
        "squares = map (^2) (numsFrom 0)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-LRVZ6YQsonz",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dc1c4e49-091a-4f28-dde8-c8df7ed71b9c"
      },
      "source": [
        "# 実験 take 5 squares => [0,1,4,9,16]\n",
        "!ghc -e $'let{numsFrom n = n:numsFrom(n+1); squares = map (^2)(numsFrom 0)} in print (take 5 squares)'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0,1,4,9,16]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i9IDhIi8vPQ_",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "741dcca6-f49b-413e-ac79-3a7b5c18d490"
      },
      "source": [
        "# 実験 ones は循環リスト circular list\n",
        "!ghc -e $'let{ones=1:ones} in print (take 5 ones)'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1,1,1,1,1]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WdBm8aZeTVcU"
      },
      "source": [
        "# フィボナッチ関数\n",
        "%%script false\n",
        "\n",
        "fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]\n",
        "\n",
        "# ここで zip とは\n",
        "\n",
        "zip (x:xs) (y:ys) = (x,y) : zip xs ys\n",
        "zip xs ys = []\n",
        "\n",
        "# エラー関数 error\n",
        "\n",
        "error :: String-> a\n",
        "\n",
        "# 型からは返す値の型は多相の型で実際の型がわからない。\n",
        "# すべての型によって「共有」される値 _|_ bottom が存在する。\n",
        "# error の返す値は常にこの値。しかし、実装はチェックのための error の文字列引数を印字する。\n",
        "\n",
        "head (x:xs) = x\n",
        "head [] = error \"head{PreludeList}: head []\"\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kytnaqOUxmKi"
      },
      "source": [
        "# Case 式\n",
        "# パターンは入れ子にも使える。\n",
        "%%script false\n",
        "\n",
        "contrived :: ([a], Char, (Int, Float), String, Bool) -> Bool\n",
        "contrived ([], 'b', (1, 2.0), \"hi\", True) = False\n",
        "\n",
        "# 仮引数 (formal parameters) もパターンであり、値にかならず照合が成功する。\n",
        "# その副作用として、仮引数は照合が成功した値に束縛される。\n",
        "# なぜなら、1つの等式であれば、そのなかのパターンには、2つ以上の同じ仮引数が含まれてはいけないから。\n",
        "# これは、線型性 (linearity) と呼ばれる。\n",
        "# 仮引数のような必ず照合が成功するようなパターンのことを irrefutable パターンと呼び、\n",
        "# refutable パターンは照合が成功しない可能性があり contrived の例はこの refutable の例。\n",
        "# 不可反駁パターンに は 3つの種類がありそのうち 2つを紹介する。\n",
        "\n",
        "# アズパターン\n",
        "# たとえばリストの第一要素を複製する関数\n",
        "\n",
        "f (x:xs) = x:x:xs\n",
        "\n",
        "# 明日パターンを使うと次のようになる。\n",
        "\n",
        "f s@(x:xs) = x:s\n",
        "\n",
        "# アズパターンは照合に常に成功するが、サブパターン(この場合は、x:xs)はもちろん照合が成功しないこともある。\n",
        "\n",
        "# ワイルドカード\n",
        "# head 関数や tail 関数は次のように書き換えることができる。\n",
        "\n",
        "head (x:_) = x\n",
        "tail (_:xs) = xs\n",
        "\n",
        "# 仮引数の場合とちがい、ワイルドカードは 1つの等式のなかに 1つ以上あっても構わない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lDDePI7Mxz-Y"
      },
      "source": [
        "# パターン照合の意味論 semantics\n",
        "\n",
        "# パターン照合は、fail, succeed, diverge (発散) の場合がある。\n",
        "# 成功すると、パターンの中の仮引数が束縛される。\n",
        "# 発散 diverge はパターンが必要とした値がエラー(_|_ )を含んでいた場合。\n",
        "# すべての等式でパターン照合が失敗すると、その関数適用の値は _|_ になり、実行時エラーとなる。\n",
        "#\n",
        "# たとえば、[1,2] を [0,bot] に照合させようとすると、0 と 1 がマッチしないので照合は失敗。\n",
        "# しかし、もし、[1,2] を [bot,0] にマッチさせようとすると、1 を botへ照合させる際に発散がおこる。\n",
        "\n",
        "# パターンがガード部を持つこともある。\n",
        "%%script false\n",
        "\n",
        "sign x |  x >  0        =   1\n",
        "       |  x == 0        =   0\n",
        "       |  x <  0        =  -1\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ljcyvf8Wd4Ub"
      },
      "source": [
        "# パターン照合が関数の意味に微妙な影響を与える場合がある\n",
        "\n",
        "%%script false\n",
        "\n",
        "take 0 _ = []\n",
        "take _ [] = []\n",
        "take n (x:xs) = x : take (n-1) xs\n",
        "\n",
        "# と\n",
        "\n",
        "take1 _ [] = []\n",
        "take1 0 _ = []\n",
        "take1 n (x:xs) = x : take1\n",
        "(n-1) xs\n",
        "\n",
        "# 次の結果を見る。\n",
        "\n",
        "take 0 bot => []\n",
        "take1 0 bot => _|_\n",
        "take bot [] => _|_\n",
        "take1 bot [] => []\n",
        "\n",
        "# どちらがよいということでなく、違いがあるということを覚えておく。"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pOuFmZ5RuEUg"
      },
      "source": [
        "# Case 式\n",
        "# 関数定義のなかでのパターン照合の意味は、実は case 式のより単純なものと考えられる。\n",
        "%%script false\n",
        "\n",
        "# 次のような関数定義があったとする。\n",
        "f p11 ... p1k = e1\n",
        "...\n",
        "f pn1 ... pnk = en\n",
        "\n",
        "# これは以下と同等。\n",
        "\n",
        "f x1 x2 ... xk = case (x1, ..., xk) of\n",
        "    (p11, ..., p1k) -> e1\n",
        "    ...\n",
        "    (pn1, ..., pnk) -> en\n",
        "\n",
        "# take についても\n",
        "\n",
        "take m ys = case (m,ys) of\n",
        "    (0,_) -> []\n",
        "    (_,[]) -> []\n",
        "    (n,x:xs) -> x : take (n-1) xs\n",
        "\n",
        "# となる。\n",
        "# case 式の右辺はすべて同じ主型である。\n",
        "\n",
        "# if 式の\n",
        "\n",
        "if e1 then e2 else e3\n",
        "\n",
        "# は次の構文の簡略形である。\n",
        "\n",
        "case e1 of True -> e2\n",
        "        False -> e3\n",
        "\n",
        "# つまり、if_then_else_ を関数とみなせば\n",
        "\n",
        "Bool -> a -> a -> a \n",
        "\n",
        "# という型である。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wvSLoKvxxxSl"
      },
      "source": [
        "# 遅延 lazy パターン\n",
        "# 遅延パターンは ~pat であらわされる。\n",
        "# 不可反駁 irrefutable で値 v の ~pat に 対する照合は常に成功する。\n",
        "# pat のなかの識別子が右辺で「利用」されるとすると、それは v が pat に\n",
        "# マッチすると仮定した場合の値に束縛されるか、_|_ となる。\n",
        "\n",
        "# 遅延パターンは無限のデータ構造が再帰的に定義されているような場合に便利。\n",
        "# 無限リストはシミュレーションプログラムを書くのに使いやすいデータ構造で、ストリームという。\n",
        "\n",
        "# server と client との間のやりとりの簡単なケースを考える。\n",
        "# client は一連の要求を server に送り、server は各々の要求に対して、応答を返す。\n",
        "# client は引数として初期メッセージもとることに注意。\n",
        "\n",
        "%%script false\n",
        "\n",
        "reqs = client init resps\n",
        "resps = server reqs\n",
        "\n",
        "# さらに、サーバとクライアントの構造を、以下のように仮定する。\n",
        "\n",
        "client init (resp:resps) = init : client (next resp) resps\n",
        "server (req:reqs) = process req : server reqs\n",
        "\n",
        "# next はサーバからの応答を与えられて、次の要求を決定する関数であり、\n",
        "# process はクライアントからの要求を与えられて、応答を返す関数であるとする。\n",
        "\n",
        "# 残念ながら、このプログラムには大きな問題がある。\n",
        "# 問題は、client が reqs と resps の再帰的な設定のなかで使われているので、\n",
        "# 最初の要求を送信する前に応答リストと照合を試みようとする。つまり、\n",
        "# パターン照合がおこなわれるのが「早すぎる」。\n",
        "# これを是正する 1つの方法は以下のように client を再定義する。\n",
        "\n",
        "client init resps = init : client (next (head resps)) (tail resps)\n",
        "\n",
        "# これで動作するようになるが、もっとよい解決法は遅延パターンを使う方法である。\n",
        "\n",
        "client init ~(resp:resps) = init : client (next resp) resps\n",
        "\n",
        "# 遅延パターンは不可反駁なので、照合はただちに成功し、最初の要求が発信され、\n",
        "# それから最初の応答が生成される。\n",
        "\n",
        "#  この例は、以下のように定義を加えれば、実際に動作する。\n",
        "\n",
        "init = 0\n",
        "next resp = resp\n",
        "process req = req+1\n",
        "\n",
        "# 実際に動作させてみると、\n",
        "\n",
        "take 10 reqs => [0,1,2,3,4,5,6,7,8,9]\n",
        "\n",
        "## 動作しない!!!!"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7M2XhHV2nkvE"
      },
      "source": [
        "# フィボナッチ関数 遅延評価版\n",
        "%%script false\n",
        "\n",
        "fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]\n",
        "\n",
        "# これをアズパターンを使って次のように書き換える。\n",
        "\n",
        "fib@(1:tfib) = 1 : 1 : [ a+b | (a,b) <- zip fib tfib ]\n",
        "\n",
        "# この種の等式はパターン束縛(patternbinding )と呼ばれる。\n",
        "# 理由は、トップレベルにある等式で左辺全体が 1つのパターンになっているから。\n",
        "# すなわち、fib と tfibはともに宣言内で 束縛されているということです。\n",
        "# Haskellのパターン束縛は暗黙のう ちに ~ がパターンの前についているものとみなす。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VZVXuJOTUkdk",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8112b31d-32d4-454c-b4db-f607b50a7761"
      },
      "source": [
        "# 実験\n",
        "!ghc -e $'let {fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]} in print (take 5 fib)'\n",
        "!ghc -e $'let {fib@(1:tfib) = 1 : 1 : [ a+b | (a,b) <- zip fib tfib ]} in print (take 5 fib)'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1,1,2,3,5]\n",
            "[1,1,2,3,5]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "McnhdUfSxslV"
      },
      "source": [
        "# 字句の有効範囲と入れ子形式 Lexical Scoping and Nested Forms\n",
        "# let 式\n",
        "%%script false\n",
        "\n",
        "let y   = a*b\n",
        "    f x = (x+y)/y\n",
        "in f c + f d\n",
        "\n",
        "# let 式 expression によってつくられる束縛は、相互再帰的 (mutually recursive)で、遅延パターンとして扱われる。\n",
        "# ~ が暗黙のうちについている。\n",
        "\n",
        "# where 節 clause\n",
        "# いくつかのガードをもつ等式にまたがる有効範囲束縛が便利なときには where 節を使う。\n",
        "\n",
        "f x y  |  y>z           =  ...\n",
        "       |  y==z          =  ...\n",
        "       |  y<z           =  ...\n",
        "     where z = x*x\n",
        "\n",
        "# where 節はそれが覆う式の上にしか有効範囲がない。\n",
        "# where 節は等式の集まりあるいは case 式のトップレベルでしか認められない。\n",
        "\n",
        "# let 式は式であり、where 節は式ではない。where 節は関数宣言および case 式の構文の一部である。\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hk3ujlpqxo8C"
      },
      "source": [
        "# レイアウト\n",
        "# Haskell はセミコロンあるいはそれにかわる終端記号を使わずにすんでいるのか。\n",
        "%%script false\n",
        "\n",
        "let y   = a*b\n",
        "    f x = (x+y)/y\n",
        "in f c + f d\n",
        "\n",
        "# 構文解析子 parser はなぜ次のように解析したりしないのか。\n",
        "\n",
        "let y   = a*b f\n",
        "    x   = (x+y)/y\n",
        "in f c + f d\n",
        "\n",
        "# Haskell はレイアウト (layout) と呼ばれる、二次元構文を用いているから。\n",
        "# カラム位置に依存している。\n",
        "# 上の例は次のように解釈される。\n",
        "\n",
        "let { y   = a*b\n",
        "    ; f x = (x+y)/y\n",
        "    }\n",
        "in f c + f d\n",
        "\n",
        "# 1行に複数の式を書きたいときにはセミコロンが便利である。\n",
        "\n",
        "let y   = a*b;  z = a/b\n",
        "    f x = (x+y)/z\n",
        "in f c + f d\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mFLQHFq3f6-i"
      },
      "source": [
        "# 型クラスと多重定義 overloading\n",
        "# すでに述べてきた多相 polymorphism は、パラメータ多相 parametric polymorphism とよばれる。\n",
        "# アドホック多相は多重定義 overloading という呼びかたのほうが知られている。\n",
        "# たとえば\n",
        "# 1、2 などのリテラルは、固定長の整数と任意長の整数の両方で使われる。\n",
        "# + のような数値演算子は何種類もの数値上で定義される。\n",
        "# 同値演算子 (Haskell では ==)は数値とその他多くの型の上で動作する。\n",
        "# Haskell では、型クラスによって多重定義を制御する。\n",
        "\n",
        "# elem 関数の定義を見てみよう。\n",
        "%%script false\n",
        "\n",
        "x `elem`  []            = False\n",
        "x `elem` (y:ys)         = x==y || (x `elem` ys)\n",
        "\n",
        "# ここで (==) を使っている。\n",
        "# 型クラス type class によって解決している。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SZZwd9G5K_ve",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "afcc5ae0-adac-4380-ef36-dc4c71519ab1"
      },
      "source": [
        "# 実験\n",
        "!ghc -e $':t elem'\n",
        "!ghc -e $':t (==)'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "elem :: (Eq a, Foldable t) => a -> t a -> Bool\n",
            "(==) :: Eq a => a -> a -> Bool\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DO7LoCEkgTqj"
      },
      "source": [
        "# 同値演算子を含むクラスの定義をしてみよう。\n",
        "%%script false\n",
        "\n",
        "class Eq a where\n",
        "    (==) :: a -> a -> Bool\n",
        "\n",
        "# Eq は定義するクラスの名前である。\n",
        "# 型 a がクラス Eq のインスタンスでなければならない、という制約 constraint は、\n",
        "\n",
        "Eq a \n",
        "\n",
        "# のように書く。\n",
        "# Eq a は 式 expression ではなく、constraint を表しているので、文脈 context と呼ばれる。\n",
        "\n",
        "(==) :: (Eq a) => a -> a -> Bool\n",
        "\n",
        "# は、クラス Eq のインスタンスである型 a に対して、== は a->a->Boolという型をもつ、と読む。\n",
        "# したがって\n",
        "\n",
        "elem :: (Eq a) => a -> [a] -> Bool\n",
        "\n",
        "# となり、求めていたものに他ならない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xsgb9EIwL632",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "104a1102-1ef8-4982-b966-b92eeb546c3b"
      },
      "source": [
        "# 実験\n",
        "!ghc -e $':k Eq'\n",
        "!ghc -e $':k Foldable'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Eq :: * -> Constraint\n",
            "Foldable :: (* -> *) -> Constraint\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IGrivSGZgROb"
      },
      "source": [
        "# どの型が Eq クラスのインスタンスになるかを指定し、その型に対する == の実際の振舞いがどうなるかは\n",
        "# インスタンス宣言 (instance declaration)で行う。\n",
        "%%script false\n",
        "\n",
        "instance Eq Integer where \n",
        "  x == y                =  x `integerEq` y\n",
        "\n",
        "# 同様に\n",
        "\n",
        "instance Eq Float where\n",
        "  x == y                =  x `floatEq` y\n",
        "\n",
        "instance (Eq a) => Eq (Tree a) where \n",
        "  Leaf a         == Leaf b          =  a == b\n",
        "  (Branch l1 r1) == (Branch l2 r2)  =  (l1==l2) && (r1==r2)\n",
        "  _              == _               =  False\n",
        "\n",
        "# 最初の行の Eq a という文脈は必須である。なぜなら、\n",
        "# 葉のもつ要素 (型は a)は 2番目の行の同値性を用いて比較する。\n",
        "\n",
        "# 実際の Eq の定義\n",
        "class  Eq a  where\n",
        "  (==), (/=)            :: a -> a -> Bool\n",
        "  x /= y                =  not (x == y)\n",
        "\n",
        "# :i で調べたら次のようだった。 同じと思われる。\n",
        "class Eq a where\n",
        "  (==) :: a -> a -> Bool\n",
        "  (/=) :: a -> a -> Bool\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6FktdMRtgPHU"
      },
      "source": [
        "# クラス拡張 (class extension) もサポートされている。\n",
        "# たとえば、Eq クラスからすべての操作を継承 (inherit)した Ord クラスを定義したいとする。\n",
        "# このクラスは Eq クラスから継承した操作のほかに、比較 操作子と min 関数および max 関数をもつものとする。\n",
        "%%script false\n",
        "\n",
        "class  (Eq a) => Ord a  where\n",
        "  (<), (<=), (>=), (>)  :: a -> a -> Bool\n",
        "  max, min              :: a -> a -> a\n",
        "\n",
        "# Eq は Ord のスーパークラス、Ord は Eq のサブクラス(subclass )である。\n",
        "\n",
        "# Ord の宣言は、(<) に対応するデフォルトメソッドを含んでいる。\n",
        "\n",
        "x < y               =  x <= y && x /= y\n",
        "\n",
        "# quicksort の型は次のようになっている。\n",
        "\n",
        "quicksort :: (Ord a) => [a] -> [a]\n",
        "\n",
        "# 多重継承 (multiple inheritance) \n",
        "\n",
        "class (Eq a, Show a) => C a \n",
        "    where ...\n",
        "\n",
        "# C というクラスをつくっている、操作を Eq と Show の両方から継承している。\n",
        "\n",
        "# クラスメソッドはトップレベルの宣言として扱われる。\n",
        "\n",
        "# クラスメソッドには、制約を付加することができる。\n",
        "\n",
        "class C a where\n",
        "    m :: Show b => a -> b\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ymXtGyyLfj3p"
      },
      "source": [
        "# クラス宣言の中で、高階型 higher-order type を使う。\n",
        "# 以下のような Functor クラスを考えよう。\n",
        "%%script false\n",
        "\n",
        "class Functor f where\n",
        "    fmap :: (a -> b) -> f a -> f b\n",
        "\n",
        "# fmap 関数は以前に使った map 関数を一般化したもの。\n",
        "# 型変数 f は f a のなかで他の型に適用される。こ のように、型変数が\n",
        "# 型 Tree に対する Functor のインスタンス は、\n",
        "\n",
        "instance Functor Tree where\n",
        "  fmap f (Leaf x)       = Leaf   (f x)\n",
        "  fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2)\n",
        "\n",
        "# このインスタンス宣言は Tree a ではなく Tree が Functor のインスタンスであることを宣言している。\n",
        "# これは総称的「コンテナ」型を記述する能力のあることを示し、fmap のような、任意の木、\n",
        "# リストあるいは他の型の上で統一的に動作する関数を可能にする。\n",
        "\n",
        "# 型適用は関数適用とおなじやりかたで書ける。型 T a b は (T a) b　と構文解析される。\n",
        "# タプルのような特別な構文を使う型はカリー化可能な別のスタイルで書ける。\n",
        "# 関数については、(->) が型構築子である。f -> g と (->) f g とは同じである。\n",
        "# 同様に、[a] と [] aとは同じである。\n",
        "# タプルについては、型構築子は (,)、(,,) などとなる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "h--_PPf7rvGj"
      },
      "source": [
        "# 型システムは式の中で型付けエラーを検出する。\n",
        "# 式 (+) 1 2 3 は型エラーになる。それは (+) は 2 つしか引数をとらないからである。\n",
        "# 同様に、Tree Int Int は、エラーを起こす。それは Tree 型は 1つの引数しかとらないからである。\n",
        "# Haskellはどのようにして不正な型式を検出するのか。\n",
        "\n",
        "# その答は、型の正当性を確認する第2の型システムにある。\n",
        "# 型は類 (kind)と結びついている。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SlIXAGJjtLt9",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "479017d6-1746-45f9-8e4d-95ae310d1e7f"
      },
      "source": [
        "!ghc -e $':k Eq'\n",
        "!ghc -e $':k Integer'\n",
        "!ghc -e $':k Functor'\n",
        "!ghc -e $':k Num'\n",
        "!ghc -e $':k Foldable'\n",
        "!ghc -e $':k Ord'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Eq :: * -> Constraint\n",
            "Integer :: *\n",
            "Functor :: (* -> *) -> Constraint\n",
            "Num :: * -> Constraint\n",
            "Foldable :: (* -> *) -> Constraint\n",
            "Ord :: * -> Constraint\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_JMbT9o4tKBh"
      },
      "source": [
        "# 型はは次の 2つの形式をとる。\n",
        "\n",
        "# 記号 * は具体的なデータ対象に結びついた型の類をあらわす。\n",
        "# k1 と k2 とが類ならば、k1->k2 は k1 という類の型をとり、k2 という類の型を返す型の類である。\n",
        "\n",
        "# 型構築子 Tree の類は、*->* であり、Tree Int の類は * である。\n",
        "# Functor クラスのメンバーはすべて、類 *->* でなければならず、\n",
        "# 類付けのエラーは、次のような宣言により引き起こされる。\n",
        "%%script false\n",
        "\n",
        "instance Functor Integer where ...\n",
        "\n",
        "# なぜなら、Integer の類は * だからである。\n",
        "# 類は Haskell のプログラムの直接あらわれることはない。\n",
        "# コンパイラが型検査の前に類を推論する。「類宣言」のようなものは必要ない。\n",
        "# 型シグネチャが類エラーをおこすとき以外は、類は Haskellのプログラムの後ろに隠れている。\n",
        "# 類は非常にシンプルなので、コンパイラは、類衝突がおこれば、その旨のエラーメッセージを表示する。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "U666LVobgIAO"
      },
      "source": [
        "# オブジェクト指向プログラミング OOP とのアナロジー\n",
        "# OOP におけるクラスを型クラスへ置き換え、オブジェクトを型へ置き換えれば、ほぼ Haskell の型クラスになる。\n",
        "\n",
        "# OOP と比べると、型はオブジェクトではないというのは明かで、\n",
        "# OOP 言語に対する利点は、Haskellのメソッドは完全に型安全である。\n",
        "# 必要なクラスのなかにはない型の値にメソッドを適用するとしているかどうかは、\n",
        "# コンパイル時に検出される。単純に高階関数として引き渡される。\n",
        "\n",
        "# パラメータ多相とアドホック多相 overloading との関係を考察すると別の見方をすることができる。\n",
        "# パラメータ多相がどれほど便利かということは既に示した。\n",
        "# しかしながら、ときには、このような包括的グルーピングでは広すぎることもある。\n",
        "# もっと小さい型の集合の上でコントロールをしたい場合がある。たとえば、比較同値性をもつような型の集合\n",
        "# の上で、という時、型クラスは、これを実現する構造的方法とみなすことができる。\n",
        "# パラメータ多相は一種の多重定義とみなすことができ、多重定義は暗黙にすべての型の上で起こり、\n",
        "# 限定された型の集合(つまり、型クラス)上で起こるのではない。\n",
        "\n",
        "# 他の言語との比較\n",
        "# Haskell で用いられるクラスは OOP で用いられるクラスに類似している。しかし、いくつかの重大な相違がある。\n",
        "\n",
        "# Haskell は、型の定義とその型に結びついているメソッドの定義を分離する。 \n",
        "# C++ や Java のクラスは、ふつう、データ構造(メンバー変数)とそのデータ構造と結びついた関数(メソッド)\n",
        "# の両方を定義する。Haskell ではこれらの定義は別々におこなう。\n",
        "\n",
        "# Haskell は、型の違う関数が共通の名前を共有するような C++ 流の多重定義 はサポートしていない。\n",
        "\n",
        "# Haskell のオブジェクトの型は暗黙の型変換を受けない。値が投入あるい\n",
        "# は投出される Object のようなすべての基になるようなクラスは ない。\n",
        "\n",
        "# C++ や Java ではオブジェクトの実行時表現に (VTable のような) 同定情報を付加する。\n",
        "# Haskellではこのような情報は、型システムを通じて物理的にではなく、論理的に、値に付加する。\n",
        "\n",
        "# Haskell のクラスシステムには、(publicあるいは private などといっ\n",
        "# たクラス構成要素のような) アクセスコントロールの機構は組込まれていない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "i5B44NMHnSoM"
      },
      "source": [
        "# 再び、型について"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YwEfQHRekl0S"
      },
      "source": [
        "# 再び、型について\n",
        "\n",
        "# newtype 宣言\n",
        "# 表現が既存の型と同一だが，型システムの中では別の型として識別されるような型を定義する。\n",
        "# たとえば、Integer 型を次のような宣言で用いて、自然数を表現することができる。\n",
        "%%script false\n",
        "\n",
        "newtype Natural = MakeNatural Integer\n",
        "\n",
        "# 完全に新しい型 Natural を生成し、その構築子は 1つ の Integerだけを引数にとる。\n",
        "# この構築子 MakeNatural は Natural と Integer との間の変換をおこなう。\n",
        "\n",
        "toNatural               :: Integer -> Natural\n",
        "toNatural x | x < 0     = error \"Can't create negative naturals!\" \n",
        "            | otherwise = MakeNatural x\n",
        "\n",
        "fromNatural             :: Natural -> Integer\n",
        "fromNatural (MakeNatural i) = i\n",
        "\n",
        "# 次のインスタンス宣言は Natural を Num クラスに所属させる。\n",
        "\n",
        "instance Num Natural where\n",
        "    fromInteger         = toNatural\n",
        "    x + y               = toNatural (fromNatural x + fromNatural y)\n",
        "    x - y               = let r = fromNatural x - fromNatural y in\n",
        "                            if r < 0 then error \"Unnatural subtraction\"\n",
        "                                     else toNatural r\n",
        "    x * y               = toNatural (fromNatural x * fromNatural y)\n",
        "\n",
        "# この宣言なしでは、Natural は Num には属することができない。\n",
        "# 元の型に対するインスタンス宣言内容が、新しい型に持ち越されることはない。\n",
        "# 実際、この型の目的は、別の Num のインスタンスを導入することな。\n",
        "# もし、Naturalが Integer の型シノニムとして宣言されていれば、これはできない。\n",
        "\n",
        "# これらはすべて、newtype 宣言ではなく data 宣言を用いて も機能する。\n",
        "# しかし、data宣言では、Natural の値の表現にオーバヘッドが生じる。\n",
        "# newtype を用いることで data 宣言によって間接参照のレベルが深くなる (これは遅延性の故) \n",
        "# のを避けることができる。\n",
        "\n",
        "# キーワードをのぞけば、newtype 宣言は、単一フィールドをもつ単一 構築子の data\n",
        "# 宣言と同じ構文を用いる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5YJzpJFCnasi"
      },
      "source": [
        "# フィールドラベル\n",
        "# Haskell のデータ型内のフィールドは、位置を手がかりにアクセスすることも、\n",
        "# フィールドラベルを用いて名前でアクセスすることもできる。\n",
        "# 2次元の点に対する型について考察する。\n",
        "%%script false\n",
        "\n",
        "data Point = Pt Float Float\n",
        "\n",
        "# Point の構成要素は、構築子 Pt の第一引数と第二引数である。 次のような関数が考えられる。\n",
        "\n",
        "pointx :: Point -> Float\n",
        "pointx (Pt x _) = x\n",
        "\n",
        "# data 宣言における構築子は、フィールド名付で (波括弧で括られて) 宣言することができる。\n",
        "# フィールド名は構築子の構成要素を位置によってではなく、名前で同定する。\n",
        "\n",
        "data Point = Pt {pointx, pointy :: Float}\n",
        "\n",
        "# このデータ型は Point と同一、構築子 Pt も同じ。\n",
        "# しかし、この宣言では2つのフィールド名、pointx と pointyとが定義されている。\n",
        "# これらのフィールド名は構造の中から構成要素を取り出すための選択関数 (selector function) として使うことができる。\n",
        "\n",
        "pointx :: Point -> Float\n",
        "pointy :: Point -> Float\n",
        "\n",
        "# この selector を使って次のような関数を作ることができる。\n",
        "\n",
        "absPoint :: Point -> Float\n",
        "absPoint p = sqrt (pointx p * pointx p + pointy p * pointy p)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dGz4IRMa_gX2",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bde56a6a-b8b7-4a4e-dcd5-66e335c60a55"
      },
      "source": [
        "# 実験\n",
        "%%writefile point01.hs\n",
        "\n",
        "data Point = Pt {pointx, pointy :: Float}\n",
        "\n",
        "absPoint :: Point -> Float\n",
        "absPoint p = sqrt (pointx p * pointx p + pointy p * pointy p)\n",
        "\n",
        "somepoint = Pt 3.1 3.9\n",
        "\n",
        "main = print $ absPoint somepoint"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Overwriting point01.hs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LN1qcT8PARbm",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d49d695c-254b-4932-e80d-b10887022666"
      },
      "source": [
        "!runghc point01.hs"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "4.9819674\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Sva17Rgt_ePK"
      },
      "source": [
        "# フィールドラベルは新しい値を構築するときに使う。\n",
        "# 式 Pt {pointx=1, pointy=2} は式 Pt 1 2 と同一。\n",
        "# フィールド名を使って値を構築する場合、フィールドをいくつか省略することができる。\n",
        "# 省略されたフィールドは定義されない。\n",
        "# フィールド名を使ったパターンマッチングは構築子 Pt のときと同じような構文で使いる。\n",
        "%%script false\n",
        "\n",
        "absPoint (Pt {pointx = x, pointy = y}) = sqrt (x*x + y*y)\n",
        "\n",
        "# 既存の構造中のフィールド値を使って、新しい構造の構成要素を作る (update) ことができる。\n",
        "# p が Point ならば、p {pointx=2} は p と同じ pointy をもつが、pointx は 2 に置き換る。\n",
        "# 破壊的更新ではなく、オブジェクトの新しいコピーを生成する。\n",
        "\n",
        "# フィールドラベルと併せて使用した波括弧はいくぶん特殊な使い方で、\n",
        "# 通常、波括弧はレイアウトルールを無視するのに使われるが、\n",
        "# フィールド名とむすびついた波括弧は明示的に書かなければならない。\n",
        "\n",
        "# フィールド名は単一構築子の型 (レコード型とよばれる) に限るものではない。\n",
        "# 複数の構築子をもつ型では、フィールド名を用いての選択や更新の操作は実行時エラーを引き起こす可能性がある。\n",
        "# これは、空リストにhead を適用したときと似ている。\n",
        "\n",
        "# フィールドラベルは一般の変数やクラスメソッドとトップレベルの名前空間を共有する。\n",
        "# スコープのなかで同じ名前のフィールド、1つ以上のデータ型で使うことはできない。\n",
        "# しかし、1つのデータ型の中でなら、型付けが同じあるかぎり、1つ以上の構築子のなかで、使うことができる。\n",
        "# たとえば、次のようなデータ型のなかで、\n",
        "\n",
        "data T = C1 {f :: Int, g :: Float} | C2 {f :: Int, h :: Bool}\n",
        "\n",
        "# フィールド名 f は型 T の両方の構築子に適用されている。\n",
        "# つまり、もし、x の型が T ならば、x {f=5} は T 内のどちらの構築子が生成した値に対しても機能する。\n",
        "\n",
        "# フィールド名が代数的データ型の基本性質を変えることはない。\n",
        "# フィールド名は、データ構造の構成要素にアクセスするのに位置を手がかりにするより、\n",
        "# 名前を手がかりにするために用意された、便宜的な構文にすぎない。この構文\n",
        "# のおかげで、多くの構成要素をもつ構築子の扱いが簡単になる。\n",
        "# フィールドは構築子へのそれぞれの参照を変更することなく追加したり削除したりすることができるからである。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aI5RDS1jnYJU"
      },
      "source": [
        "# 正格データ構築子\n",
        "\n",
        "# Haskell ではデータ構造は一般的に遅延性をもつ。\n",
        "# 構成要素は必要になるまで評価されない。\n",
        "# この性質のおかげで、データ構造はもし評価されるとエラーあるいは停止できないような要素を含むことができる。\n",
        "# 遅延データ構造は Haskell の表現力を強化し、Haskellのプログラミングスタイルの要になる。\n",
        "\n",
        "# 内部的には、遅延データオブジェクトの各フィールドはサンク (thunk) とよくいわれる構造に包みこまれている。\n",
        "# サンクはフィールド値を定義した計算をカプセル化したもの。\n",
        "# 値が必要にならないかぎり、サンクの中へ入ることはない。\n",
        "# エラー (_|_ )を含むサンクがあってもデータ構造の他の要素には影響しない。\n",
        "# たとえば、タプル ('a',_|_) は完全に正しい Haskell の値である。\n",
        "# この 'a' はこのタプルのもう一方の要素にかまうことなく、使うことができる。\n",
        "# 他のプログラミング言語は遅延性ではなく正格性をもっている。\n",
        "# すなわち、データ構造のすべての要素はそのデータ構造に入れる前に値にまで簡約される。\n",
        "\n",
        "# サンクにはいろいろなオーバヘッドがついてまわる。\n",
        "# サンクを構成するにも、それを評価するにも時間がかかる。\n",
        "# ヒープの領域をとるし、そのサンクの評価のために必要な別の構造を確保するため、\n",
        "# ガーベッジコレクタを起動することもある。\n",
        "# こうしたオーバヘッドを回避するために、正格性フラグを data 宣言で使いる。\n",
        "# こうして、選択的に遅延性を抑制することで、指定した構築子のフィールドをただちに評価する。\n",
        "# data 宣言の中で、! でマークされたフィールドは、サンクに入れて遅延するのではなく、\n",
        "# 構造が生成される際に、直ちに評価される。この正格性フラグを用いるほうがよい状況はいくつかある。\n",
        "\n",
        "# * プログラム実行中に必ず評価されることが確定している構成要素\n",
        "# * 簡単に評価できて絶対にエラーを起こさないことが確定している構成要素\n",
        "# * 部分的に未定義の値であると意味のない型\n",
        "\n",
        "# たとえば、複素数のライブラリが定義している Complex 型は次のようになっている。\n",
        "%%script false\n",
        "\n",
        "data RealFloat a => Complex a = !a :+ !a\n",
        "\n",
        "# 構築子 :+ の中置定義に注意!\n",
        "# この定義では、2つの構成要素にマークがついている。\n",
        "# 複素数の実数部と虚数部は正格性をもつようにマークされている。\n",
        "# これは、複素数のよりコンパクトな表現だが、たとえば、1 :+ _|_ のように未定義の構成要素があっ\n",
        "# た場合、全体が未定義 (_|_)になってしまうという代償をはらっている。\n",
        "# しかし、部分的にしか定義されていない複素数が必要になることは実際にはありえないので、\n",
        "# 効率のよい表現を達成するために正格性フラグを使用するのは意味のあることである。\n",
        "\n",
        "# 正格性フラグはメモリリーク(もはや使うことはないのにガーベッジコレクタに\n",
        "# 回収されない構造)を解決するために使うこともできる。\n",
        "\n",
        "# 正格性フラグ ! は data 宣言のなかでのみ使われる。\n",
        "# そのほかの型シグネチャーや型定義では使えない。\n",
        "# 関数の引数に対して正格性をもつようにマークをつける方法はない。\n",
        "# しかし、seq あるいは !$ という関数を使用することで同じ効果が得られる\n",
        " \n",
        "# 正格性フラグの使い方の正確なガイドラインを示すのは難しい。\n",
        "# 注意して使用しなければならない。\n",
        "# 遅延性は Haskell の基本的な特徴の 1つであって、\n",
        "# そこへ正格性フラグをつけ加えることは無限ループの発見を困難なものにし、ほかの予期せぬ結果をまねきかねない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "K7nqmV_H5zjT"
      },
      "source": [
        "# 入出力\n",
        "# Haskell の I/O システムは純粋に関数的である。\n",
        "# 命令型の言語では、プログラムは環境を変更するアクションを通じて進行する。\n",
        "# 典型的なアクションには、グローバル変数を読むこと、設定すること、ファイルへの書き込み、\n",
        "# 入力の読み込み、ウィンドウのオープンなどがある。\n",
        "# このようなアクションは Haskell の言語のコアの部分からは、切離されている。\n",
        "\n",
        "# Haskell の I/O システムは数学のモナド (monad) を基礎として築かれている。\n",
        "# しかし、I/O システムを使う上で底流にあるモナドの理論を理解する必要はない。\n",
        "# モナドの理論は、I/O にたまたま適合した概念上の構造である。\n",
        "# 単純な算術演算を実行するのに群論を理解する必要がないのと同じで、\n",
        "# Haskell の I/O を実行するのにモナド理論を理解する必要はない。\n",
        "\n",
        "# I/O システムを構築しているモナド演算子は別の目的にも使用される。\n",
        "# ここでは、モナドという用語を使うのは避けて、I/O システムの使い方に集中する。\n",
        "# I/O モナドを単に抽象データ型だと考えておくのがいいだろう。\n",
        "\n",
        "# アクションは Haskell では呼出すのではなく定義するものである。\n",
        "# アクションの定義を評価することでは、実際のアクションは起こらない。\n",
        "# むしろ、アクションは、ここまで考えてきた式の評価というものの外側で起こることである。\n",
        "\n",
        "# アクションはシステムプリミティブとして定義されるようにアトミックなものであり、\n",
        "# また、一連のアクションの合成でもある。\n",
        "# I/O モナドは複合アクションを構成するためのプリミティブをふくみ、\n",
        "# 他の言語では ; (セミコロン) を使って、文を一列に並べるのと同じように構成する。\n",
        "# このモナドの機構はプログラムのなかのアクションをくっつける糊のような役目をする。\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "agn1k1GM_Vks"
      },
      "source": [
        "# I/O の基本演算\n",
        "# 各 I/O のアクションはそれぞれ値を返する。\n",
        "# 型システムにおいては、返り値 は、IO という「タグ」がつけられている。\n",
        "# これはアクションを他の 値と区別するためである。\n",
        "# たとえば、関数 getChar の型は、次のようなものである。\n",
        "%%script false\n",
        "\n",
        "getChar :: IO Char\n",
        "\n",
        "# この IO Char は getChar が呼出されたときに、文字を返すなんらかの動作をする、ということを示している。\n",
        "# 意味のある値を 返さないアクションにたいしてはユニット型 () を用いる。\n",
        "# たとえば、関数 putChar の型は、次のようなものである。\n",
        "\n",
        "putChar :: Char -> IO ()\n",
        "\n",
        "# この関数は引数として文字を取るが、特に意味のある値は返さない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5jZNjKizEwgZ"
      },
      "source": [
        "\n",
        "# アクションは、演算子 >>= (`bind`)を使って、順序付けをする。\n",
        "# この演算子を直接使わず、do 記法という糖衣構文を使うこともできる。\n",
        "# この記法では、順序制御の演算子は構文の後に隠れるので、伝統的な言語に近くなる。\n",
        "# do 記法は簡単に >>= に展開することができる。\n",
        "\n",
        "# キーワード do により順に実行される文のならびが導入される。\n",
        "# 文はアクションであるとともに、<- を使ってアクションの結果に束縛されたパターンであり、\n",
        "# let を使った局所的な定義の集合でもある。\n",
        "# do 記法は let や where と同じく、レイアウトを使いる。\n",
        "# 適正なインデントをつかえば、波括弧とセミコロンを省略することができる。\n",
        "# 次のは一文字よみこみそれを印字する簡単なプログラムである。\n",
        "\n",
        "main :: IO ()\n",
        "main = do c <- getChar\n",
        "          putChar c\n",
        "\n",
        "# main の使い方は重要である。\n",
        "# main は (C の main 関数と同様に) Haskell のプログラムのエントリポイントとして定義されている。\n",
        "# main は IO 型でなければならない。ふつうは IO () である。\n",
        "# main は Main モジュールのなかだけで特別な意味をもつ。\n",
        "# 上のプログラムは順に 2 つのアクションを実行する。\n",
        "# 最初に、一文字に読み込み、その結果を変数 cへ束縛する。\n",
        "# それからその文字を印字する。\n",
        "# let 式とはちがい、<- で定義した変数は、そのあとに続く文のなかでのみ有効である。\n",
        "\n",
        "# do を用いて、アクションを起動し、その結果を知ることができるが、\n",
        "# 一連のアクションから結果を返すのはどうするか。\n",
        "# たとえば、一文字読み込んでその文字が 'y' であれば、True を返す ready という関数を考えてみよう。\n",
        "\n",
        "%%script false\n",
        "\n",
        "ready :: IO Bool\n",
        "ready = do c <- getChar\n",
        "            c == 'y' -- ダメ!!!\n",
        "\n",
        "# この関数は、do のなかの 2つめの文が、アクションではなく、単なる真理値なので、動作しない。\n",
        "# この真理値をとって、なにもしないが、結果としてこの真理値を返すアクションを生成しなければならない。\n",
        "# return 関数はまさにこれを行う。\n",
        "\n",
        "return :: a -> IO a\n",
        "\n",
        "# この return 関数はプリミティブの実行を完成させる。\n",
        "# ready の最後の行は、return (c == 'y') でなくてはならない。\n",
        "\n",
        "# では、もっと複雑な I/O 関数を見てみよう。\n",
        "# まず、getLine 関数である。\n",
        "\n",
        "getLine     :: IO String\n",
        "getLine     =  do c <- getChar\n",
        "                  if c == '\\n'\n",
        "                       then return \"\"\n",
        "                       else do l <- getLine\n",
        "                               return (c:l)\n",
        "\n",
        "# else 節にある、2つめの do に注目。\n",
        "# それぞれの do は一本の文の列を構成している。\n",
        "# if のように介入的な言語要素はその先のアクション列を導入するのに新たな doを使う必要がある。\n",
        "\n",
        "# return 関数は真理値などの一般の値を I/O アクションの領域に入れる。\n",
        "# その逆はどうか。\n",
        "# いくつかの I/O アクションをふつうの式のなかで起動できるか。\n",
        "# たとえば、x + print y を式のなかに入れて、y がその式の評価の結果として印字されるようにすることはできるか。\n",
        "# できない。\n",
        "# 純粋関数型のコードのなかで、こっそりと命令型の世界にしのび込むことはできない。\n",
        "# 命令型の世界に「影響される」値にはそれとわかるタグがついている必要がある。\n",
        "\n",
        "# 次のよう な関数\n",
        "\n",
        "f :: Int -> Int -> Int\n",
        "\n",
        "# は絶対に I/O を行うことはできない。\n",
        "# それは IO が返り値にあらわ れていないからである。\n",
        "# このことは、デバッグのときに文字通りコード全体にわたって\n",
        "# print 文を埋めこむことの多いプログラマにとっては悩みの種だろう。\n",
        "# 実際のところは、この問題に対処するために、いくつかの安全ではない関数が用意されている。\n",
        "# しかし、これらは、上級プログラマにとっておいた方がよいものである。\n",
        "# デバッグ用のパッケージ (Trace など) は往々にして「禁じ手」となっている関数を気前よく使っている。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MsQOZjrw_b98"
      },
      "source": [
        "# アクションをつかったプログラミング\n",
        "# I/O アクションはふつうの Haskell の値である。\n",
        "# 関数にわたされることもあるだろうし、なかに入れることも、Haskell のほかの値とおなじようにできる。\n",
        "# 次にアクションのリストを考えてみよう。\n",
        "%%script false\n",
        "\n",
        "todoList :: [IO ()]\n",
        "\n",
        "todoList = [putChar 'a',\n",
        "            do putChar 'b'\n",
        "               putChar 'c',\n",
        "            do c <- getChar\n",
        "               putChar c]\n",
        "\n",
        "# このリストは実際にはアクションを起動することはない。\n",
        "# アクションを保持しているだけである。\n",
        "# これらのアクションを 1つのアクションにまとめるのは、sequence_ のような関数が必要である。\n",
        "\n",
        "sequence_        :: [IO ()] -> IO ()\n",
        "sequence_ []     =  return ()\n",
        "sequence_ (a:as) =  do a\n",
        "                       sequence as\n",
        "\n",
        "# この関数は、なにもせずに、do x;y を x >> y へ展開する。\n",
        "\n",
        ":t (>>)\n",
        "(>>) :: Monad m => m a -> m b -> m b\n",
        "\n",
        ":i (>>)\n",
        "class Applicative m => Monad (m :: * -> *) where\n",
        "  (>>) :: m a -> m b -> m b\n",
        "        -- Defined in ‘GHC.Base’\n",
        "infixl 1 >>\n",
        "\n",
        "# このパターンの再帰は、foldr 関数でとらえることができる。\n",
        "# さらによい sequence_ の定義は以下のようなものである。\n",
        "\n",
        "sequence_        :: [IO ()] -> IO ()\n",
        "sequence_        =  foldr (>>) (return ())\n",
        "\n",
        "# この do 記法は便利なツールだが、この場合には、その底流にあるモナド演算子 >> を使うほうが適当である。\n",
        "# do の構築の基になる演算子を理解することは、Haskell プログラマにとって役にたつこと である。\n",
        "\n",
        "# sequence_ 関数は、putStr を putChar をつかって構築するときにも使える。\n",
        "\n",
        "putStr                  :: String -> IO ()\n",
        "putStr s                =  sequence_ (map putChar s)\n",
        "\n",
        "# Haskell と伝統的な命令型の言語との違いの 1つがこの putStr にみてとれる。\n",
        "# 命令型の言語では、命令型の putChar を文字列上でマッピングするだけで印字が可能である。\n",
        "# しかし、Haskell では map 関数はアクションを実行しない。\n",
        "# そのかわり、それぞれ、文字列の一文字に対応するアクションのリストを生成する。\n",
        "# sequence_ のなかの畳み込み演算は >>関数をつかって、それぞれの個別の演算を 1つの演算にまとめる。\n",
        "# ここでも return () は必要である。\n",
        "# foldr は一連のアクションの最後になにもしないアクションを必要とする。\n",
        "\n",
        "#  Prelude やライブラリには I/O アクションの順序付けに便利な関数がたくさんある。\n",
        "# これらの関数はだいたいのものが、任意のモナド用に汎用化されている。\n",
        "# Monad m => という文脈を含む関数はどれも IO 型で使える。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7azDhnQ2Jvw2"
      },
      "source": [
        "# 例外処理 exception handling\n",
        "# ここまでは、I/O 演算中の例外の問題を避けてきた。\n",
        "# もし、getChar がファイルの最後にあたったら、どうなるか。\n",
        "# _|_ に対してはエラー error という用語を使う。\n",
        "# これは、停止しない、あるいは、パターンマッチが失敗した、というような回復不可能な場合に使う。\n",
        "# 一方、例外 exception は、I/O モナド内で捕捉可能および処理可能なものである。\n",
        "# I/O モナド中での、「file not found」などの例外的状況を扱うには、standard ML\n",
        "# の入出力にある機能にあるような、ハンドリング機構を使いる。\n",
        "# 特別な構文や意味論を用いることはない。\n",
        "# 例外処理は、I/Oの順序付け演算子の定義の一部になっている。"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4THNFokY_Z1p"
      },
      "source": [
        "# 例外は特別なデータ型 IOError としてコード化されている。\n",
        "# この 型は I/O モナド中でおこりうるすべての例外を表わしている。\n",
        "# これは一種の 抽象型で、ユーザが利用可能な IOError の構築子はない。\n",
        "# IOError 型の値に対して使うことができる述語がいくつかある。\n",
        "\n",
        "%%script false\n",
        "\n",
        "isEOFError :: IOError -> Bool\n",
        "\n",
        "# という関数はエラーが、ファイル終端条件でひきおこされたものかどうかを判定する。\n",
        "# IOError を抽象型とすることで、明示的なデータ型の変更なしで、新しい種類のエラーをシステムに導入することができる。\n",
        "# この isEOFError 関数は IO ライブラリのなかで定義されているので、明示的にインポートする必要がある。\n",
        "\n",
        "# 例外ハンドラ は IOError -> IO a という型になる。\n",
        "# catch 関数は例外ハンドラをアクションあるいはアクションの集まりと関連づける。\n",
        "\n",
        "catch                     :: IO a -> (IOError -> IO a) -> IO a\n",
        "\n",
        "# catch の引数はアクションとハンドラである。\n",
        "# アクションが成功すれば、ハンドラを起動せずにその結果だけを返する。\n",
        "# エラーが起これば、IOError 型の値をハンドラに渡し、そのハンドラに関連づけられているアクションを起動する。\n",
        "# 例として、エラーにであうと改行を返す getChar をあげておこう。\n",
        "\n",
        "getChar'                :: IO Char\n",
        "getChar'                =  getChar `catch` (\\e -> return '\\n')\n",
        "\n",
        "# これは、すべてのエラーについて同じ処理をしているので、あまり洗練された実装ではない。\n",
        "# もし、ファイル終端になった場合だけをわけたい場合には、エラーの種類を確かめなければならない。\n",
        "\n",
        "getChar'                :: IO Char\n",
        "getChar'                =  getChar `catch` eofHandler where\n",
        "    eofHandler e = if isEofError e then return '\\n' else ioError e\n",
        "\n",
        "# ここで使われている ioError 関数は次の例外ハンドラに例外を投げる。\n",
        "# ioError の型は、\n",
        "\n",
        "ioError :: IOError -> IO a\n",
        "\n",
        "# である。\n",
        "# これは、つぎの I/O アクションを実行するかわりに、\n",
        "# 制御を例外ハンドラに移すという点をのぞけば、return と類似している。\n",
        "# catch の入れ子になった呼び出しも可能である。\n",
        "# 入れ子になった catch の呼び出しは、入れ子になった例外ハンドラを生成する。\n",
        "# この例を、getChar' を使って getLine を再定義することで示そう。\n",
        "\n",
        "getLine'        :: IO String\n",
        "getLine'        = catch getLine'' (\\err -> return (\"Error: \" ++ show err))\n",
        "        where\n",
        "                   getLine'' = do c <- getChar'\n",
        "                         if c == '\\n' then return \"\"\n",
        "                                            else do l <- getLine'\n",
        "                                                    return (c:l)\n",
        "\n",
        "\n",
        "# 入れ子になったエラーハンドラは getChar' がファイル終端を捕捉することを可能にしている。\n",
        "# 一方で、ほかのエラーがおこると \"Error: \" ではじまる文字列が、getLine' から戻る。\n",
        "\n",
        "# Haskell では利便性確保のために、プログラムの最上位レベルにプログラムを停止し、\n",
        "# 例外を印字する例外ハンドラが用意されている。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sxwX91N1_Ptk"
      },
      "source": [
        "# ファイル、チャネル、ハンドル\n",
        "# I/O モナドや例外処理機構が提供するもののほか、\n",
        "# Haskell の I/O は、他の言語にあるものとほとんど同じ機構が備わっている。\n",
        "\n",
        "# ファイルをオープンするとハンドル (型は Handle) が生成されて、これを使って I/O のやりとりをする。\n",
        "# このハンドルをクローズすると、それに関連付けられているファイルがクローズする。\n",
        "%%script false\n",
        "\n",
        "type FilePath         =  String  -- path names in the file system\n",
        "openFile              :: FilePath -> IOMode -> IO Handle\n",
        "hClose                :: Handle -> IO () \n",
        "data IOMode           =  ReadMode | WriteMode | AppendMode | ReadWriteMode\n",
        "\n",
        "# ハンドルはチャネルにも関連付けられる。\n",
        "# チャネルはファイルとは直接結びつかないコミュニケーションポートである。\n",
        "# いくつかのチャネルハンドルは定義済になっている。\n",
        "# たとえば、stdin (標準入力)、stdout (標準出力)、stderr (標準エラー) である。\n",
        "# hGetChar や hPutChar の文字単位の I/O演算は、引数のひ とつとして、ハンドルをとる。\n",
        "# さきほどの getChar 関数は次のように定義されている。\n",
        "\n",
        "getChar = hGetChar stdin\n",
        "\n",
        "# Haskellでは内容全体を 1つの文字列として返すファイルやチャネルが使える。\n",
        "\n",
        "getContents :: Handle -> IO String\n",
        "\n",
        "# 実行上、getContents はチャネルやファイルの全内容を一度にすべて\n",
        "# 読みこまなければならず、メモリや実行時間が足りなくなるということが起こりそうに見える。\n",
        "# しかし、それは間違いである。\n",
        "# 鍵となる要点は、getContents は文字の「遅延」(すなわち非正格)リストを返すということである。\n",
        "# このリストの要素は、他のリストと同様に、「必要になってはじめて」読み込まれるのである。\n",
        "# この要求駆動の振舞いの実装は、計算側からの要求があるたびに、\n",
        "# 一度に一文字づつファイルから読みこむことで実現する。\n",
        "\n",
        "# 次の例はファイルをコピーする Haskell のプログラムである。\n",
        "\n",
        "main = do fromHandle <- getAndOpenFile \"Copy from: \" ReadMode\n",
        "          toHandle   <- getAndOpenFile \"Copy to: \" WriteMode \n",
        "          contents   <- hGetContents fromHandle\n",
        "          hPutStr toHandle contents\n",
        "          hClose toHandle\n",
        "          putStr \"Done.\"\n",
        "\n",
        "getAndOpenFile          :: String -> IOMode -> IO Handle\n",
        "getAndOpenFile prompt mode =\n",
        "    do putStr prompt\n",
        "       name <- getLine\n",
        "       catch (openFile name mode)\n",
        "             (\\_ -> do putStrLn (\"Cannot open \"++ name ++ \"\\n\")\n",
        "                       getAndOpenFile prompt mode)\n",
        "\n",
        "\n",
        "# 遅延性のある getContents 関数を使うと、ファイルの内容全部を一度にメモリへ読み込む必要がなくなる。\n",
        "# もし、hPutStr がバッファとして固定長の文字列を採用するなら、一度にメモリへ読み込むには、\n",
        "# 入力ファイル 1 ブロック分だけが必要である。\n",
        "# 入力ファイルは最後の文字が読み出されれば、暗黙のうちにクローズされる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UeqHjVcr_KIA"
      },
      "source": [
        "# Haskell と命令型 imperativeプログラミング\n",
        "# 最後に、I/O プログラミングは重大な問題を表面化したことについて考える。\n",
        "# このスタイルは従来の命令型のプログラミングとさしてかわらないではないということである。\n",
        "\n",
        "# たとえば、getLine 関数、\n",
        "%%script false\n",
        "\n",
        "getLine         = do c <- getChar\n",
        "                     if c == '\\n'\n",
        "                          then return \"\"\n",
        "                          else do l <- getLine\n",
        "                                  return (c:l)\n",
        "\n",
        "これは、つぎの命令型のコードと酷似している。\n",
        "\n",
        "function getLine() {\n",
        "  c := getChar();\n",
        "  if c == `\\n` then return \"\"\n",
        "               else {l := getLine();\n",
        "                     return c:l}}\n",
        "\n",
        "# ということは、結局、Haskell は単に命令型の車輪を再発明しただけなのか。\n",
        "\n",
        "# ある意味では、そのとおりである。\n",
        "# I/O モナドは Haskell のなかに小さな命令型のサブ言語を構成している。\n",
        "# それゆえ、プログラムの I/O の構成要素は従来の命令型のコードにそっくりになるのである。\n",
        "# しかし、1つ大きな違いがある。\n",
        "# これを扱うのに特別な意味論を必要としないということである。\n",
        "# 特に、Haskell における等式論証の仕組みはなんら損われていない。\n",
        "# プログラム中のモナドのコードの命令型のフィーリングは\n",
        "# Haskell の関数的な側面をそこなうものではない。\n",
        "# 経験を積んだ関数プログラマはプログラム中の命令型の構成要素を最小限にし、\n",
        "# トップレベルで順序付けを最小にし、それについてだけ、I/O モナドを使用することができる。\n",
        "# モナドはプログラムの関数的な構成要素と命令的な構成要素を綺麗にわける。\n",
        "# 一方で、関数的なサブセットをもつ命令型の言語では純粋に関数的な世界と命令的な世界をへだて\n",
        "# るものがハッキリとは定義されていない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t5BIA5BL4Yh6"
      },
      "source": [
        "# 標準クラス"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zT25Yq303ztF"
      },
      "source": [
        "# 8 Haskell の標準クラス\n",
        "# このセクションでは、Haskellの定義済標準型クラスを紹介する。\n",
        "# 一部のクラスについては Haskell の標準ライブラリの一部になっている。\n",
        "\n",
        "# 同値クラスと順序クラス\n",
        "# Eq クラスと Ord クラスについては既に述べた。\n",
        "#  Prelude にある Ord クラスの定義は、以前に定義した単純なものよりも、複雑である。\n",
        "# 特に、compare メソッドは、以下のようになっている。\n",
        "%%script false\n",
        "\n",
        "data Ordering           =  EQ | LT | GT \n",
        "compare                 :: Ord a => a -> a -> Ordering\n",
        "\n",
        "# compare メソッドがあれば、このクラスの他のすべてのメソッドは定義できる。\n",
        "# Ord のインスタンスを生成するにはこの方法が一番すぐれている。\n",
        "\n",
        "# 列挙クラス\n",
        "# Enum クラスには数列表現の糖衣構文の底流にある一連の演算がある。\n",
        "# たとえば、数列式 [1,3..] は enumFromThen 1 3 を表わしている。\n",
        "# これで、Enum のインスタンスの型であればどの型に対しても、\n",
        "# この数列式を用いてリストの生成ができることがわかる。\n",
        "# Enum のインスタンスにはほとんどの数値型が含まれているばかりではなく、\n",
        "# Char 型も含まれており、['a'..'z'] はアルファベット順に並べた、小文字のリストを表す。\n",
        "# さらに、Color のよ うな、ユーザ定義の列挙型を Enum のインスタンスとして宣言できる。\n",
        "# それは次のようになる。\n",
        "\n",
        "[Red .. Violet] => [Red, Green, Blue, Indigo, Violet]\n",
        "\n",
        "# ここで、注意すべきことは、このような列は、算術的であるということである。\n",
        "# すなわち、各値の増分はそれが数値であろうとなかろうと、一定であるということである。\n",
        "# Enum のほとんどのインスタンスは固定長の整数上に写像することが可能である。\n",
        "# この目的のために、fromEnum や toEnum が用意されており、Int と Enum\n",
        "# のインスタンスの間での変換 をおこなう。\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Yablo8eK6LKJ"
      },
      "source": [
        "# Read クラスと Show クラス\n",
        "# Show クラスのインスタンスは文字列への変換 (典型的な目的はI/O) が可能な型である。\n",
        "# Read クラスには、その値を表現する文字列を構文解析する演算が用意されている。\n",
        "# Show クラスの最も単純な関数は show である。\n",
        "%%script false\n",
        "\n",
        "show :: (Show a) => a -> String\n",
        "\n",
        "# show は当然、対応する型のあらゆる値をとり、その表現として、文字列を返す。\n",
        "# たとえば、show (2+2) は \"4\" を返す。\n",
        "# このように正しく動作するものについてはいいが、それぞれの型のいろいろな値について、\n",
        "# 複雑な表現が必要になる。\n",
        "# たとえば、\n",
        "\n",
        "\n",
        "\"The sum of \" ++ show x ++ \" and \" ++ show y ++ \" is \" ++ show (x+y) ++ \".\"\n",
        "\n",
        "# のような場合、それぞれの文字列を連結しているのでは、能率的ではない。\n",
        "# ことに、二分木の文字列表現を考えてみよう。\n",
        "# 入れ子になった部分木を表示するために適当なマークをつけてたり、左の枝と右の枝をわける印をつけたりする。\n",
        "\n",
        "showTree                :: (Show a) => Tree a -> String\n",
        "showTree (Leaf x)       =  show x\n",
        "showTree (Branch l r)   =  \"<\" ++ showTree l ++ \"|\" ++ showTree r ++ \">\"\n",
        "\n",
        "# (++) は左側の引数の長さの線型で効く計算量をもつので、\n",
        "# showTree は木のサイズの 2 次で効く計算量になる。\n",
        "\n",
        "# 線型の複雑さを持つように、関数 shows を以下のように定義する。\n",
        "\n",
        "shows                   :: (Show a) => a -> String -> String\n",
        "\n",
        "# この shows は印字可能な値と文字列をとり、前の部分にその値の文字列表現を連結した文字列を返す。\n",
        "# 2つめの引数は一種の文字列積算子になる。\n",
        "# show は shows にナル積算子をあたえたものとして定義することができる。\n",
        "# これは Show クラスの定義のなかの show のデフォルトの定義となる。\n",
        "\n",
        "show x = shows x \"\"\n",
        "\n",
        "# shows を使って、showTree のより効率のよい定義をすることができる。\n",
        "# このときも、文字列積算子引数をもたせる。\n",
        "\n",
        "showsTree               :: (Show a) => Tree a -> String -> String\n",
        "showsTree (Leaf x) s    =  shows x s\n",
        "showsTree (Branch l r) s=  '<' : showsTree l ('|' : showsTree r ('>' : s))\n",
        "\n",
        "# この定義により効率の問題は解決した。\n",
        "# (showsTree の計算量は 線型のオーダである) \n",
        "# しかし、この関数の表現をさらに改良することができる。\n",
        "# まず、型シノニムをつくってみよう。\n",
        "\n",
        "type ShowS = String -> String\n",
        "\n",
        "# この型は、なにかの文字列表現に積算子文字列を連ねた文字列を返す関数の型である。\n",
        "# つぎに、積算子をもちまわり、長い文字列の構築の右端での括弧の蓄積を\n",
        "# 回避するために、関数合成を使うことができる。\n",
        "\n",
        "showsTree               :: (Show a) => Tree a -> ShowS\n",
        "showsTree (Leaf x)      =  shows x\n",
        "showsTree (Branch l r)  =  ('<':) . showsTree l . ('|':) . showsTree r . ('>':)\n",
        "\n",
        "# コードを整理することよりもさらに重要なことが、このプログラム変換によってあきらかになった。\n",
        "# それは、オブジェクトレベルでの表現から関数レベルの表現への変換である。\n",
        "# ここで、showsTree の型付 けは、tree から表示関数への写像ということができる。\n",
        "# ('<' :) あるいは (\"a string\" ++) のような関数はプリミティブな表示関数で、\n",
        "# 関数合成を用いて、より複雑な関数を構築することができる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0AVRzQe69qAm"
      },
      "source": [
        "# さて、tree を文字列に換える話に戻ろう。\n",
        "# こんどは逆の問題を考える。\n",
        "# 基本のアイディアは、型 a に対する構文解析子である。\n",
        "# 型 a の構文解析子は文字列を引数としてとり、(a,String) のリストを返す関数である。\n",
        "# Prelude にはこのような関数の型シノニムが備えられている。\n",
        "%%script false\n",
        "\n",
        "type ReadS a = String -> [(a,String)]\n",
        "\n",
        "# ふつうの状況では、構文解析子は単一の要素を含むリストを返す。\n",
        "# この要素は、入力文字列から読み込んだ型 aの値と、そのあと構文解析される、残りの文字列の組である。\n",
        "# もし、構文解析が不可能であれば、結果は空リストである。\n",
        "# もし、2つ以上の構文解析が可能であるなら (この場合は曖昧な構文ということになる)、\n",
        "# 結果は、2 つ以上の組を含むリストになる。\n",
        "# 標準関数の reads は Read のあらゆるインスタンスに対応する構文解析子関数である。\n",
        "\n",
        "reads :: (Read a) => ReadS a\n",
        "\n",
        "# この関数を使って、showTree を使って作った、二分木の文字列表現を構文解析する関数を定義することができる。\n",
        "# リストの内包表記はこのような構文解析関数を構築するのに便利なイディオムである。\n",
        "# (モナドや構文解析結合子を使ったもっとエレガントな方法もある。\n",
        "# これらは、ほとんどの Haskellシステムとともに配布される標準の構文解析ライブラリの一部となっている)\n",
        "\n",
        "readsTree               :: (Read a) => ReadS (Tree a)\n",
        "readsTree ('<':s)       =  [(Branch l r, u) | (l, '|':t) <- readsTree s,\n",
        "                                              (r, '>':u) <- readsTree t ]\n",
        "readsTree s             =  [(Leaf x, t)     | (x,t)      <- reads s]\n",
        "\n",
        "# すこし、時間をかけてこの関数の定義を詳細にみていこう。\n",
        "# 考慮すべき状況が2つある。\n",
        "# もし、構文解析の対象となる文字列の最初の文字が '<' の場合、これは、枝の表現に違いない。\n",
        "# そうでなかった場合、これは葉の表現である。\n",
        "# 最初の場合は、開き三角括弧につづく入力文字列 の残りの部分を s とすると、\n",
        "\n",
        "# 可能な構文解析はなんであれ、Branch l r となり、残りの文字列は、u となり、以下の条件に従う。\n",
        "\n",
        "# 1. 木 l は文字列 s の最初から構文解析されたものとすることができる。\n",
        "# 1. ( l の文字列表現に続く)残りの文字列は '|' で始まる) この文字列の先頭をのぞく部分を t とする。\n",
        "# 1. 木 r は文字列 t の最初から構文解析されたものとすることができる。\n",
        "# 1. この構文解析の残りの文字列は '>' で始まる。この文字列の先 頭をのぞく部分は u である。\n",
        "\n",
        "# リスト内包表記のパターンマッチングの組み合わせによる表現力に注目する。\n",
        "# リスト内包表記されたメインの式であたえられている構文解析結果の形式は、\n",
        "# まず、上にあげた 2 つの条件を最初の生成部 ((l,'|':t) は、s の構文解析結果のリストから引出されている) \n",
        "# によって表現されている。\n",
        "# 残りの条件は、2 つめの生成部によって表現されている。\n",
        "# 上の 2つめの定義等式は葉の表現に対する構文解析は、この木の要素の表現を構文解析し、\n",
        "# その結果に構築子 Leaf を適用して、値を得る、という意味である。\n",
        "\n",
        "# とりあえず、(色々な型があるなかで) Integer の Read (および Show)\n",
        "# インスタンスがあって、期待通りの振舞いをする reads が備わっていることを受容する。\n",
        "# つまりは以下のとおりである。\n",
        "\n",
        "(reads \"5 golden rings\") :: [(Integer,String)] => [(5, \"golden rings\")]\n",
        "\n",
        "# これが理解できれば、次の評価を確認できるはずである。\n",
        "\n",
        "\n",
        "readsTree \"<1|<2|3>>\"\t=>\t[(Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), \"\")]\n",
        "readsTree \"<1|2\"\t=>\t[]\n",
        "\n",
        "# いま定義した readsTree には、2 つの欠点がある。\n",
        "#  1つは、この構文解析器はたいへん厳格にできていて、木の表現の文字列の要素の前や間に空白を許さないというもの。\n",
        "# もう 1つは、区切の記号を構文解析する方法が葉の値の場合と部分木の場合ではすっかり違うということである。\n",
        "# この統一性のなさが、この関数の定義を読みづらいものにしている。\n",
        "# この 2つの問題を Prelude で定義されている字句解析器を使って解決することができる。\n",
        "\n",
        "lex :: ReadS String\n",
        "\n",
        "# lex は通常は、文字列の組の単一要素のリストを返する。\n",
        "# その組は、入力の最初の字句と入力の残りである。\n",
        "# ここでの字句のルールは、Haskell プログラムの字句のルールである。\n",
        "# lex は空白をスキップする。\n",
        "# もし、入力文字列が空あるいは空白およびコメントしか含まなければ、lex は [(\"\",\"\")] を返す。\n",
        "# もし、この意味で空ではなく、かつ、空白のつづく有効な字句ではじまっていない場合には、lex は [] を返す。\n",
        "\n",
        "# この字句解析器を使うと、木の構文解析器は次のようになる。\n",
        "\n",
        "readsTree               :: (Read a) => ReadS (Tree a)\n",
        "readsTree s             =  [(Branch l r, x) | (\"<\", t) <- lex s,\n",
        "                                              (l,   u) <- readsTree t,\n",
        "                                              (\"|\", v) <- lex u,\n",
        "                                              (r,   w) <- readsTree v,\n",
        "                                              (\">\", x) <- lex w         ]\n",
        "                           ++\n",
        "                           [(Leaf x, t)     | (x,   t) <- reads s       ]\n",
        "\n",
        "\n",
        "さて、ここで、readsTree と showsTree を使って、\n",
        "Read のインスタンス (Read a) => Tree a と Show のインスタンス (Show a) => Tree a を宣言してみよう。\n",
        "こうすれば、木の構文解析と表示用に Prelude にある総称的多重定義関数を利用することができる。\n",
        "さらに、構成要素に木を含むほかの多くの型の構文解析や表示ができるようになる。\n",
        "たとえば、[Tree Integer] のようなものである。\n",
        "ここでわかるように、readsTree と showsTree はほぼ、Show および Read のメソッドの型を満している。\n",
        "showsPrec と readsPrec のメソッドは、shows と reads をパラメータ化したものである。\n",
        "追加されたパラメータは、優先レベルである。\n",
        "これは、中置構築子が式に含まれている場合に正しく、括弧付けをおこなうために使用する。\n",
        "Tree のような型に対しては優先度は無視される。\n",
        "Show と Read のインスタンスとしての Tree は以下のようになる。\n",
        "\n",
        "instance Show a => Show (Tree a) where\n",
        "    showsPrec _ x = showsTree x\n",
        "\n",
        "instance Real a => Read (Tree a) where\n",
        "    readsPrec _ s = readsTree s\n",
        "\n",
        "# また、Show のインスタンスは showTree を使って、次のよ うに定義することもできる。\n",
        "\n",
        "instance Show a => Show (Tree a) where\n",
        "   show t = showTree t\n",
        "\n",
        "# しかし、これは、ShowS バージョンよりも効率の面で劣る。\n",
        "\n",
        "# Show クラスでは showsPrec と show の両方についてデフォルトのメソッドを定義しており、\n",
        "# ユーザはインスタンス 1つにつき、どちらかを定義すればいいようになっている。\n",
        "# これらのデフォルトメソッドは相互再帰的になっているので、インスタンス宣言のなかで、\n",
        "# これらの関数のどちらも定義しなかった場合、呼び出しの際にループを引き起こす。\n",
        "# Num のようなクラスの場合でも、このような「相互ロック性のデフォルトメソッド」がある。\n",
        "\n",
        "# (read . show) (これは恒等関数になるはず) をいくつかの 木に適用することで\n",
        "# Read および Show のインスタンスをテストすることができる。\n",
        "# ここで、read は reads を特殊化 したものである。\n",
        "\n",
        "read :: (Read a) => String -> a\n",
        "\n",
        "# 入力に対して、構文解析結果が唯一でない場合、あるいは、入力が、a の型の 1つの値に対して \n",
        "# 2つ以上の表現(あるいは、コメントや空白)を含むような場合には、この関数は失敗する。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "emzVH1SE6E7N"
      },
      "source": [
        "# 導出されたインスタンス derived instance\n",
        "\n",
        "# 5 節で紹介した木の Eq インスタンスについて思い出す。\n",
        "# このような宣言をいちいち書くのは単純だが、面倒である。\n",
        "# 葉の要素の型が同値型であることを要求しているのだから、2つの葉は同値の要素をもつ場合、\n",
        "# そして、その場合にかぎり同値であり、2つの枝は、その左の部分木と右の部分木がそれぞれ等しい場合、\n",
        "# かつ、その場合にかぎり等しいわけで、それ以外の場合、2つの木は同値でない。\n",
        "%%script false\n",
        "\n",
        "instance  (Eq a) => Eq (Tree a)  where\n",
        "    (Leaf x)     == (Leaf y)        =  x == y\n",
        "    (Branch l r) == (Branch l' r')  =  l == l' && r == r'\n",
        "    _            == _               =  False\n",
        "\n",
        "\n",
        "# 幸い、この面倒な作業を、新しい型の同値演算子が必要になるたびに繰り返す必要はない。\n",
        "# Eq インスタンスは、データ宣言でそのように指定すれば、自動的に導出される。\n",
        "\n",
        "data  Tree a            =  Leaf a | Branch (Tree a) (Tree a)  deriving Eq\n",
        "\n",
        "# deriving 節は暗黙のうちに、5 節にあるように Eq インスタンス宣言を生成する。\n",
        "# Ord、Enum、Ix、Read、Show の各インスタンスも同様に deriving 節を使って生成することができる。\n",
        "# [ここでは 2 つ以上のクラス名を指定することができる。その場合にはクラス\n",
        "# の名前リストは括弧でかこまれ、名前はそれぞれコンマで区切る必要がある。]\n",
        "# \n",
        "# Tree に対して導出された Ord インスタンスは Eq の場合にくらべていくぶん複雑である。\n",
        "\n",
        "instance  (Ord a) => Ord (Tree a)  where\n",
        "    (Leaf _)     <= (Branch _)      =  True\n",
        "    (Leaf x)     <= (Leaf y)        =  x <= y\n",
        "    (Branch _)   <= (Leaf _)        =  False\n",
        "    (Branch l r) <= (Branch l' r')  =  l == l' && r <= r' || l <= l'\n",
        "\n",
        "# ここでは、辞書順 を指定している。\n",
        "# 構築子は、data 宣言中でその出現の順に並べられている。\n",
        "# そして、構築子への引数は左から右へ と比較されていくる。\n",
        "# 組み込みのリスト型は意味論的には2つの構築子をもつ型と同じであることを思い出す。\n",
        "# 実際にこの完全な定義は\n",
        "\n",
        "data [a]        = [] | a : [a] deriving (Eq, Ord)     -- pseudo-code\n",
        "\n",
        "# である。(リストは、Textインスタンスでもあるが、これは導出されない) \n",
        "# リストに対して導出された Eq および Ord のインスタンスはごくふつうのものである。\n",
        "# 特に、文字のリストとしての文字列は、その基になる Char型の順序によって、並べられる。\n",
        "# 先頭部分文 字列はそれより長い文字列よりも小さいと判定する。\n",
        "# たとえば、\"cat\" < \"catalog\" である。\n",
        "\n",
        "# 実際問題として、Eq および Ord のインスタンスは、ほとんどの場合、自動的に導出され、ユーザーが定義する必要はない。\n",
        "# ユーザーが定義する場合、同値関係と全順序関係という代数的な性質を維持するように注意しながら、\n",
        "# 独自の同値述語や順序述語を定義しなければならない。\n",
        "\n",
        "# (==) 述語をユーザー定義すると、プログラムを読むものを困惑させ、手動あるいは自動的な、(==)\n",
        "# 述語が明白な同値性の近似であることに依存する、プログラム変換を困難なものにする。\n",
        "\n",
        "# とはいうものの、導出されるものとはちがう Eq あるいはOrd のインスタンスが必要な場合もある。\n",
        "# もっとも重要な例は、同じ抽象値をあらわす別の具体的な値となるような抽象型のインスタンスの例である。\n",
        "\n",
        "# 列挙型は導出された Enum のインスタンスを用いる。\n",
        "# ここで、この型の順序は data 宣言での構築子の出現順になる。\n",
        "# たとえば、\n",
        "\n",
        "data Day = Sunday | Monday | Tuesday | Wednesday\n",
        "         | Thursday | Friday | Saturday         deriving (Enum)\n",
        "\n",
        "# このとき、この型に対して導出されたインスタンスを用いた単純な例は次のようなものになる。\n",
        "\n",
        "\n",
        "[Wednesday .. Friday]\t=>\t[Wednesday, Thursday, Friday]\n",
        "[Monday, Wednesday ..]\t=>\t[Monday, Wednesday, Friday]\n",
        "\n",
        "# その構成要素が Read (Show) のインスタンスであるような 型なら、その型に対して \n",
        "# Read (Show) のインスタンスであることを導出することが可能である。\n",
        "# (標準の型のほとんどについては、Read および Show のインスタンスであることが、Prelude のなかで示されている。\n",
        "# 関数の型である (->) のような型の いくつかは、Show インスタンスではあるが、\n",
        "# それに対応した Read のインスタンスではない。\n",
        "# ) 導出された Show インスタンスで定義されるテキストでの表現は、\n",
        "# 対象となる型の Haskell での 定数式の見かけと整合性がある。\n",
        "# 例えば、型 Day について Show と Read をその deriving 節に加えると、\n",
        "\n",
        "show [Monday .. Wednesday] => \"[Monday,Tuesday,Wednesday]\"\n",
        "\n",
        "# を得ることができる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uIuaHwsSHNcv"
      },
      "source": [
        "# モナド monad"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eAgU9OOwHM3P"
      },
      "source": [
        "# モナドについて\n",
        "# はじめて Haskell にふれる多くのひとにとって モナド monad の概念は謎である。\n",
        "# Haskell ではモナドに頻繁に出会う。\n",
        "# I/O システムはモナドによって構成されているし、モナドのための特別な構文 ( do 式 )も用意されている。\n",
        "# また、モナドのためだけのモジュール も標準ライブラリに含まれている。\n",
        "# このセクションではモナドを使ったプログ ラミングについて詳細にみていく。\n",
        "\n",
        "# このセクションは他のセクションにくらべるとおそらく「やさしい」というわけにいかない。\n",
        "# ここでは、モナドをふくむ言語の特徴を示すだけではなく、もっと壮大な絵を明かにしようと思う。\n",
        "# なぜモナドがこれほど重要なツー ルであり、どのようにこれを使うか、ということである。\n",
        "# だれにとっても、わかるモナドの説明は、これだ、というものはない。\n",
        "# 詳細な説明は、haskell.org から辿れる。\n",
        "# モナドをつかった、実際のプログ ラミング入門としてよい文献として\n",
        "# Wadler の Monads for Functional Programming をあげておく。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tQhJ6dVQUBSe"
      },
      "source": [
        "# モナドのクラス\n",
        "# Prelude には Haskell で使うモナドを定義したクラスがいくつもある。\n",
        "# これらのクラスは圏論 category theory におけるモナドの構成を基礎としている。\n",
        "# 圏論の用語はモナドのクラスや演算にその名前を残しているが、\n",
        "# モナドのクラスの使い方を直観的に理解するにはこういった抽象数学に通じてい る必要はない。\n",
        "\n",
        "# モナドは IO のような多相型の上に構成される。\n",
        "# モナド自身はインスタンス宣言によって定義される。\n",
        "# このインスタンス宣言には、Functor、Monad および MonadPlus というモナド のクラスの一部\n",
        "# あるいは全部の型に対するものである。\n",
        "# モナドのクラスはどれも導出されることはない。\n",
        "# IO のほかに、リスト ([]) と Maybe というモナドクラスの型が Prelude に定義されている。\n",
        "\n",
        "# 数学的にはモナドは、モナドの演算に対する一連の法則により支配されている。\n",
        "# この法則の概念はなにもモナドに限ったことではない。\n",
        "# Haskell ではほか にも、すくなくとも非公式には、法則に支配されている演算がある。\n",
        "# 例をあ げると x /= y と not (x == y) とは比較されるあらゆる型の値に対して同じでなければならない。\n",
        "# しかし、こ れを保証するものはなにもない。\n",
        "# == と /= とは Eq クラスのなかでは別のメソッドである。\n",
        "# しかも、== と =/ とが関連をもつものであることを保証する手段はない。\n",
        "# おなじように、ここで示すモナドの法則は、Haskell では保証できない。\n",
        "# しかし、モナドのクラスのインスタンスであれば、どれも満すべき法則である。\n",
        "# モナドの法則はモナドの構造の底流にあるものへの洞察をあたえるものである。\n",
        "# これらの法則を検証しながら、モナドをどのように使うかの感覚を覚える。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Bx5Rz-IxVWu_"
      },
      "source": [
        "# Functor クラスはすでに 5 章で述べた。\n",
        "# このクラスは 1つの演算 fmap のみを定義している。\n",
        "# このマップ関数はひと つの演算をコンテナ内のオブジェクトに適用し、\n",
        "# (多相型は別の型の値のコ ンテナとして考えることが可能である) 同じ形のコンテナを返す。\n",
        "# つぎの法則 は Functor クラスの map に適用される。\n",
        "%%script false\n",
        "\n",
        "fmap id\t=\tid\n",
        "fmap (f . g)\t=\tfmap f . fmap g\n",
        "\n",
        "# これらの法則は、コンテナの形は map によって変更されないということと、\n",
        "# コンテナの中身がマップの演算によってならび変えられことはないということを保証するものである。\n",
        "\n",
        "# Monad クラスは 2つの基本演算を定義している。\n",
        "# それは、>>= (bind) と return である。\n",
        "\n",
        "infixl 1  >>, >>=\n",
        "class  Monad m  where\n",
        "    (>>=)            :: m a -> (a -> m b) -> m b\n",
        "    (>>)             :: m a -> m b -> m b\n",
        "    return           :: a -> m a\n",
        "    fail             :: String -> m a\n",
        "\n",
        "    m >> k           =  m >>= \\_ -> k\n",
        "\n",
        "# この bind 演算、>> と >>= はふたつのモナドの値を合成し、return 演算は値をモナド (コンテナ) の中へ投入する。\n",
        "# >>= のシグネチャ Monad m => m a -> (a -> m b) -> m b をみれば、この演算を理解するのに役立つ。\n",
        "# ma >>= \\v -> mb は a 型の 値を含むモナドの値 ma と、型 a の値 v をとり、モナドの値 mb を返す関数とを合成する。\n",
        "# その結果、ma と mb は合成されて、b 型の値を含むモナドの値となる。\n",
        "# >> は第二引数の関数が最初のモナド演算の結果生成されて値を必要としない場合に用いられる。\n",
        "\n",
        "# bind の正確な意味は、もちろん、そのモナドに依存する。\n",
        "# たとえば、IO モナドでは x >>= y はふたつのアクションを順に実行する。\n",
        "# 最初のアクションの結果は2つ目のアクションに渡される。\n",
        "# 別の組み 込みのモナド、リストと Maybe について見てみる。\n",
        "# これらのモナド演算は、ゼロ個あるいはそれ以上を値を 1つの計算から次の計算へ渡すということで理解できる。\n",
        "# この例を簡単にみていく。\n",
        "\n",
        "# do 構文を使うとモナド演算の鎖を簡単に表記できる。\n",
        "# do の基本的な変換は以下のふたつのルールでとらえることができる。\n",
        "\n",
        "do e1 ; e2      =        e1 >> e2\n",
        "do p <- e1; e2  =        e1 >>= \\p -> e2\n",
        "\n",
        "# do の2つ目の形式におけるパターンは反駁可能で、パターンマッチ が失敗すると fail 演算が呼ばれる。\n",
        "# これが呼ばれると ( IO モナドのときと同様に)エラーが発生するか、\n",
        "# あるいは、(リスト モナドのときと同様に)「zero」が返される。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gu20Xw73z-YO"
      },
      "source": [
        "# 次のものはもっと複雑な変換である。\n",
        "\n",
        "do p <- e1; e2  =   e1 >>= (\\v -> case v of p -> e2; _ -> fail \"s\")    \n",
        "\n",
        "# ここで、\"s\" は do 文の位置を同定する文字列で、これは エラーメッセージのなかで使われるかもしれないものである。\n",
        "# たとえば、I/O モナドのなかで、'a' <- getChar のようなアクションは、\n",
        "# もし、型付けされた文字が 'a' ではなかった場合、fail を呼ぶ。\n",
        "# 次に、I/O モナドの fail はプログラムを停止し、error を呼ぶ。\n",
        "\n",
        "# >>= および return を支配している法則は以下の通り である。\n",
        "\n",
        "return a >>= k\t=\tk a\n",
        "m >>= return\t=\tm\n",
        "xs >>= return . f\t=\tfmap f xs\n",
        "m >>= (\\x -> k x >>= h)\t=\t(m >>= k) >>= h\n",
        "\n",
        "# クラス MonadZero は zero 要素および plus 演算を もつモナドに対して定義されている。\n",
        "\n",
        "class  (Monad m) => MonadZero m  where\n",
        "mzero             :: m a\n",
        "mplus             :: m a -> m a -> m a\n",
        "\n",
        "# zero 要素は次の法則に従わなければならない。\n",
        "\n",
        "m >>= \\x -> mzero\t=\tmzero\n",
        "mzero >>= m\t=\tmzero\n",
        "\n",
        "# リストについていえば、zero 値は []、つまり空リストである。\n",
        "# I/O モナドは zero 要素を持たない。\n",
        "# つまり、このクラスには属さない。\n",
        "\n",
        "# mplus 演算を支配している法則は以下のようになっている。\n",
        "\n",
        "m `mplus` mzero\t=\tm\n",
        "mzero `mplus` m\t=\tm\n",
        "\n",
        "# この mplus 演算はリストモナドではふつうの連結演算である。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OovnWPGsdtqG"
      },
      "source": [
        "# 9.2  組み込みモナド\n",
        "# モナド演算とそれらを支配する法則があるとなにが構築することができるか。\n",
        "# I/O モナドについてはすでに詳しくしらべたので、あとのふたつのモナドからはじめる。\n",
        "\n",
        "# リストのモナド bind はリスト中のそれぞれの値にたいしての一連の計算を結合する。\n",
        "# リストを使う場合は、>>= のシグネチャは以下のようになる。\n",
        "\n",
        "# (>>=)                   :: [a] -> (a -> [b]) -> [b] \n",
        "\n",
        "# これは、a のリストと a を bのリストへ写像する 関数が与えられたとき、\n",
        "# bind が、この関数を、入力それぞれの a に 適用して、生成したすべての b のリストを 1つのリストに連結する。\n",
        "# return 関数は単一要素リストを生成する。\n",
        "# これらの演算については 既になれていることと思う。\n",
        "# リストの内包表記はこのリストについて定義されたモナド演算を使って簡単に表現することができる。\n",
        "# 以下の 3 つの式は すべて同じ式を別の構文で表現したものである。\n",
        "\n",
        "[(x,y) | x <- [1,2,3] , y <- [1,2,3], x /= y]\n",
        "\n",
        "do x <- [1,2,3]\n",
        "   y <- [1,2,3]\n",
        "   True <- return (x /= y)\n",
        "   return (x,y)\n",
        "\n",
        "[1,2,3] >>= (\\ x -> [1,2,3] >>= (\\y -> return (x/=y) >>=\n",
        "   (\\r -> case r of True -> return (x,y)\n",
        "                    _    -> fail \"\")))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BxlbnmGy5x14",
        "outputId": "3ca32a8b-7f36-4331-8c07-887adb3cce30"
      },
      "source": [
        "# 実験\n",
        "!ghc -e $'[(x,y) | x <- [1,2,3] , y <- [1,2,3], x /= y]'\n",
        "!ghc -e $'[1,2,3] >>= (\\x -> [1,2,3] >>= (\\y -> if (x/=y) then return (x,y) else fail \"\"))'"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]\n",
            "[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yyYJMksi5vpn"
      },
      "source": [
        "# この定義は、このモナドでは fail の定義が空リストであることに依 存している。\n",
        "# 基本的には、それぞれの <- は、のこりのモナド計算へつぎつぎと渡される値の集合を生成する。\n",
        "# であるから、x <- [1,2,3] はのこりのモナド計算を 3 回起動することになる。\n",
        "# リストの各要素について 1回ずつである。\n",
        "# 戻りの式 (x,y) はそれを取り巻く bind の可能な組み合わせすべてについて評価される。\n",
        "# この意味ではリストモナドは多重値の引数をとる関数を記述しているものと考えることができる。\n",
        "# たとえば、つぎの関数を考えてみる。\n",
        "\n",
        "mvLift2                :: (a -> b -> c) -> [a] -> [b] -> [c]\n",
        "mvLift2 f x y          =  do    x' <- x\n",
        "                                y' <- y\n",
        "                                return (f x' y')\n",
        "\n",
        "# これは、通常の 2 引数関数を多重値 (引数リスト) 上の関数に変える。\n",
        "# できた関数は 2つの引数のすべての組み合わせのそれぞれに対して 1つの値を返する。\n",
        "\n",
        "# たとえば、\n",
        "\n",
        "mvLift2 (+) [1,3] [10,20,30]\t=>\t[11,21,31,13,23,33]\n",
        "mvLift2 (\\a b->[a,b]) \"ab\" \"cd\"\t=>\t[\"ac\",\"ad\",\"bc\",\"bd\"]\n",
        "mvLift2 (*) [1,2,4] []\t=>\t[]\n",
        "\n",
        "# この関数はモナドライブラリの関数 LiftM2 の特別版である。\n",
        "# これを、関数 f をリストモナドの外から、\n",
        "# 多重値上の計算をおこなうリストモナドの世界へ持ち込んだものと考えることができる。\n",
        "\n",
        "# Maybe に対して定義されたモナドはリストモナドに類似している。\n",
        "# 値 Nothing は [] の、Just x は [x] のように機能する。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ddJw7Qred4p1"
      },
      "source": [
        "# モナドを使う\n",
        "\n",
        "# モナド演算子とその法則について説明するだけではモナドがなんの役に立つのかわからない。\n",
        "# モナドがもたらす効用は、モジュール化 modularity である。\n",
        "# すなわち、演算をモナド的に定義することで、底流にある計算機というものを隠蔽し、\n",
        "# 新しい特徴をモナドに透過的に結びつけることを可能にする。\n",
        "# Wadler の論文はモナドを使っていかにモジュール化プログラムを構築するかの秀逸な例である。\n",
        "# この 論文から直接、例をとるところからはじめる。\n",
        "# 状態モナドをもとによく似 た定義のさらに複雑なモナドを構築する。\n",
        "\n",
        "# 簡単にいうと、状態の型 S についての状態モナドというのは次のよう なものである。\n",
        "\n",
        "data SM a = SM (S -> (a,S))  -- The monadic type\n",
        "\n",
        "instance Monad SM where\n",
        "  -- defines state propagation\n",
        "  SM c1 >>= fc2         =  SM (\\s0 -> let (r,s1) = c1 s0 \n",
        "                                          SM c2 = fc2 r in\n",
        "                                         c2 s1)\n",
        "  return k              =  SM (\\s -> (k,s))\n",
        "\n",
        " -- extracts the state from the monad\n",
        "readSM                  :: SM S\n",
        "readSM                  =  SM (\\s -> (s,s))\n",
        "\n",
        " -- updates the state of the monad\n",
        "updateSM                :: (S -> S) -> SM ()  -- alters the state\n",
        "updateSM f              =  SM (\\s -> ((), f s)) \n",
        "\n",
        "-- run a computation in the SM monad\n",
        "runSM                   :: S -> SM a -> (a,S)\n",
        "runSM s0 (SM c)         =  c s0\n",
        "\n",
        "# この例では新しい型 SM を定義して、型 S を暗黙に運ぶ計算を表現している。\n",
        "# すなわち、SM t 型の計算は、型 t の値を定義し、一方で、型 S の状態と読み出しと書きこ みといった相互作用をする。\n",
        "# SM の定義は単純で、1つの状態をとり、2 つの結果を返す関数で構成されている。\n",
        "# 1つ(任意の型)は返り値で、もう  1つは更新された状態である。\n",
        "# ここでは型シノニムは使えない SM という名前がインスタンス宣言で必要になるからである。\n",
        "# こういった ところで newtype 宣言を data 宣言のかわりによく使いる。\n",
        "\n",
        "# このインスタンス宣言は、モナドの「配管」を定義している。\n",
        "# ふたつの 計算の直列化と空の計算の定義である。\n",
        "# 直列化 ( >>= 演算子) は、(構築子 SM で表示されている) 計算を定義しており、\n",
        "# この計算は初期 状態 s0 を c1 へ渡し、この計算で得られ値 r を 2つ目の計算 c2 を返す関数に渡す。\n",
        "# そして、最後に、c1 で得られた状態を c2 に渡し、全体の結果を、計算 c2 の結果とする。\n",
        "\n",
        "# return の定義はもっと簡単である。\n",
        "# return は状態をまったく変更しない。\n",
        "# 値をモナドに入れ込むだけである。\n",
        "\n",
        "# >>= と return は基本的なモナドの直列化演算であるが、モナドプリミティブ ( monadic primitives ) も必要になる。\n",
        "# モナドプリミティブはモナド抽象の中でもちいられる単なる演算子で、モナドが機能するよう「車輪とギア」を接続する。\n",
        "# たとえば、IO モナドでは putChar のような演算子はプリミ ティブである。\n",
        "# それは、これらの演算子は IO モナドの内部的な仕事をのみ取り扱うからである。\n",
        "# 同様にして、状態モナドは 2 つのプリミティブ readSM と updateSM を使いる。\n",
        "# これらが、このモナドの内部構造に依存していることに注目する。\n",
        "# SM 型の定義を変更すると、これらのプリミティブも変更しなくてはならない。\n",
        "\n",
        "# readSM および updateSM の定義は単純である。\n",
        "# readSM は状態を観察できるようモナドの外へ状態を持ち出す。\n",
        "# 一 方、updateSM はユーザがそのモナドの状態を変更することを許する。\n",
        "# ( writeSM をプリミティブとすることも可能なのであるが、状態を扱う 場合\n",
        "# には update の方がより自然な場合が多い )\n",
        "\n",
        "# 最後に必要な関数はこのモナドの計算を駆動する関数 runSM である。\n",
        "# この関数は初期状態と計算をとり、返り値と最終状態の両方を返す関数である。\n",
        "\n",
        "# より大きな視点でみると、やらんとしていることは、すべての計算を一連のステッ プ( SM a 型の関数)として定義し、\n",
        "# >>= と return を使って直列にならべることである。\n",
        "# これらのステップは状態と ( readSM あるいは updateSM を通じて)\n",
        "# やりとりするか、あるいは、状態を無視する。\n",
        "# しかし、この状態の使用(不使用)は隠蔽されていて、S を使用するしないに依存して、\n",
        "# 計算をべつべつに駆動あるいは 直列化することはない。\n",
        "\n",
        "# この簡単な状態モナドの例をいくつも示すかわりに、状態モナドをつかったもっと複雑な例に進む。\n",
        "# リソースを利用する計算のための、ちょっとした 埋め込み言語 ( embedded language ) を定義する。\n",
        "# つまり、特別な目的のための言語を Haskell の型と関数の集合として構築する。\n",
        "# このような言語は Haskell の基本ツールを使う。\n",
        "# 関数と型を使って、対象分野に特化した型と演算ライブラリを構築する。\n",
        "\n",
        "# ここでの例では、なんらかのリソースを必要とする計算を考える。\n",
        "# もしリ ソースが利用可能である場合、計算が先へ進み、リソースが利用できないときには、計算が保留される。\n",
        "# これから定義するモナドによって制御されているリソースを使う計算を表示するために、型 R を使う。\n",
        "# R の定義は次のようになる。\n",
        "\n",
        "data R a = R (Resource -> (Resource, Either a (R a)))\n",
        "\n",
        "# おのおのの計算は、利用可能なリソースから、計算した後の残りに\n",
        "# リソースと a 型の結果あるいは保留された計算とのペアへの関数である。\n",
        "# その型は R a でこれはリソースが使い果されるところまで計算をつづける。\n",
        "\n",
        "# R の Monad インスタンスは以下のようになる。\n",
        "\n",
        "instance Monad R where\n",
        "  R c1 >>= fc2          = R (\\r -> case c1 r of\n",
        "                                (r', Left v)    -> let R c2 = fc2 v in\n",
        "                                                     c2 r'\n",
        "                                (r', Right pc1) -> (r', Right (pc1 >>= fc2)))\n",
        "  return v              = R (\\r -> (r, (Left v)))\n",
        "\n",
        "# この Resource 型は状態モナドのなかの状態と同じ扱いになる。\n",
        "# この定義はこんな風に読める。\n",
        "# 「リソースを消費する」ふたつの計算、c1 と( c2 を生成する) fc2 を合成するためには、初期リソースを c1 へ渡す。\n",
        "# 結果は、値 v とのこりのリソースで、これらは次の計算 ( fc2 v )の呼出し)を決定するために使われる。\n",
        "# さもなければ、保留された計算 pc1 とその保留の時点でのこっているリソースである。\n",
        "# 計算の保留の際は、2つ目の計算を考慮にいれておかなくてはいけない。\n",
        "# pc1 は最初の計算 c1 だけを保留するので、計算全体を保 留するためには c2 をこれに bind しておく必要がある。\n",
        "# return の定義は、v をこのモナドへ投入するが、リソース を変更しないというものである。\n",
        "# このインスタンス宣言はこのモナドの基本構造を定義しているが、リソースが どのよに使われるのかは決められていない。\n",
        "# このモナドは多くの型のリソース を制御するのに使うことが可能で多くのタイプのリソース使用ポリシーを実装することができる。\n",
        "# 例として、非常に単純なリソースの定義をあげる。\n",
        "# Resource として Integer を選択し、これを利用可能な計算ステップ数を表現するものとする。\n",
        "\n",
        "type Resource           =  Integer\n",
        "\n",
        "# 次の関数は、利用可能なステップ数がなくなるまで、1ステップを消費する。\n",
        "\n",
        "step                    :: a -> R a\n",
        "step v                  =  c where\n",
        "                              c = R (\\r -> if r /= 0 then (r-1, Left v)\n",
        "                                                     else (r, Right c))\n",
        "\n",
        "# Left と Right 構築子は Either 型のものである。\n",
        "# この関数は利用可能な計算ステップリソースが 1つでもあれば、v を返すことで R 内の計算を継続する。\n",
        "# もし、利用可能なステップがなければ、step 関数は現在の計算を保留し\n",
        "# (この保留は c で捕捉される)、この保留された計算をモナドへ戻す。\n",
        "\n",
        "# これで、一連の「リソースを用いる」計算 (このモナド) を定義するツールを手に入れたので、\n",
        "# step を用いてリソースの使用状況の形式を表現することができる。\n",
        "# 最後に、このモナドでは計算はどのように表現されるのかに言及しておく必要がある。\n",
        "\n",
        "# このモナド内でインクリメントを行う関数を考えてみる。\n",
        "\n",
        "inc                     :: R Integer -> R Integer\n",
        "inc i                   =  do iValue <- i\n",
        "                              step (iValue+1)\n",
        "\n",
        "# これは、計算の1ステップをインクリメントする関数を定義している。\n",
        "# <- はこのモナドから引数の値を引出すのに必要なものである。\n",
        "# iValue の型は R Integer ではなくて Integer である。\n",
        "\n",
        "# しかし、この定義は一般のインクリメント関数に比べると満足のいくものではない。\n",
        "# なんとか、既存の + 演算子を「ドレスアップ」して、この モナドの世界で機能するようにできないものか。\n",
        "# 持ち上げ ( lifting )をおこなう関数の集りから始める。\n",
        "# これらの関数は、既存の機能をモナド内へ持ち込む。\n",
        "# lift1 の定義 (これはMonad ライブラリの中の liftM1 とは少し違うものである) を考察してみる。\n",
        "\n",
        "lift1                   :: (a -> b) -> (R a -> R b)\n",
        "lift1 f                 =  \\ra1 -> do a1 <- ra1\n",
        "                                      step (f a1)\n",
        "\n",
        "# この関数は単一引数関数 f をとり、R 内で1ステップ消費し て持ち上げられた関数を実行する関数である。\n",
        "# この lift1 を用いると inc は次のようになる。\n",
        "\n",
        "inc                     :: R Integer -> R Integer\n",
        "inc i                   =  lift1 (i+1)\n",
        "\n",
        "# これで、ましにはなりったが、理想的というわけにはいかない。\n",
        "# まず、次の lift2 を加えてみる。\n",
        "\n",
        "lift2                   :: (a -> b -> c) -> (R a -> R b -> R c)\n",
        "lift2 f                 =  \\ra1 ra2 -> do a1 <- ra1\n",
        "                                          a2 <- ra2\n",
        "                                          step (f a1 a2)\n",
        "\n",
        "# この関数は、持ち上げられた関数内での評価の順番を明示的に設定していることに注目する。\n",
        "# a1 を生成する計算は、a2 を生成する計算より前におこなわれる。\n",
        "\n",
        "# lift2を使うと R モナド内で新しいバージョンの == を生成することができる。\n",
        "\n",
        "(==*)                   :: Ord a => R a -> R a -> R Bool\n",
        "(==*)                   =  lift2 (==)\n",
        "\n",
        "# この新しい関数については少しちがう名前をつかわなければならない。\n",
        "# それは == はすでに使われているから当然である。\n",
        "# しかし、場合によっ ては、持ち上げ前の関数と持ち上げ後の関数とでおなじ名前を用いることができる。\n",
        "# 以下のインスタンス宣言は、Num のすべての演算子が R 内で使えるようにするものである。\n",
        "\n",
        "instance Num a => Num (R a) where\n",
        "  (+)                   =  lift2 (+)\n",
        "  (-)                   =  lift2 (-)\n",
        "  negate                =  lift1 negate\n",
        "  (*)                   =  lift2 (*)\n",
        "  abs                   =  lift1 abs\n",
        "  fromInteger           =  return . fromInteger\n",
        "\n",
        "# Haskell プログラムでは、fromInteger 関数が、すべての整数定数に ついて暗黙のうちに適用される。\n",
        "# この定義のおかげで整数定数は型 R Integer となることができる。\n",
        "# やっとこれで、自然で完全なインクリメント関数を書くことができる。\n",
        "\n",
        "inc                     :: R Integer -> R Integer\n",
        "inc x                   =  x + 1\n",
        "\n",
        "# Eq クラスは Num クラスと同じやりかたで持ち上げることは できないことに注意する。\n",
        "# ==* のシグネチャは == の多重定義でなんとかなるようなものではない。\n",
        "# それは ==* の 結果が Bool ではなくて、R Bool であるからである。\n",
        "\n",
        "# R 中で興味のわく計算を表現するためには、条件式が必要である。\n",
        "# if は使えないので ( if は条件式として、R Bool ではなくて Bool 型が必要である )、ifR という名前の関数を考える。\n",
        "\n",
        "ifR                     :: R Bool -> R a -> R a -> R a\n",
        "ifR tst thn els         =  do t <- tst\n",
        "                              if t then thn else els\n",
        "\n",
        "# これで、R モナドのなかで大きなプログラムを書く準備がととのった。\n",
        "\n",
        "fact                    :: R Integer -> R Integer\n",
        "fact x                  =  ifR (x ==* 0) 1 (x * fact (x-1))\n",
        "\n",
        "# さて、次は一般の階乗関数と全く同じものというわけにはではないが、十分に読みやすくなっている。\n",
        "# + あるいは if のような既存 の演算子に新しい定義を与えると、Haskell のなかの\n",
        "# 埋め込み言語の基本的な部分を作ることにほかならない。\n",
        "# モナドは特に、これらの埋め込み言語の意味論をクリーンでモジュール性のある方法でカプセル化するのに便利である。\n",
        "\n",
        "# これで、なにかプログラムを走らせる準備ができた。\n",
        "# 以下の関数は、プログ ラムを、最大計算ステップ数をあたえられた M の中で動作させるもの である。\n",
        "\n",
        "run                     :: Resource -> R a -> Maybe a\n",
        "run s (R p)             =  case (p s) of \n",
        "                             (_, Left v) -> Just v\n",
        "                             _           -> Nothing\n",
        "\n",
        "# 割当てられたステップ数内に計算が終了するかどうかを Maybe 型を利用して扱う。\n",
        "# それで、次のような計算が可能になる。\n",
        "\n",
        "run 10 (fact 2)\t=>\tJust 2\n",
        "\n",
        "run 10 (fact 20)\t=>\tNothing\n",
        "\n",
        "\n",
        "# ここにきて、このモナドにいくつかの興味深い機能を加えることができる。\n",
        "# 次 の関数を考えてみる。\n",
        "\n",
        "(|||)                   :: R a -> R a -> R a\n",
        "\n",
        "# この関数は 2 つの計算を並列に実行し、最初に終った方の結果を返する。\n",
        "# こ の関数は例えば、こんな風に定義できる。\n",
        "\n",
        "c1 ||| c2                =  oneStep c1 (\\c1' -> c2 ||| c1')\n",
        "   where\n",
        "        oneStep          :: R a -> (R a -> R a) -> R a\n",
        "        oneStep (R c1) f =\n",
        "             R (\\r -> case c1 1 of\n",
        "                         (r', Left v) -> (r+r'-1, Left v)\n",
        "                         (r', Right c1') ->  -- r' must be 0\n",
        "                          let R next = f c1' in\n",
        "                            next (r+r'-1))\n",
        "\n",
        "# これは、c1 で 1 ステップで、c1 が終了すればその 値を返すか、\n",
        "# または、c1 が保留された計算( c1' )を返したときには、c2 ||| c1' を評価する、のどちらかである。\n",
        "# この oneStep 関数はその引数内で単一ステップを消費し、評価された値を返すか、\n",
        "# あるいは、のこりの計算を f に渡すかのどちらかである。\n",
        "# oneStep の定義は単純である。\n",
        "# これは c1 にリソース引数とし て 1 を与える。\n",
        "# もし、それで最終の値に到達したら、その値が返る。\n",
        "# 返されるステップカウント値 (計算がステップを消費せずに戻ることはありえる。\n",
        "# であるからこのときリソースカウントが 0 である必要はない) も調整されている。\n",
        "# この計算が保留された場合、調整されたリソースカウントが最後の計算に渡される。\n",
        "\n",
        "# これで、run 100 (fact (-1) ||| (fact 3)) のような式をループに陥ることなしで評価することができる。\n",
        "# 計算が相 互に実行されるからである。\n",
        "# (先に定義した fact では -1 を 与えるとループに陥る。\n",
        "# この基本構造の上にいろいろなバリエーションを考えることができる。\n",
        "# たとえば、状態を拡張して計算のステップのトレースを含むようにすることも可能である。\n",
        "# このモナドを IO モナドへ埋め込むことも可能である。\n",
        "# そうすれば、M 内の計算は外界とやりとりすることが可能になる。\n",
        "# ここでの例はこのチュートリアルの他の部分より高度なものであるが、\n",
        "# システムの基本的な意味論を定義する道具としてのモナドの力をよく説明している。\n",
        "# また、この例を小規模の領域限定言語 ( Domain Specific Language ) のモデルとなることを説明した。\n",
        "# あるいは、Haskell がこうしたものを定義 するのに適しているということも示した。\n",
        "# おおくの DSL が Haskell で開発されている。\n",
        "# おおくの例が、haskell.org にあるので参照する。\n",
        "# 特に興味ある例は、リアクションのあるアニメーションのための言語 Fran と\n",
        "# コンピュータミュージックのための言語 Haskore である。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JKpIyNBlPMz4"
      },
      "source": [
        "# Numbers"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1p0-_SWlPMiM"
      },
      "source": [
        "# 数 numbers\n",
        "# Haskell にはさまざまな数値型がある。\n",
        "# これらは Scheme の数値型をもとにしており、Scheme は Common Lisp をもとにしている。\n",
        "# (しかし、これらの言語は動的な型付けをおこなう) 標準の型には、固定長および任意倍長の整数、\n",
        "# それぞれの整数で構成された比 (分数)、単精度お よび倍精度の実数、複素数の浮動小数が含まれている。\n",
        "# ここでは数値クラス構造の基本的性格の概略を説明する。\n",
        "\n",
        "# 数値クラスの構造\n",
        "# 数値型クラス (クラス Num とその下にあるクラス) は Haskell の標準クラスの多くを対象としている。\n",
        "# Num は Eq のサブクラスだが、Ord のサブクラスではないこを注意しておく。\n",
        "# これは、順序述語は複素数には適用できないことによる。\n",
        "# しかしながら、Num クラスのサブクラス Real は Ord のサブクラスである。\n",
        "\n",
        "# Num クラスはすべての数値型に共通するいくつかの基本演算を備えている。\n",
        "# これには、加算、減算、符号反転、乗算、絶対値が含まれている。\n",
        "\n",
        "(+), (-), (*)           :: (Num a) => a -> a -> a\n",
        "negate, abs             :: (Num a) => a -> a\n",
        "\n",
        "# [negate は Haskell では唯一採用された前置演算子 - (マイナス) を適用する関数である。\n",
        "# これの呼出しを (-) と書くことはできない。\n",
        "# それは、(-) と書けば、減算関数になってしまうからである。\n",
        "# そこで、この nagate という名前をかわりに使う。\n",
        "# たとえば、-x*y は negate (x*y) と同値である。\n",
        "# (前置のマイナスは中置のマイナスとおなじ優先度をもつので、当然、乗算より優先度は低い)]\n",
        "\n",
        "# Num には除算演算子がないことに注意する。\n",
        "# 2 つの別の種類の除算演算子がオーバラップしない 2 つの Num のサ ブクラスで定義されている。\n",
        "# クラス Integral では全数 整数除算演算と剰余演算子が提供されている。\n",
        "# Integral の標準インスタンスは Integer (範囲制限のない整数あるいは数学で いうところの整数、一般には「bignum」としてしられているもの) と Int (範囲限定のある、計算機上の整数、範囲は最低でも 29 bit の符 号付 2 進数)である。\n",
        "# 一部の Haskell ではこれらのほかに別の integral 型が提 供されている。\n",
        "# Integral は Num の直接のサブクラスでは なく、Real のサブクラスであることに注目する。\n",
        "# その意味す るところは、ガウス整数を提供するつもりはないということである。\n",
        "\n",
        "# 他のすべての数値型はどれも Fractional クラスに属する。\n",
        "# このク ラスは普通の除算演算子 (/) を備えている。\n",
        "# そのサブクラスには、Floating があり、三角関数、対数関数、指数関数を備えている。\n",
        "\n",
        "# Fractionnal と Real のサブクラスである RealFrac は関数 properFraction を備えている。\n",
        "# この関数は数を整数部分と小数部分にわける。\n",
        "# また、それぞれ別のルールで整数に丸める関数群もそなえている。\n",
        "\n",
        "properFraction          :: (Fractional a, Integral b) => a -> (b,a)\n",
        "truncate, round,\n",
        "floor, ceiling:         :: (Fractional a, Integral b) => a -> b\n",
        "\n",
        "# RealFloat は Floating と RealFrac のサブクラ スで浮動小数部への効率てきなアクセスのためにいくつかの特別な関数を備えている。\n",
        "# それは、exponent と significand である。\n",
        "# 標準の型 Float と Double は RealFloat クラスになる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9biM1_q9rNyR"
      },
      "source": [
        "# 構造のある数値型\n",
        "# 標準の型、Int、Integer、Float、Double はプリミティブである。\n",
        "# その他はこれらからタイプ構築子により構築される。\n",
        "\n",
        "# Complex ( Complex ライブラリにある) はタイプ構築子であり、RealFloat 型から \n",
        "# Floating クラスの複素数のクラスを構築する。\n",
        "\n",
        "data (RealFloat a) => Complex a = !a :+ !a  deriving (Eq, Text)\n",
        "\n",
        "# ! の記号は正格性フラグである。\n",
        "\n",
        "#  引数の型を限定している文脈 (RealFloat a) => に注目する。\n",
        "# つまり、標準の複素数型は Complex Float であり、Complex Double だということである。\n",
        "# また、data 宣言から、複素数は x :+ y のように書くということ がわかる。\n",
        "# 引数はそれぞれ、実数部と虚数部である。\n",
        "# :+ はデータ構築子であるから、これをパターンマッチングに使用することができる。\n",
        "\n",
        "conjugate               :: (RealFloat a) => Complex a -> Complex a\n",
        "conjugate (x:+y)        =  x :+ (-y)\n",
        "\n",
        "\n",
        "# 同様にして、型構築子 Ratio (これは、Rational ライ ブラリに含まれている) は、\n",
        "# Integral のインスタンスから RealFrac クラスの分数クラスを生成する。\n",
        "# ( Rational は Ratio Integer の型シノニムである) しかし、Ratio は抽象型構築子である。\n",
        "# データ構築子 :+ のかわりに、分数は2つの 整数から1つの分数を形成する「%」関数を使う。\n",
        "# パターンマッ チングのかわりに、構成要素を引出す関数が用意されている。\n",
        "\n",
        "(%)                     :: (Integral a) => a -> a -> Ratio a\n",
        "numerator, denominator  :: (Integral a) => Ratio a -> a\n",
        "\n",
        "\n",
        "# この差の理由は何か。\n",
        "# 直積形式の複素数はユニークに決定できる。\n",
        "# すなわち、:+ を含む同一性は明白である。\n",
        "# 一方、分数ではユニークに決定できない。\n",
        "# しかし、正規(規約)形式を持つ。\n",
        "# これは、この抽象データ型の実装が保持すべきものである。\n",
        "# たとえば、numerator (x%y) は x に等しいとはかぎらない。\n",
        "# しかし、x:+y の実数部は常 に x である。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nLaFzEr8sAU2"
      },
      "source": [
        "# 数値型変換と多重定義されたリテラル\n",
        "\n",
        "# 標準Prelude と標準ライブラリには明示的な型変換をおこなう多重定義関数がいくつか備わっている。\n",
        "\n",
        "fromInteger             :: (Num a) => Integer -> a\n",
        "fromRational            :: (Fractional a) => Rational -> a\n",
        "toInteger               :: (Integral a) => a -> Integer\n",
        "toRational              :: (RealFrac a) => a -> Rational\n",
        "fromIntegral            :: (Integral a, Num b) => a -> b\n",
        "fromRealFrac            :: (RealFrac a, Fractional b) => a -> b\n",
        "\n",
        "fromIntegral            =  fromInteger . toInteger\n",
        "fromRealFrac            =  fromRational . toRational\n",
        "\n",
        "# これらのうち 2つは、多重定義数値リテラルを実現するために、暗黙のうちに 使用されている。\n",
        "# (小数を含まない) 整数は実際には、Integer のような数値に fromInteger を適用したものと同等である。\n",
        "# おなじように、浮動小数は Rational のような数値に fromRationa を適用 したものとみなす。\n",
        "# であるから、7 の型は (Num a) => a であり、7.3 の型は (Fractional a) => a である。\n",
        "# つまり、数値リテラルは、たとえば、総称数値関数で用いることができる。\n",
        "\n",
        "halve                   :: (Fractional a) => a -> a\n",
        "halve x                 =  x * 0.5\n",
        "\n",
        "# 数値のいくぶん間接的な多重定義の方法には、数値を与えられた型の数値として解釈するためのメソッドを、\n",
        "# Integral あるいは Fractional のインスタンス宣言によって指定できるという利点がある。\n",
        "# (これが可能なのは、fromInteger と fromRational はそれぞれ対応するクラスの演算子であるからである) \n",
        "# たとえば、Num のインスタンスである (RealFloat a) => Complex a は次のメソッドを含んでいる。\n",
        "\n",
        "fromInteger x           =  fromInteger x :+ 0\n",
        "\n",
        "# これは、つまり、fromInteger の Complex 版インスタンス は、実数部が適切な fromInteger の \n",
        "# RealFloat 版インスタンスにより生成される、複素数を生成するために定義されたものである、という ことである。\n",
        "# この伝でいけば、ユーザ定義の数値型(例えば、4 元数)でさえも多重定義の数を利用することができる。\n",
        "\n",
        "# もう1つ例をあげる。\n",
        "# # 2 節の inc の最初の定義を思い出す。\n",
        "\n",
        "inc                     :: Integer -> Integer\n",
        "inc n                   =  n+1\n",
        "\n",
        "# 型シグネチャを無視すれば、もっとも一般的な inc の型は (Num a) => a->a である。\n",
        "# しかし、この明示的な 型シグネチャは正当なものである。\n",
        "# それは、これが主型より限定的である からに他ならない。\n",
        "# (主型より一般的な型では静的エラーが発生する) \n",
        "# この型シグネチャには、inc の型を限定するという効果がある。\n",
        "# そして、この場合には、inc (1::Float) のようにすると型付け不可能ということになる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TOPaoTyEtCih"
      },
      "source": [
        "# デフォルトの数値型\n",
        "# 以下のような関数の定義を考えてみる。\n",
        "\n",
        "rms              :: (Floating a) => a -> a -> a\n",
        "rms x y          =  sqrt ((x^2 + y^2) * 0.5)\n",
        "\n",
        "# この指数関数 (^) (3 つある、それぞれ別の型付けがされている標準の指数関数のうちの1つ、\n",
        "# これの型は (Num a, Integral b) => a -> b -> a である。\n",
        "# また、2 は (Num a) => a という 型であるから、x^2 の型は (Num a, Integral b) => a となる。\n",
        "# これには問題がある。\n",
        "# それは、b という型変数についての多重定義を解決する方法がないということである。\n",
        "# なぜなら、これは文脈のなかにあるが、しかし、型式からは消えてしまっているからである。\n",
        "# 根本的には、プログラマは、x は自乗するよう指定したのであって、2 が Int の値であるか \n",
        "# Integer の値であるかを指定したわけではない。\n",
        "\n",
        "# もちろん、この問題は解決するこができる。\n",
        "\n",
        "rms x y          =  sqrt ((x ^ (2::Integer) + y ^ (2::Integer)) * 0.5)\n",
        "\n",
        "# しかしながら、これは、すぐに面倒になるのは明白である。\n",
        "\n",
        "# 実際、このての多重定義の曖昧性は数値に限ったことではない。\n",
        "\n",
        "show (read \"xyz\")\n",
        "\n",
        "# この文字列はどのような型だと仮定して読めばいいのか。\n",
        "# これは指数関数の ときの曖昧性よりもさらに深刻な問題である。\n",
        "# なぜなら、先程の場合では、Integral のインスタンスであればよいわけであるが、\n",
        "# 今度の場合は Text のどのインスタンスがこの曖昧性の解決に用いられるかによって\n",
        "# 期待できる振舞いがすっかりかわってしまうからである。\n",
        "\n",
        "# この多重定義の曖昧性の問題は一般の場合と数値の場合では違っているので、Haskell では\n",
        "# 数値に限って解決法を提供している。\n",
        "# 各モジュールにはデフォルト宣言 ( default declaration ) があり、これはキーワード default とそれにつづく\n",
        "# 括弧でくくられ、コンマで区切られた数値の モノタイプ (monotype) (型変数を含まない型) で構成されている。\n",
        "# 曖昧な型変数がみつかった場合(たとえば、上例の b )、すくなくともクラスの 1つが数値であり、\n",
        "# かつ、そのクラスのすべてが標準のものであれば、デフォルトリストが参照されて、\n",
        "# 型変数の文脈を満足する最初のものが使用される。\n",
        "# たとえば、もし、デフォルト宣言 default (Int, Float) があれば、上の曖昧な指数は型 Int と解決される。\n",
        "\n",
        "# 「デフォルトのデフォルト」は (Integer, Double) であるが、(Integer, Rational, Double) でもかまわない。\n",
        "#  注意深いプログラマなら、default () を好むかもしれない。\n",
        "#  これは、デフォルトがないということである。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2DrCBglEuOAc"
      },
      "source": [
        "# モジュール"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pyhphxtkuOb8"
      },
      "source": [
        "#モジュール\n",
        "# Haskell のプログラムはモジュール module の集合である。\n",
        "# Haskell のモジュールは名前空間の制御と抽象データ型の生成という2つの目的のためにある。\n",
        "\n",
        "# トップレベルのモジュールはこれまで議論したさまざまな宣言をすべて含む。\n",
        "# 結合性宣言、データ宣言と型宣言、クラス宣言とインスタンス宣言、型シグネチャ、\n",
        "# 関数定義、それに、パターン束縛である。\n",
        "# インポート宣言が最初に来なければならないことをのぞけば、宣言はどのような順序で出現してもかまわない。\n",
        "# (トップレベルのスコープは相互再帰的である)\n",
        "\n",
        "# Haskell のモジュールは比較的保守的にできている。\n",
        "# モジュールの名前空間は平坦である。\n",
        "# また、モジュールは「第一級」の対象ではない。\n",
        "# モジュールの 名前は英数字で、最初の文字は大文字でなければならない。\n",
        "# Haskell のモジュールとサポートされているファイルシステムの間には正式な結び付きはない。\n",
        "# とくに、モジュール名とファイル名とは正式には結びつかない。\n",
        "# また、2つ以上のモジュールを一つのファイルに含むことができる。\n",
        "# (ひとつのモジュールを複数のファイルに分ることもできる) \n",
        "# もちろん、特定の実装でモジュールとファイル名が関連するような習慣を採用するのがふつうである。\n",
        "\n",
        "# 技術的な観点では、モジュールというのは module というキーワードではじまる1つの大きな宣言ということができる。\n",
        "# つぎのは Tree というモジュールの例である。\n",
        "\n",
        "module Tree ( Tree(Leaf,Branch), fringe ) where\n",
        "\n",
        "data Tree a                = Leaf a | Branch (Tree a) (Tree a) \n",
        "\n",
        "fringe :: Tree a -> [a]\n",
        "fringe (Leaf x)            = [x]\n",
        "fringe (Branch left right) = fringe left ++ fringe right\n",
        "\n",
        "# この Tree 型と fringe 関数は、もうおなじみのはずである。\n",
        "# [ where というキーワードがあるので、レイアウトがモジュールのトップレベルで有効になる。\n",
        "# それゆえ、宣言はすべておなじカラム位置(典型的には第一カラム)に配置される。\n",
        "# また、モジュール名はこの型の名前とおなじであるが、これは許されていることに注意する]\n",
        "\n",
        "# このモジュールは明示的に Tree、Leaf、Branch、および fringe をエクスポートしている。\n",
        "# もし、この module キーワードのあとに続く、エクスポートリストがなければ、\n",
        "# このモジュールのトップレベルで束縛されている名前はすべてエクスポートされる。\n",
        "# (上の例では、すべてが明示的にエクスポートされている。\n",
        "# であるから効果 としてはエクスポートリストがない場合とおなじである) \n",
        "# 型の名前とその構築子は、Tree(Leaf,Branch) のように1つのグループにまとめられる。\n",
        "# これを簡略して、Tree(..) のように書くこともできる。\n",
        "# 構築子のサ ブセットをエクスポートすることも可能である。\n",
        "# エクスポートリストのなかの名前 は当該のエクスポートモジュールの局所名である必要はない。\n",
        "# スコープ内 の名前であればこのエクスポートリストに入れることができる。\n",
        "\n",
        "# これで、Tree モジュールはなにか別のモジュールにインポート することができる。\n",
        "\n",
        "module Main (main) where\n",
        "import Tree ( Tree(Leaf,Branch), fringe )\n",
        "\n",
        "main = print (fringe (Branch (Leaf 1) (Leaf 2)))\n",
        "\n",
        "# インポートされたりエクスポートされたりするモジュールのさまざまな項目のことを エンティティ と呼ぶ。\n",
        "# インポート宣言における明示的なインポートリストを省略すると \n",
        "# Tree モジュールからエクスポートされたすべてのエンティティがインポートされることに注目する。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VYIh8hk58CPg"
      },
      "source": [
        "# 修飾された名前\n",
        "# モジュールの名前空間に直接インポートされた名前はあきらかな問題をはらんでいる。\n",
        "# もし、インポートされた複数のモジュールが同じ名前の別のエンティティを含んでいたらどうなるか。\n",
        "# Haskell ではこの問題を修飾された名前 ( qualified name ) を使うことで解決する。\n",
        "# インポート宣言で、qualified キーワードを使い、インポートされた名前がインポートされた\n",
        "# モジュール名を接頭辞として使うようにする。\n",
        "# これらの接頭辞の あとに 「 . 」文字を空白をいれずに続ける。\n",
        "# [接頭辞は字句構文の 一部である。\n",
        "# すなわち、A.x および A . x は全く 別ものである。\n",
        "# 前者は修飾された名前であり、後者は中置関数の 「 . 」である] \n",
        "# たとえば、先程の Tree モジュールを使ってみる。\n",
        "\n",
        "module Fringe(fringe) where\n",
        "import Tree(Tree(..))\n",
        "\n",
        "fringe :: Tree a -> [a]   -- A different definition of fringe\n",
        "fringe (Leaf x) = [x]\n",
        "fringe (Branch x y) = fringe x\n",
        "\n",
        "module Main where\n",
        "import Tree ( Tree(Leaf,Branch), fringe )\n",
        "import qualified Fringe ( fringe )  \n",
        "\n",
        "main = do print (fringe (Branch (Leaf 1) (Leaf 2)))\n",
        "          print (Fringe.fringe (Branch (Leaf 1) (Leaf 2)))\n",
        "\n",
        "# Haskell のプログラマのなかにはすべてのインポートされた名前について、\n",
        "# それぞれの由来がはっきりわかるように、修飾子を使うことを好むひともいる。\n",
        "# 一方、短い名前を好むので、修飾子は必要最小限にしようとするプログラマもいる。\n",
        "\n",
        "# 修飾子はおなじ名前をもつ別のエンティティ間の衝突を解決するために使用する。\n",
        "# しかし、2つ以上のモジュールから同じエンティティがインポートされた場合どうなるか。\n",
        "# 幸いこのような名前のぶつかりは許されている。\n",
        "\n",
        "# 1つのエンティティが別の経路でインポートされても衝突は起こさない。\n",
        "# コンパイラが別のモジュールからのエンティティが実際に同じものかどうかを判別する。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7syhHm9o76U5"
      },
      "source": [
        "# 抽象データ型\n",
        "# 名前空間の制御のほかに、モジュールは Haskell で抽象データ型 ( ADT ) を構築する唯一の方法である。\n",
        "# たとえば、ADT の特徴は、表現型 ( representation type ) が隠蔽されるということであるが、\n",
        "# これは ADT 上のすべての演算がその表現型には依存せずに、抽象レベルで実行されるということである。\n",
        "\n",
        "# 例をあげる。\n",
        "# Tree 型は単純なので ふつは抽象型にはしないが、これに対応する ADT は次のような演算をふくむ。\n",
        "\n",
        "data Tree a             -- just the type name \n",
        "leaf                    :: a -> Tree a\n",
        "branch                  :: Tree a -> Tree a -> Tree a\n",
        "cell                    :: Tree a -> a\n",
        "left, right             :: Tree a -> Tree a\n",
        "isLeaf                  :: Tree a -> Bool\n",
        "\n",
        "# モジュールはこれを支援する。\n",
        "\n",
        "module TreeADT (Tree, leaf, branch, cell, \n",
        "                left, right, isLeaf) where\n",
        "\n",
        "data Tree a             = Leaf a | Branch (Tree a) (Tree a) \n",
        "\n",
        "leaf                    = Leaf\n",
        "branch                  = Branch\n",
        "cell  (Leaf a)          = a\n",
        "left  (Branch l r)      = l\n",
        "right (Branch l r)      = r\n",
        "isLeaf   (Leaf _)       = True\n",
        "isLeaf   _              = False\n",
        "\n",
        "# エクスポートリストに Tree という型名のみ (すなわち構築子がないということ) があらわれていることに注目する。\n",
        "# ということは、Leaf や Branch はエクスポートされないということである。\n",
        "# そして、木を構成したり、構成要素をとりだしたりする唯一の方法は、いくつかの(抽象)演算を使うことである。\n",
        "# もちろん、この情報の隠蔽の利点はあとで表現型をこの型の利用者に影響をあたえることなく、変更できるというこ とである。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9CJ2bffW7_cg"
      },
      "source": [
        "# そのほかの特徴\n",
        "# ここで、このモジュールシステムのその他の側面について手短に説明する。\n",
        "\n",
        "# import 宣言では、その宣言内で hiding 節を用いるこ とで選択的にエンティティを隠蔽できる。\n",
        "# これはそのモジュールの他の名前に修飾子をつけなくてもいいので明示的に他の使いたい名前を排除するのに便利である。\n",
        "\n",
        "# import 宣言には、as 節をおくことができる。\n",
        "# これにより、インポートされるモジュールの名前とは別の修飾子を指定することができる。\n",
        "# これにより、長いモジュールに由来する修飾子名を短くしたり、すべての修飾子を変更することなく、モジュール名の変更をおこなうことが簡単にできる。\n",
        "# プログラムは暗黙のうちに Prelude モジュールをインポートする。\n",
        "# 明示的な Prelude のインポートは、すべての Prelude 名の暗黙のインポートを上書きする。\n",
        "\n",
        "# それゆえ、\n",
        "\n",
        "import Prelude hiding length\n",
        "\n",
        "# は標準プレリュードからは length をインポートせず、この length の名前は別の方法で定義することができる。\n",
        "# インスタンス宣言はインポートやエクスポートリストのなかで明示的に名前がつくわけではない。\n",
        "# すべてのモジュールはそれぞれ、そのなかのすべてのインスタンス宣言をエクスポートし、\n",
        "# すべてのインポートはそれぞれ、すべてのインスタンス宣言をスコープないに持ち込む。\n",
        "# クラスのメソッドは括弧でくくったデータ構築子のあとにクラス名をつづけるか、\n",
        "# 普通の変数とおなじように名前をつけることができる。\n",
        "# Haskell のモジュールシステムは比較的保守的なものであるが、値のインポートと エクスポートに関しては多くのルールがある。\n",
        "# 多くは明白なものである。\n",
        "# たとえば、同じ名前をもつ別のエンティティをスコープ内にインポートすることは違反である。\n",
        "# いくつかのルールはこれほどは明白なものではない。\n",
        "# 例をあげると、1つの型やクラスに対して、そのプログラム内のどこかで\n",
        "# 型やクラスを組合せるための2つ以上のインスタンス宣言というものは存在できない。\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ShkCL8Fq8InV"
      },
      "source": [
        "# 型付けの落し穴 pitfalls"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r-G6YgiB8JQN"
      },
      "source": [
        "# 型付けの落し穴\n",
        "# この短いセクションでは Haskell の型システムを使う際、初心者に共通の 2、3 の問題について直観的な説明する。\n",
        "\n",
        "# let-束縛の多相性\n",
        "# Hidler-Milner の型システムを使うどの言語にも let-束縛の多相性 ( let-bound polymorphism ) と呼ばれるものがある。\n",
        "# これは、let あるいは where 節をもちいた束縛のない識別子はその多相性に関して制限があるからである。\n",
        "# 特に、ラムダ束縛された ( lambda-bound ) 関数 (すなわち、別の関数の引数になった関数) は \n",
        "# 2つの方法ではインスタンス化できない。\n",
        "# たとえば、以下のプログラムは不正 なプログラムである。\n",
        "\n",
        "let f g  =  (g [], g 'a')                       -- ill-typed expression\n",
        "in f (\\x->x)\n",
        "\n",
        "# なぜなら、主型が a-> a であるようなラムダ抽象に束縛された関数 g が f 内で\n",
        "# 2つの別の方法でつかわれているからである。\n",
        "# 一度は [a]->[a] という型で、そして、もう一度は Char->Char という型で使われている。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NqTMFyBcAs69"
      },
      "source": [
        "# 数値の多重定義\n",
        "# 数が多重定義されること、数の型変換が他の言語とおなじように暗黙のうちに起こることはないことをよく忘れてしまう。\n",
        "# より一般的な数値式が本当に総称的なものにはなれないこともある。\n",
        "# よくある数値の型付けエラーは次のよう なものである。\n",
        "\n",
        "average xs              =  sum xs / length xs           -- Wrong!\n",
        "\n",
        "# (/) は分数の引数を必要とする。\n",
        "# しかし、length の結果 は Int である。\n",
        "# この型の不一致は明示的な型変換によって訂正しなけれ ばならない。\n",
        "\n",
        "average                 :: (Fractional a) => [a] -> a\n",
        "average xs              =  sum xs / fromIntegral (length xs)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2vLXDa0ABFbK"
      },
      "source": [
        "# 単相性限定\n",
        "# Haskell の型システムはふつうの Hidley-Milner の型システムにはない型クラスに関連した制限がある。\n",
        "# これを、単相性限定 ( monomorphism restriction ) という。\n",
        "# この制限がある理由は subtle 型の曖昧性に関連している。\n",
        "\n",
        "# この単相性限定とは (単一の識別子への束縛を含む) パターン束縛により束縛をうける識別子で\n",
        "# 明示的な型シグネチャをもたないものは、単相的 ( monomorphic ) でなければならない、というものである。\n",
        "# 識別子は、多重定義されていないか、あるいは、多重定義されていても少くとも \n",
        "# 1つの限定的な多重定義のなかで用いられ、エクスポートされていないときには、単相的識別子である。\n",
        "\n",
        "# この制限に違反すると、静的型エラーがおこる。\n",
        "# この問題を回避するもっと も単純な方法は明示的な型シグネチャをつけることである。\n",
        "# あらゆる型シグネチャで (これが正しいものであれば) この問題を回避できる。\n",
        "\n",
        "# よくあるこの制限違反は高階関数的な手法で関数を定義する際におこる。\n",
        "# 標準Prelude にある sum の定義から例をあげる。\n",
        "\n",
        "sum                     =  foldl (+) 0\n",
        "\n",
        "# ここにあるようにすると、静的型エラーがおこる。\n",
        "# この問題は明示的な型シグネチャを付加することで解決する。\n",
        "\n",
        "sum                     :: (Num a) => [a] -> a\n",
        "\n",
        "# また、この問題は以下のように書けば起こらない。\n",
        "\n",
        "sum xs                  =  foldl (+) 0 xs\n",
        "\n",
        "# なぜなら、この制限はパターン束縛にのみ適用されるからである。"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6PkASMbZBx3f"
      },
      "source": [
        "# 配列 array"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HGWq2uHrByYN"
      },
      "source": [
        "# 配列\n",
        "# 理想的には、関数型言語での配列は単にインデックスから値への関数とみなす。\n",
        "# しかし、実際のところは、配列要素への効率的なアクセスを確保するために、\n",
        "# これらのアクセス関数の領域の特別な性質の利点を十分活用できることを確認しておく必要がある。\n",
        "# これは、連続した整数からなる整数の有限部分集合の同型性という性質である。\n",
        "# Haskell では、それゆえに、配列を適用演算をする一般的な関数としては扱わず、\n",
        "# サブスクリプト演算を行う抽象データ型として扱う。\n",
        "\n",
        "# 関数的配列への2つの主要なアプローチは、インクリメンタルな定義とモノリシックな定義とに識別することができる。\n",
        "# インクリメンタルなアプローチの場合は、与えられたサイズの空の配列を生成する関数と、\n",
        "# もう1つ、配列と、インデックスと、値を引数としてとり、与えられたインデックスの要素だけが\n",
        "# 元の配列と違う新しい配列を生成する関数となる。\n",
        "# 明かに、このような配列の意味を素朴に実装するると、インクリメンタルな再定義のたびに\n",
        "# 配列の新しい複製が必要になり、がまんできないくらい非効率になる。\n",
        "# したがって、このアプローチをどうしても使いたい場合には、過度の複製を回避するために、\n",
        "# 洗練された静的分析と巧妙な実行時の仕組を採用する。\n",
        "# 一方、モノリシックなアプローチの場合には、配列全体は一度に生成される。\n",
        "# 途中段階での配列の値を参照することはない。\n",
        "# Haskell には、インクリメンタルな配列更新の演算子があるが、\n",
        "# この配列の機能の主たる推進力はモノリシックなものである。\n",
        "\n",
        "# 配列は標準プレリュードには含まれていない。\n",
        "# この標準ライブラリには配列演算が含まれている。\n",
        "# 配列を使用するモジュールでは Array モジュールをインポートしなくてはならない。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "D-mrhR6LZHqJ"
      },
      "source": [
        "# インデックス型\n",
        "# Ix ライブラリは配列インデックスの型クラスを定義している。\n",
        "\n",
        "class  (Ord a) => Ix a  where\n",
        "    range       :: (a,a) -> [a]\n",
        "    index       :: (a,a) a -> Int\n",
        "    inRange     :: (a,a) -> a -> Bool\n",
        "\n",
        "# Int、Integer、Char、Bool および Ix の組型についてインスタンス宣言がなされている。\n",
        "# さらに、列挙型やタプル型に対してはインスタンスが自動的に導出される。\n",
        "# プリミティブ型を 1次元インデックスとみなし、タプルを多次元長方行列のインデックスとみなす。\n",
        "# クラス Ix の各演算の第一引数はインデックスのペアであることに注目する。\n",
        "# これらは典型的には配列の境界 (最初と最後のインデックス) である。\n",
        "# たとえば、Int のインデックスをもつ、0-オリジンの要素数 10 の境界は (0,9) となる。\n",
        "# また、1-オリジンの 100 × 100 の行列の境界は ((1,1),(100,100)) となる。\n",
        "# (他の多くの言語ではこのような境界は 1:100, 1:100 のように書く。\n",
        "# しかし、ここに示した形式のほうが型システムにピッタリ来る。\n",
        "# なぜなら、それぞ れの境界が一般のインデックスと同じ型になるからである)\n",
        "\n",
        "# range 演算は境界のペアを引数として、その間にあるインデックスの順序リストを生成する。\n",
        "# 例を以下に示す。\n",
        "\n",
        "range (0,4) => [0,1,2,3,4]\n",
        "\n",
        "range ((0,0),(1,2)) => [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2)]\n",
        "\n",
        "# inRange 述語はインデックスが与えられ境界のペアの間に入っている かどうかを判定する。\n",
        "# 最後に index 演算は配列の特定の要素を特定するのに必要な演算である。\n",
        "# 境界のペアと範囲内にあるインデックスを与えると、この演算は、そのインデックスが \n",
        "# 0-オリジンで何番目のインデックスかを返す。\n",
        "# たとえば、次のようになる。\n",
        "\n",
        "index (1,9) 2 => 1\n",
        "\n",
        "index ((0,0),(1,2)) (1,1) => 4\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IbYMfcyfYM8S"
      },
      "source": [
        "#  配列生成\n",
        "# Haskell のモノリシックな配列生成関数は境界のペアとインデックスと値のペア (連想リスト)のリストから配列を生成する。\n",
        "\n",
        "array                   :: (Ix a) => (a,a) -> [(a,b)] -> Array a b\n",
        "\n",
        "# ここで、1 から 100 までの数の自乗の配列の例をあげる。\n",
        "\n",
        "squares                 =  array (1,100) [(i, i*i) | i <- [1..100]]\n",
        "\n",
        "# この配列の式は連想リストに対するリストの内包表記の典型的な使用例である。\n",
        "# 実際、この使用例は、Id 言語の配列の内包表記にたいへんよく似ている。\n",
        "\n",
        "# 配列のインデックスによる指定には中置演算子 ! を使う。\n",
        "# また、境界は関数 bounds を使って取り出すことができる。\n",
        "\n",
        "squares!7 => 49\n",
        "\n",
        "bounds squares => (1,100)\n",
        "\n",
        "# この例を、各インデックスに対して適用する関数と境界とをパラメータ化することで一般化することができる。\n",
        "\n",
        "mkArray                 :: (Ix a) => (a -> b) -> (a,a) -> Array a b\n",
        "mkArray f bnds          =  array bnds [(i, f i) | i <- range bnds]\n",
        "\n",
        "# こうすれば、squares を mkArray (\\i -> i * i) (1,100) と定義することができる。\n",
        "\n",
        "# 多くの配列は再帰的に定義する。\n",
        "# すなわち、いくつかの要素の値は別の要素の値に依存している。\n",
        "# たとえば、フィボナッチ数の配列を返す関数をみる。\n",
        "\n",
        "fibs    :: Int -> Array Int Int\n",
        "fibs n  =  a  where a = array (0,n) ([(0, 1), (1, 1)] ++ \n",
        "                                     [(i, a!(i-2) + a!(i-1)) | i <- [2..n]])\n",
        "\n",
        "# こういった再帰をもう1つあげると、n × n のウェーブフロント行列である。\n",
        "# これは、その最初の行の要素と最初の列の要素がすべて 1 で、\n",
        "# その他の要素はその左側と左上側と上側との和であるような行列である。\n",
        "\n",
        "wavefront       :: Int -> Array (Int,Int) Int\n",
        "wavefront n     =  a  where\n",
        "                   a = array ((1,1),(n,n))\n",
        "                        ([((1,j), 1) | j <- [1..n]] ++\n",
        "                         [((i,1), 1) | i <- [2..n]] ++\n",
        "                         [((i,j), a!(i,j-1) + a!(i-1,j-1) + a!(i-1,j))\n",
        "                                     | i <- [2..n], j <- [2..n]])\n",
        "\n",
        "# このウェーブフロント行列は並列実装がゆえに、反復命令とよばれ、\n",
        "# 計算が最初の行と列から並列に始まり、左上から右下へ楔形に計算がすすむ。\n",
        "# しかし、計算の順序が連想リストによって指定されているわけではないとういことに注目することが重要である。\n",
        "\n",
        "# いまあげた例にかぎれば、対象の配列の各インデックスに対して、\n",
        "# 対応する配列の境界内にあるインデックスに対してのみ、唯一の連想リストを与えた。\n",
        "# 実際、一般に、配列を完全に定義するにはこのようにしなければならない。\n",
        "# インデックス境界を越える連想リストはエラーを引き起こす。\n",
        "# しかしながら、もしインデックスがないか、あるいは、2回以上出現する場合は即座にはエラーにはならない。\n",
        "# しかし、配列の当該のインデックスの値が未定義になるので、\n",
        "# そのインデックスの場所の値を参照しようとしたときにエラーとなる。\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "C5JmSBlZYKm5"
      },
      "source": [
        "# 累積\n",
        "# 単一のインデックスに対応する複数の値を合成する方法を指定することで、\n",
        "# インデックスが連想リスト中で 1 度しか出現してはいけないという制限を緩和することができる。\n",
        "# この結果のことを累積配列 ( accumulated array ) と呼ぶ。\n",
        "\n",
        "accumArray :: (Ix a) -> (b -> c -> b) -> b -> (a,a) -> [Assoc a c] -> Array a b\n",
        "\n",
        "# accumArray の第一引数は累積関数 ( accumulating function ) である。\n",
        "# 第二引数は初期値 (配列の各引数に対して同じ値) である。\n",
        "# 残りの引数は境界と連想リストで、これは array 関数と同じものである。\n",
        "# 典型的な累積関数は (+) で初期値は 0 である。\n",
        "# たとえば、次の関数は境界のペアと、(インデックス型の) 値のリストを引数としてとり、\n",
        "# ヒストグラム、すなわち、境界内での各値の出現頻度の表を生成する。\n",
        "\n",
        "hist            :: (Ix a, Integral b) => (a,a) -> [a] -> Array a b\n",
        "hist bnds is    =  accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]\n",
        "\n",
        "# 区間 [a,b) における計数をし、10を1つにカウントすると、次のようになる。\n",
        "\n",
        "decades         :: (RealFrac a) => a -> a -> [a] -> Array Int Int\n",
        "decades a b     =  hist (0,9) . map decade\n",
        "                   where decade x = floor ((x - a) * s)\n",
        "                         s        = 10 / (b - a)\n",
        "\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VxVTuNOnYEqh"
      },
      "source": [
        "# 漸進更新\n",
        "# モノリシックな配列の生成関数に加えて、Haskell では漸進的な配列の更新関数がある。\n",
        "# これは中置演算子 // を書くことで実現する。\n",
        "# 最も単純な場合としては、配列 a の i 番目の要素を v に更新するのは、a // [(i, v)] のように書く。\n",
        "# (//) の左引数に角括弧が使用されている理由は、この引 数が連想リストであるからである。\n",
        "# この連想リストは通常、この配列のインデックスの適切な部分集合を含む。\n",
        "\n",
        "(//)            :: (Ix a) => Array a b -> [(a,b)] -> Array a b\n",
        "\n",
        "# array 関数と同様に、値が定義されるためには、それに対応する連想 リスト中のインデックスは、唯一でなければならない。\n",
        "# たとえば、次の例は、行列の2つの行を入れ替える関数である。\n",
        "\n",
        "swapRows :: (Ix a, Ix b, Enum b) => a -> a -> Array (a,b) c -> Array (a,b) c\n",
        "swapRows i i' a =  a // ([((i ,j), a!(i',j)) | j <- [jLo..jHi]] ++\n",
        "                         [((i',j), a!(i ,j)) | j <- [jLo..jHi]])\n",
        "                   where ((iLo,jLo),(iHi,jHi)) = bounds a\n",
        "\n",
        "# ここでの j インデックスの同じリスト上の2つの別々のリスト内包表記の連結は少し効率の悪いものである。\n",
        "# 命令型言語のループを二つ書くようなものである。\n",
        "# 案ずることはない。\n",
        "# Haskell ではループの融合最適化と同じこと が可能なのである。\n",
        "\n",
        "swapRows i i' a =  a // [assoc | j <- [jLo..jHi],\n",
        "                                 assoc <- [((i ,j), a!(i',j)),\n",
        "                                           ((i',j), a!(i, j))] ]\n",
        "                   where ((iLo,jLo),(iHi,jHi)) = bounds a\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QG3xYZOSbuc4"
      },
      "source": [
        "# 例：行列の積\n",
        "# Haskell の配列の紹介をよく知られた行列の積の例でしめくくる。\n",
        "# 一般的な関数を1つ定義するために多重定義の長所を利用する。\n",
        "# 行列の要素の乗法と加法しか必要ではないので、あれこれやろうとしなければ、\n",
        "# あらゆる数値型の行列の乗算をする関数を手にいれるだけである。\n",
        "# さらに、(!) を適用し、インデックスへ Ix を作用させるときに十分注意すれば、\n",
        "# インデックス型に対しても一般性を得る。\n",
        "# 事実、4つの行と列のインデックス の型は同じである必要がない。\n",
        "# しかしながら、話を単純にするために 左側の行列の列のインデックスの型と\n",
        "# 右側の行列の行のインデックスの型は同じで、かつ、境界も同じであるとする。\n",
        "\n",
        "matMult         :: (Ix a, Ix b, Ix c, Num d) =>\n",
        "                   Array (a,b) d -> Array (b,c) d -> Array (a,c) d\n",
        "matMult x y     =  array resultBounds\n",
        "                         [((i,j), sum [x!(i,k) * y!(k,j) | k <- range (lj,uj)])\n",
        "                                       | i <- range (li,ui),\n",
        "                                         j <- range (lj',uj') ]\n",
        "        where ((li,lj),(ui,uj))         =  bounds x\n",
        "              ((li',lj'),(ui',uj'))     =  bounds y\n",
        "              resultBounds\n",
        "                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))\n",
        "                | otherwise             = error \"matMult: incompatible bounds\"\n",
        "\n",
        "# 余談であるが、命令型言語でふつうにつかわれる定式化により近い表現になるように \n",
        "# accumArray を用いて matMult を定義することも可能である。\n",
        "\n",
        "matMult x y     =  accumArray (+) 0 resultBounds\n",
        "                              [((i,j), x!(i,k) * y!(k,j))\n",
        "                                      | i <- range (li,ui),\n",
        "                                        j <- range (lj',uj')\n",
        "                                        k <- range (lj,uj)  ]\n",
        "        where ((li,lj),(ui,uj))         =  bounds x\n",
        "              ((li',lj'),(ui',uj'))     =  bounds y\n",
        "              resultBounds\n",
        "                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))\n",
        "                | otherwise             = error \"matMult: incompatible bounds\"\n",
        "\n",
        "\n",
        "# この関数を sum や (*) を関数パラメータにして高階化することで、さらに一般化をはかることができる。\n",
        "\n",
        "genMatMult      :: (Ix a, Ix b, Ix c) =>\n",
        "                   ([f] -> g) -> (d -> e -> f) ->\n",
        "                   Array (a,b) d -> Array (b,c) e -> Array (a,c) g\n",
        "genMatMult sum' star x y  =\n",
        "      array resultBounds\n",
        "            [((i,j), sum' [x!(i,k) `star` y!(k,j) | k <- range (lj,uj)])\n",
        "                                 | i <- range (li,ui),\n",
        "                                   j <- range (lj',uj') ]\n",
        "        where ((li,lj),(ui,uj))         =  bounds x\n",
        "              ((li',lj'),(ui',uj'))     =  bounds y\n",
        "              resultBounds\n",
        "                | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))\n",
        "                | otherwise             = error \"matMult: incompatible bounds\"\n",
        "\n",
        "# APL 好きならつぎのような関数がとても便利なことがわかる。\n",
        "\n",
        "genMatMult maximum (-)\n",
        "genMatMult and (==)\n",
        "\n",
        "# これらのうち最初の方は、引数が数値行列である。\n",
        "# そして、その結果の行列の (i,j) 番目の要素が、対応する i 番目の行と j 番目の列の要素の間の最大差異となる。\n",
        "# 2つ目は、引数は同値類の型で、結果は真理値行列になる。\n",
        "# この行列の (i,j) 要素は第一引数の i 番目の行と第二引数の j 番目の列が\n",
        "# ベクトルとして同値であるとき、そのときに限り True になる。\n",
        "\n",
        "# genMatMult の要素の型はすべて同一である必要はなく、単にこの関数 の引数 star として\n",
        "# 適切な型であればよいだけである。\n",
        "# また、1つ目の列のインデックスと2つ目の行のインデックスが同一でなければならない、\n",
        "# という要請を落とせば、もっと一般化することができる。\n",
        "# あきらかに、2つの行列は、はじめの行列の列数とあとの行列の行数がおなじであるかぎり、\n",
        "# 適合可能であると考えることができる。\n",
        "# みなさんはもっと一般性のある版を導出したいと思われるだろう。\n",
        "# (ヒント：長さを決定するのに index 演算を使用すること)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mjN7cxIncggO"
      },
      "source": [
        "# 次の段階 next stage"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "okRG53bDcg9n"
      },
      "source": [
        "# 次の段階\n",
        "# Haskell のリソースの膨大なコレクションが haskell.org のウェブサイトで利用可能である。\n",
        "# このサイトでコンパイラ、デモ、論文、そして Haskell と関数プログラミングに関する\n",
        "# たいへん重要な情報を見つけることができる。"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Afd1DAExM2I"
      },
      "source": [
        "# いまここ\n",
        "「やさしい Haskell 入門」 とは名ばかりで、めちゃむずかしい。\n",
        "ここから Haskell に入門した人は挫折ですね!!!!"
      ]
    }
  ]
}