プログラミングHaskell第2版 6章〜9章メモ書き

自社で開催している関数型プログラミング勉強会で学んだことの覚書です。ブログの更新はサボっていましたが、勉強会自体はコツコツ進めていました。今回は6〜9章を簡単にまとめます。これで基礎編はおしまいで、次の10章からは高度な話題（モナド、副作用を引き起こす関数、コンパイラの算出...etc）に入ります。もともとhaskellでコンパイラを書くことに興味があって関数型言語の勉強をはじめたので、すごく楽しみです。

第６章再帰関数

6.1 基礎概念

再帰 ... 関数の定義にその関数自身を利用して定義された関数を再帰的であるという

-- 階乗を求める関数
fac :: Int -> Int
fac 0 = 1              -- ... 基底部
fac n = n * fac (n-1)  -- ... 再帰部

6.2 リストに対する再帰

リストを連結する演算子++の定義がよくできているなと思った

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

ys で任意のリストを受けることができるの知らなかった・・空リストも受けられるんですね。

6.3 複数の引数を持つ再帰関数

引数が2つあるので、基底部も2つ必要

zip :: [a] -> [b] -> [(a,b)]
zip [] _          = []
zip _  []         = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

6.4 多重再帰

多重再帰 ... 関数が自分自身を複数参照すること

-- n番目のフィボナッチ数を生成する関数
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

6.5 相互再帰

相互再帰 ... 2つ以上の関数がお互いを参照し合うこと

even :: Int -> Bool
even 0 = True
even n = odd (n-1)

odd :: Int -> Bool
odd 0 = False
odd n = even (n-1)

第7章高階関数

7.1 基礎概念

高階関数 ... プログラミングにおける共通の様式を関数に閉じ込めたもの。引数として関数をとる関数。

※厳密には、高階関数には返り値として関数を返す関数も含まれるが、これにはカリー化という用語が定着しているため、実際には「引数として関数を取る関数」のみをさして高階関数という言葉が使われることが多い。この本でも、高階関数は「引数として関数をとる関数」の意味で使われる。

高階関数は、HaskellでDSLを作成するのに利用することができる

DSL、たとえばrubyでいうと、こんな風に自然言語的に（命令的？）にかけるやつ

create Player, with: { score: 100, life: 2 }

https://hackage.haskell.org/package/esqueleto

putPersons :: SqlPersist m ()
putPersons = do
  -- DSL風な表現ココから
  people <- select $
              from $ \person -> do
              return person
  -- DSLここまで
  liftIO $ mapM_ (putStrLn . personName . entityVal) people

関数と、手続きを閉じ込めたラムダ式とかを組み合わせてる風

<- は代入（アサイン）を意味するらしい https://stackoverflow.com/questions/28624408/equal-vs-left-arrow-symbols-in-haskell/28625714

7.2 リスト処理

map

-- リスト内包表記による定義
map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

-- 再帰による定義
map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

-- mapの引数にmapを渡すと入れ子リストの処理も可能
  map (map (+1)) [[1, 2, 3], [4, 5]]
= [map (+1) [1, 2, 3], map (+1) [4, 5]]
= [[2, 3, 4], [5, 6]]

filter

-- リスト内包表記による定義
filter :: (a -> Bool) -> [a] -> [a]
filter :: p xs = [x | x <- xs, p x]

-- 再帰による定義
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

filterで特定の要素を選択してからmapで要素を変換する使い方がよくされる。

7.3 畳込関数 foldr

再帰の簡単な様式を定義している関数

-- 定義いまいち理解できなかった。。
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v = v
foldr f v (x:xs) = f x (foldr f v xs)


-- 動作を理解するには、「リストのcons演算子を関数fに置き換え、末尾の空リストを値vに置き換える」と考えるとわかりやすい
-- 例
sum :: Num a => [a] -> [a]
sum = foldr (+) 0

  sum [1, 2, 3]
= 1 : 2 : 3 : []
= 1 + 2 + 3 + 0

foldr :: (a -> b -> b) -> b -> [a] -> b

要素を１つずつ考える。

(a -> b -> b)　は二変数（a, b）をとってbを返す関数

例：　

mult :: Int a, Float b => a -> b -> b

mult a b = a * b

-- mult 300 0.1 = 30.0

この場合、multは、Int型とFloat型の引数をとって、Float型を返す関数

mult_05 = foldr mult 0.5 -- [a] -> b

  mult_05 [1, 2, 3, 4, 5]
= foldr mult 0.5 [1, 2, 3, 4, 5]
= mult 1 (foldr mult 0.5 [2, 3, 4, 5])
= mult 1 (mult 2 (foldr mult 0.5 [3, 4, 5]))
= mult 1 (mult 2 (mult 3 (foldr mult 0.5 [4, 5])))
= mult 1 (mult 2 (mult 3 (mult 4 (foldr mult 0.5 [5]))))
= mult 1 (mult 2 (mult 3 (mult 4 (mult 5 (foldr mult 0.5 [])))))

7.4 畳込関数 foldl

リストに対する再帰的な関数が右結合であることを前提としたfoldrに対して、foldlは左結合が前提の畳込関数。

sum :: Num a => [a] -> a
sum = foldl (+) 0

-- 別の書き方
sum [] = 0
sum (x:xs) = x + sum xs

lは左から計算、rは右から計算

Prelude> l = foldl (/) 1.0
Prelude> l [0.1, 0.1]
100.0
-- (1.0 /  0.1 ) / 0.1 = 10 / 0.1 = 100.0

Prelude> r =foldr (/) 1.0
Prelude> r [0.1, 0.1]
1.0
-- 0.1 / (0.1 / 1.0) = 0.1 / 0.1 = 1.0

7.5 関数合成

(.) ... 二つの関数を合成した関数を返す高階演算子。

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

7.6 文字列の２進数加算器

https://github.com/fursich/programming_haskell/blob/master/7/samples/binary.hs

二変数引数をとるラムダ式（無名関数）もカリー化可能

f = (\x y -> x + y) 1

f 6 = 7

g = (+) 1
g 6 = 7

カリー化された関数をuncurryするとはカリー化されている ... 二変数関数に一つの引数だけを適用することが可能（一変数関数{残り1つの引数を要求する}になる）。組を引数にとる関数で同じことをすると、引数の型が違う（組じゃない）のでエラーになる

Prelude> h(x,y) = x + y
Prelude> h 1 -- タブルとは型が違うので「部分適用」が不能

<interactive>:12:1: error:
    • Non type-variable argument in the constraint: Num (a, a)
      (Use FlexibleContexts to permit this)
    • When checking the inferred type
        it :: forall a. (Num a, Num (a, a)) => a

Prelude> h (4,_) -- こんなこともできない

<interactive>:16:6: error:
    • Found hole: _ :: a
      Where: ‘a’ is a rigid type variable bound by
               the inferred type of it :: Num a => a
               at <interactive>:16:1-7
    • In the expression: _
      In the first argument of ‘h’, namely ‘(4, _)’
      In the expression: h (4, _)
    • Relevant bindings include it :: a (bound at <interactive>:16:1)
      Constraints include Num a (from <interactive>:16:1-7)
      Valid hole fits include
        it :: forall a. Num a => a
          with it @a
          (defined at <interactive>:15:1)

Prelude> h(1,2) -- タプルを与えればもちろん定義通りに動作する
3

all' f = foldl (\x y -> x && f y) True

-- all' even [2, 4, 6, 7] => False
-- == (((True && even 2) && even 4) && even 6) && even 7
--                                                ~~~~~~ここがFalse

all'' f = and.map f
-- こっちのほうがおしゃれw（preludeの定義）

[2,4,6,7].inject(true) {|result, val| result && val.even?}

# => false

8章型と型クラスの定義

8.1 typeによる型宣言

既存の型に別名をつける

-- Stringは文字のリストにすぎない
type String = [Char]

-- 別名の型の宣言には、他の別名も使える
-- 座標の型PosはIntの組の別名
type Pos = (Int, Int)
-- 座標を変換する関数の型TransはPosをPosに変換する関数の別名
type Trans = Pos -> Pos

-- ただし、typeによる型宣言は再帰できない(再帰型はdataで宣言する)
-- これはできない
type Tree = (Int, [Tree])

-- typeによる型宣言は、型変数を使って多相的にもできる
-- Pair a は (a, a)の別名
type Pair a = (a, a)
-- 型変数を2つ以上使う宣言も可能
-- ある型のキーとある型の値の組のリスト
type Assoc k v = [(k, v)]

-- 連想リストの中で与えられたキーに結び付けられた最初の値を返す関数
find :: Eq k => k -> Assoc k v -> v
find k t = head [v | (k', v) <- t, k == k']
-- example
find 1 [(2, 3), (3, 4), (1, 2)]
=> 2

「既存の型に別名」とは・・？

Prelude> type Foo = [Int]
Prelude> :{
Prelude| foo :: Foo -> Int
Prelude| foo xs = sum xs
Prelude| :}
Prelude> f  = [1,2,3,4] :: Foo
Prelude> f2 = [1,2,3,4] :: [Int]

-- どちらでも引数として受け付けられる（単なるエイリアス）
Prelude> foo f
10
Prelude> foo f2
10

つまりtypeによる型定義では、「fooの引数を型で縛る」ことはできない

8.2 dataによる型宣言

既存の型に別名をつけるのではなく、完全に新しい型を宣言するにはdataを使って型の値を指定する。

-- プレリュードの例
-- Bool型がFalseとTrueという二つの値から構成されることを示す
-- ここでのFalseとTrueのような型の値を「構成子」と呼ぶ
data Bool = False | True

新しく定義する型と構成子の名前はHaskellにとって何か特別な意味があるわけではなく、プログラマによって、新しい型を使う関数を通じて決定される。

新しく定義した型の値は、組み込み型の値と全く同じように利用できる。

data Move = North | South | East | West -- 上述のように、この段階での型と構成子の名前には、Haskellにとって何も特別な意味はない

-- 座標を移動させる関数move
move :: Move -> Pos -> Pos -- type Pos = (Int, Int), PosはIntの組の別名
move North (x, y) = (x, y+1)
move South (x, y) = (x, y-1)
move East  (x, y) = (x+1, y)
move West  (x, y) = (x-1, y)

-- 移動のリストを座標に適用する関数moves
moves :: [Move] -> Pos -> Pos
moves [] p = p
moves (m:ms) = moves ms (move m p) -- move m pで移動させた座標に対してmovesを呼び出していく

-- 移動の方向を逆転させる関数rev
rev :: Move -> Move
rev North = South
rev South = North
rev East  = West
rev West  = East

dataによる型宣言では、構成子に引数を取らせることもできる

-- 型Shapeは、値として、Circle rという形の値と、Rect x yという形の値をもつ（r, x, yは全てFloat型）
data Shape = Circle Float | Rect Float Float

-- 構成子に引数をとる型Shapeを、関数の定義に使ってみる
-- 正方形を生成する関数
square :: Float -> Shape
square n = Rect n n

-- 円を生成する関数
circle :: Float -> Shape
circle r = Circle r

-- 図形の面積を計算する関数
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y

引数を取ることから、構成子は関数だと言える。

-- Shape型の構成子CircleとRectは、引数の型がFloatで結果の型がShapeの構成子関数である。
> :type Circle
Circle :: Float -> Shape

> :type Rect
Rect :: Float -> Float -> Shape

普通の関数と構成子関数の違いは、構成子関数は定義に等式を持たず、純粋にデータを作るために存在していることである。

negate 1.0 -- negateの定義を適用することで、-1.0に評価される

Circle 1.0 -- Circleの定義に等式がないため、この状態で完全に評価済みであり、これ以上簡約できない。

-- 1.0がデータであるのと同様に、式Circle 1.0も単にデータである

dataによる宣言でも、型変数を利用できる

-- プレリュードの例
-- 型Maybe a はNothingかJust xのどちらか（xは型aの任意の値, aは型）
data Maybe a = Nothing | Just a

-- Maybe a の使用例
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)

safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)

（議論メモ）OOPとの比較で考えてみる

money, size,nameという内部状態を持つ、Companyというクラスを持つことを想定してみる

class Company
  attr_reader :money, :size, :name
  def initialize(money:, size:, name:)
    @money = money
    #... 内部状態を設定する
  end
end

company1 = Company.new(money: 100000, size: 10, name: 'hoge company') # これをオブジェクトとしてみる
company1.name
#=> 'hoge company'

haskellはオブジェクトのようなものを、「内部状態の組み合わせ」に対応した新しいデータとしてみている風

つまり、moneyとsizeとnameの組に対応して、「全ての会社(Corporationと仮に呼ぶ）」という集合の１つの会社（データ）が決まる

Int -> Int -> [Char] -> Corporation

みたいなイメージかと？

data Corporation = Company Int Int [Char]

company1 = Company 10000 10 "hoge company" -- (:: Corporation型となる)

:type company1
company1 :: Corporation

:{
 name :: Corporation -> [Char]
 name(Company _ _ ss) = ss
:}

name company1
"hoge company"

8.3 newtypeによる型宣言

新しい型を定義する際、構成子も引数も一つだけであれば、newtypeという仕組みが使える。

-- 自然数の定義
-- 唯一の構成子Nが型Intを唯一の引数としてとる
newtype Nat = N Int

-- この値が常に自然数であることを保証するのはプログラマーの仕事

newtypeを使う宣言と、type, dataを使う宣言の違い

typeではなくnewtypeを使うと、NatはIntの別名ではなく互いに別の型となるため、プログラムにおける両者の混同を型システムが防いでくれる
dataではなくnewtypeを使うと、効率が良くなる。Nのようなnewtypeの構成子は、型検査が通った後にコンパイラによって削除されるので、プログラムを評価する際にコストが発生しない

8.4 再帰型

dataやnewtypeを使って宣言される型は、再帰的にもできる。

-- 例: 前節の自然数の型を再帰を使って定義する
data Nat = Zero | Succ Nat

-- すなわち、型Natの値は、ZeroもしくはSucc n（nは型Natの任意の値）という形をとる
-- この宣言により、値Zeroから構成子関数Succを適用しはじめて、
-- Succを適用した値にSuccを適用することを繰り返すことで無限個の値を次々に生成できる
-- Zeroは0を表す構成子関数とし、Succは引数の次の値(+1)を表す構成子関数を表すということ？？(そう人間が仮定しているということ？) 
-- このように考えると、型Natの値を自然数とみなすことができる。
-- 数学的な話らしい
-- Succはサクセッサー、次を表す概念
-- https://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%A2%E3%83%8E%E3%81%AE%E5%85%AC%E7%90%86
Zero
Succ Zero
Succ (Succ Zero)
Succ (Succ (Succ Zero))

より形式的には、以下の変換関数を定義できる

nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n

int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))

上記関数を用いると、二つの自然数の足し算が可能だが、、、

add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)

再帰を用いると、上記のようにNatとInt間の変換なしに関数addを定義することができる

add :: Nat -> Nat -> Nat
add Zero     n = n
add (Succ m) n = Succ (add m n)

-- 2 + 1 = 3
= add (Succ (Succ Zero)) (Succ Zero)
= Succ (add (Succ Zero) (Succ Zero))
= Succ (Succ (add Zero (Succ Zero)))
= Succ (Succ (Succ Zero))

-- 2 + 3 = 5
-- 「0の２だけ次の数」+「3」
--  = 「0の1だけ次の数」+「3の+1だけ次の数」
--  = 「0の0だけ次の数」+「（3の+1だけ次の数）の+1だけ次の数」
--  = 「0そのもの」+「（3の+1だけ次の数）の+1だけ次の数」
--  = 「（3の+1だけ次の数）の+1だけ次の数」
-- Succ(Succ(「元の右辺の数(3)」))

(Succ m) + n
= (Succ m-1)  + Succ(n)
= (Succ n-2)  + Succ(Succ(n))
= ...
= Zero  + Succ(Succ(...(Succ(n)))
= Succ(Succ(...(Succ(n)))

-- 2 + 3 = 5
-- =「0の２だけ次の数」+「0の3だけ次の数」
-- =「0の(2+3)だけ次の数」
-- =「0の5だけ次の数」
(Succ m) + n
= Succ (m+n)

Zero + n
= n

dataによる型宣言で型変数を使った独自のリストを定義する例

リストの例

-- 型List aの値は、空リストを表すNilか、空でないリストを表すCons x xsの形である
data List a = Nil | Cons a (List a)

-- リストの長さを計算する関数
len :: List a -> Int
len Nil       = 0
len (Cons _ xs) = 1 + len xs

二分木の例

-- 木は葉と節から構成される
data Tree a = Leaf a | Node (Tree a) a (Tree a)

-- 木の表現一例（テキストの図を見ること）
t :: Tree Int
t = Node (Node (Leaf 1) 3 (Leaf 4)) 5 (Node (Leaf 6) 7 (Leaf 9))


-- 与えられた値が木の中に存在するか判断する関数
-- （探索木ではない木を想定しているため）最悪の場合だと、木の全体を走査することがある
occurs :: Eq a => a -> Tree a -> Bool
occurs x (Leaf y)     = x == y
occurs x (Node l y r) = x == y | occurs x l | occurs x r -- 前方の条件がTrueになれば後方は評価されない点に注意

-- 与えられる木が探索木の場合は、もっと効率が良いように関数occursを書き直すことができる
occurs :: Ord a => a -> Tree a -> Bool
occurs x (Leaf y)                 = x == y
occurs x (Node l y r) | x == y    = True
                      | x < y     = occurs x l
                      | otherwise = occurs x r

--- 様々な木の形状

-- 葉のみにデータをもつ木
data Tree a = Leaf a | Node (Tree a) (Tree a)

-- 節のみにデータをもつ木
data Tree a = Leaf | Node (Tree a) a (Tree a)

-- 葉と節のデータ型が異なる木
data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)

-- 部分木のリストをもつ木
-- 任意の個数ノードを持てる木
data Tree a = Node a [Tree a]

8.5 型クラスとインスタンスの宣言

Haskellでは、classを用いて新しい型クラスを宣言することができるクラスのインスタンスとなれるのは、dataとnewtypeを用いて宣言された型のみ

-- プレリュードのEqクラスの定義
-- ある型aが、Eqクラスのインスタンスになるためには、その型に対して同等と不等のメソッドを実装する必要がある
-- `/=`については、デフォルトの実装が型クラスに含まれているため、実際にこの型クラスEqのインスタンスになるために
-- 必要なのは`==`メソッドの実装だけである。（※また、デフォルトの実装は必要に応じて上書きすることもできる）
class Eq a where
  (==), (/=) :: a -> a -> Bool
  
  x /= y = not (x == y)
  
-- Bool型をEqクラスのインスタンスにする
instance Eq Bool where
  False == False = True
  True  == True  = True
  _     == _     = False

ある型クラスを拡張して、別の型クラスを作ることもできる

-- プレリュードのOrdは、Eqクラスを拡張して定義されている
class Eq a => Ord a where -- Rubyの継承みたいな概念なのか？？
  (<), (<=), (>), (>=) :: a -> a -> Bool
  min, max             :: a -> a -> a

  min x y | x <= y    = x
          | otherwise = y

  max x y | x <= y    = y
          | otherwise = x
          
-- 例えば、Bool型のようなEqクラスのインスタンスをOrdクラスのインスタンスにするためには、
-- 比較のための4つのメソッドを実装する必要がある（min, maxに関してはデフォルトの実装があるので実装不要）
instance Ord Bool where
  False < True = True
  _     < _    = False
  
  b <= c = (b < c) || (b == c)
  b >  c = c < b
  b >= c = c <= b

インスタンスの自動導出 haskellには、型を自動的にEq, Ord, Show, Readのインスタンスにするderivingという機能がある。(自動導出)

-- Bool型の実際のプレリュードの定義
data Bool = False | True
            deriving (Eq, Ord, Show, Read)


-- 結果としてBool型の値に対しては、上記4つの型クラスから導出されたメソッドが利用可能
> False == False
True

> False < True
True

> show False
"False"

> read "False" :: Bool
False

8.6 恒真式検査器

恒真式 ... 真理値表の結果が全てTrueになるような式

命題が恒真式であるかを判断する関数を定義する一歩目は、命題を表す型Propの宣言

-- 命題を表す型Propの宣言
-- 命題を構成する五種類の要素について、それぞれ構成子を定義します
data Prop = Const Bool
          | Var Char
          | Not Prop
          | And Prop Prop
          | Imply Prop Prop -- Implyは論理包含のこと（AならばB） 論理包含では、前提が間違っている場合は全て真とみなす rubyだと [].all?がtrueになるのに似てる

-- 命題の例を型Propを使って表す

-- A かつ notA
p1 :: Prop
p1 = And (Var 'A') (Not (Var 'A'))

-- A かつ B ならば A
p2 :: Prop
p2 = Imply (And (Var 'A') (Var 'B')) (Var 'A')

-- A ならば A かつ B
p3 :: Prop
p3 = Imply (Var 'A') (And (Var 'A') (Var 'B'))

-- ((A ⇒ B) かつ A) ⇒ B
-- 「右手の小指に怪我をしていて包帯を巻いているのが、犯人である」、「（あなたは）右手の小指の包帯を巻いている（ただ一人の人である）」⇒「あなたが犯人だ！」
p4 :: Prop
p4 = Imply (And (Var 'A') (Imply (Var 'A') (Var 'B'))) (Var 'B')

-- コレが有名な三段論法（推移律）
-- ((A ⇒ B) かつ (B ⇒ C)) ⇒ (A ⇒ C)

-- 変数名を真理値に対応づける置換表Substを宣言する
type Subst = Assoc Char Bool

-- 与えられた置換表の下で命題を評価する関数evalは、命題の五種類の構成要素に対するパターンマッチで定義できる
eval :: Subst -> Prop -> Bool -- 心理表、命題を順に受け取って真理値を返す
eval _ (Const b) = b -- 真理値がそのまま与えられているのであれば、真理表に関わらず与えられた真理値をそのまま返す
eval s (Var x)   = find x s -- 変数が1つ与えらえているのであれば、その変数に対応する真理値を真理値表から検索する
eval s (Not p)   = not (eval s p)
eval s (And p q) = eval s p && eval s q
eval s (Imply p q) = eval s p <= eval s q -- 第１命題が偽もしくは第２命題が真の時に真となるのが論理包含であるため

-- 命題が恒真式であるかを決定する

-- 最初に、命題の中にある全ての変数をリストとして返す関数varsを定義する(この関数は重複を取り除かない)
vars :: Prop -> [Char]
vars (Const _)   = []
vars (Var x)     = [x]
vars (Not p)     = vars p
vars (And p q)   = vars p ++ vars q
vars (Imply p q) = vars p ++ vars q

-- 指定した数だけ真理値を列挙したリストのリストを作る
bools :: Int -> [[Bool]]
bools 0 = [[]]
bools n = map (False:) bss ++ map (True:) bss
          where bss = bools (n-1)

-- 命題から変数を取り出し、重複を取り除き、これらの変数に対して真理値全ての組み合わせのリストを生成し、
-- それを変数と組にすれば良い
substs :: Prop -> [Subst]
substs p = map (zip vs) (bools (lengths vs))
           where vs = rmdups (vars p)
           
> substs p2
[
[('A', False), ('B', False)],
[('A', False), ('B', True)],
[('A', True), ('B', False)],
[('A', True), ('B', True)],
]


-- 最終的に命題が恒真式かどうかを決定する関数は、全ての置換に対して命題がTrueとなるかを調べることで定義できる
isTaut :: Prop -> Bool
isTaut p = and [eval s p | s <- substs p]

8.7 抽象機械

Exprは、整数と加算演算子からなる単純な数式の型この型の数式を評価して、整数にする関数valueを考える

data Expr = Val Int | Add Expr Expr

value :: (Val n)   = n
value :: (Add x y) = value x + value y 

(2+3) + 4
= value (Add (Add (Val 2) (Val 3)) (Val 4))
= value (Add (Val 2) (Val 3)) + value (Val 4)
= (value (Val 2) + value (Val 3)) + value (Val 4)
= (2 + value (Val 3)) + value (Val 4)
= (2 + 3) + value (Val 4)
= 5 + value (Val 4)
= 5 + 4
= 9

数式を処理する抽象機械を自分で定義し、その抽象機械で各段階を評価すれば、必要に応じて次に何を評価すべきかの評価順の指定が可能になるそれを実現するために、まずは抽象機械で使う制御スタックの型を宣言する

type Cont = [Op]
data Op = EVAL Expr | ADD Int

9章カウントダウン問題

数の集合と目標の数が与えられるので、数の集合から一つ以上の数を使い、値が目標の数字になる式を加算、減算、乗算、除算、括弧を組み合わせて作る。数の集合からは、それぞれ一回までしか数を使ってはいけない。計算途中に出てくる数は正の整数でなければならず、負の数や0、2 / 3のような分数は許されない。

-- 算術演算子に対する型定義をし、Showのインスタンスにして表示可能にする
data Op = Add | Sub | Mul | Div

instance Show Op where
  show Add = "+"
  show Sub = "-"
  show Mul = "*"
  show Div = "/"

-- 2つの正の整数に演算子を適用した時に、正の整数が生成されるかを調べる関数を定義
-- 重複する演算の組み合わせを防ぐために、代数の性質（可換則など）を使って、あとでこの関数定義を更新する
valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x `mod` y == 0

-- 有効な演算子の適用を実行する関数を定義
apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y

-- 数式の型とプリティプリンターを定義する
-- 数式の型は、整数の値であるか、演算子を二つの式に適用することを表現する構成子のいずれか
data Expr = Val Int | App Op Expr Expr

instance Show Expr where
  show (Val n) = show n
  show (App o l r) = brak l ++ show o ++ brak r
                     where
                       brak (Val n) = show n
                       brak e       = "(" ++ show e ++ ")"

-- 数式の、プリティプリンターによる変換
> show (App Add (Val 1) (App Mul (Val 2) (Val 3)))
"1+(2*3)"

-- 式の中の数値をリストとして返す関数
values :: Expr -> [Int]
values (Val n)     = [n]
values (App _ l r) = values l ++ values r

-- 式全体の評価結果を返す関数
-- 要素が一つのリストが求まれば成功で、空リストが求まれば失敗（途中の計算がvalidでないということ）
eval :: Expr -> [Int]
eval (Val n)     = [n | n > 0]
eval (App o l r) = [apply o x y | x <- eval l,
                                  y <- eval r,
                                  valid o x y]

-- evalに式がどう評価されるのか、書いてみた
eval App Add (App Sub (Val 3) (Val 2)) (Val 5)
> [apply Add x y | x <- eval (App Sub (Val 3) (Val 2)), 
                   y <- eval (Val 5),
                   valid Add x y]

--  x <- eval (App Sub (Val 3) (Val 2)) を評価してxを求める
eval (App Sub (Val 3) (Val 2))
> [apply Sub x y | x <- eval (Val 3),
                   y <- eval (Val 2),
                   valid Sub x y]

> [apply Sub x y | x <- [3],
                   y <- [2],
                   valid Sub 3 2]

> [1]

-- 再び全体の式の評価に戻る
eval App Add (App Sub (Val 3) (Val 2)) (Val 5)
> [apply Add x y | x <- [1],
                   y <- [5],
                   valid Add 1 5]
-- 評価結果が求まる
> [6]

-- 組み合わせを扱うために便利な関数をいくつか定義

-- リストの部分リストを返す関数
-- 順番は変えない
subs :: [a] -> [[a]]
subs []     = [[]]
subs (x:xs) = yss ++ map (x:) yss
              where yss = subs xs

> subs [1, 2, 3]
subs (1: [2, 3]) = (subs [2, 3]) ++ map (1:) (subs [2, 3])
subs [2, 3] = subs (2:3) = (subs [3]) ++ map (2:) (subs [3])
subs [3] = subs (3:[]) = [[], [3]]

subs [2, 3] = subs (2:3) = [[], [3], [2], [2, 3]]
subs (1: [2, 3]) = [[], [3], [2], [2, 3]] ++ map (1:) [[], [3], [2], [2, 3]]

-- 新たな要素をリストへ挿入して返す関数
-- TODO: あとで手で展開する
interleave :: a -> [a] -> [[a]]
interleave x []     = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)

interleave 1 [2, 3]
(1:2:[3]) : map (2:) (interleave 1 [3])
[1, 2, 3] : map (2:) ((1:3:[]) : map (3:) (interleave 1 []))
[1, 2, 3] : map (2:) ([1, 3] : map (3:) [[1]])
[1, 2, 3] : map (2:) ([1, 3] : [[3, 1]])
[1, 2, 3] : map (2:) ([[1, 3], [3, 1]])
[1, 2, 3] : [[2, 1, 3], [2, 3, 1]]
[[1, 2, 3], [2, 1, 3], [2, 3, 1]]


-- リストの要素に対する順列を返す関数
perms :: [a] -> [[a]]
perms []     = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))


-- 例
> subs [1, 2, 3]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

> interleave 1 [2, 3, 4]
[[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4], [2, 3, 4, 1]]

> perms [1, 2, 3]
[[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

-- リストの要素を全て返す関数
choices :: [a] -> [[a]]
choices = concat . map perms . subs

-- 与えられた式がカウントダウン問題の解となっているか調べる関数
solution :: Expr -> [Int] -> Int -> Bool
solution e ns n = elem (values e) (choices ns) && eval e == [n]

具体例 solution (App Mul (App Add (Val 1) (Val 50)) (App Sub (Val 25) (Val 10))) [1, 3, 7, 10, 25, 50] 222

True

あるリストを2つのからでないリストに分割する全ての方法を組にして返す

split :: [a] -> [([a], [a])]
split [] = []
split [_] = []
split (x:xs) = ([x], xs) : [(x:ls, rs) | (ls, rs) <- split xs]

具体例 split [1, 2] split (1:[2]) ([1], [2]) : [(1:ls, rs) | (ls, rs) <- split [2]] ([1], [2]) : [(1:ls, rs) | (ls, rs) <- ] ([1], [2]) : [([1], )] [([1], [2]), ([1], [])]

私の練習問題回答はこちら

https://gist.github.com/h-shima/1e6c22c4fa655940009b60b436f0f886

内容がかなり高度になってきましたね。。残り約半分なので、しっかりやりきって関数的な考え方を身に付けたいです。早くコンパイラ作りたい、、、

第６章 再帰関数