<   2013年 02月 ( 18 )   > この月の画像一覧

Yet Another Haskell Tutorial 19

8.4.2 Computations

関数の動作が(データの検索のように)失敗する場合のプログラミングを考えてみよう。Haskell ではこのような場合の戻り値には Maybe 型を使う事が多い。そのような関数の例として、グラフの経路を検索するプログラムが YAHT に紹介してある。

まず、グラフのデータ型を考えてみる。(注:グラフとはノードとエッジでできた図形の事だ。一筆書きの図を思い浮かべると分かりやすい。)

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]

Graph タイプコンストラクタは二つの引数をとる。ひとつはノードのラベル(の型)とエッジのラベル(の型)だ。Graph データコンストラクタの第1引数は、ノードの Id (Int 型) とノードのラベルのペアのリストだ。(注:分かりやすく言うと一筆書きのノードを全ての集合だ)第2の引数は、始点のノードの Id と終点の Id とエッジのラベルのトリプルのリストだ。(注:一筆書きの矢印付きの辺の集合)この二つのパラメータで一つのグラフ(一筆書きの図形)は完全に記述できる。

グラフのあるノードから別のノードまでの経路を検索する関数を考えてみよう。このような経路はない場合もある。したがって、戻り値には Mabe 型のデータを使う事にする。経路が存在する場合にはその経路が通過するノードのリストを返すことにする。このような関数 search の例が YAHT に説明してある。この search が実験できるように次のプログラム Graph.hs を作成した。

module Graph where

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]
  deriving Show

diagonal = Graph
  [(1,"A"),(2,"B"),(3,"C"),(4,"D")]
  [(1,2,"a"),(2,3,"b"),(4,3,"c"),(1,4,"d"),(1,3,"e"),(4,2,"f")]

search :: Graph v e -> Int -> Int -> Maybe [Int]
search g@(Graph vl el) src dst
  | src == dst = Just [src]
  | otherwise = search' el
  where
    search' [] = Nothing
    search' ((u,v,_):es)
      | src == u =
        case search g v dst of
          Just p -> Just (u:p)
          Nothing -> search' es
      | otherwise = search' es

diagonal は正方形とその対角線で作ったグラフのデータだ。上のプログラムは ghci の :l コマンドでコンパイルできたので search diagonal 1 3 を実行してみた。正方形の頂点 1 から頂点 3 までの経路の検索だ。

Prelude> :l Graph.hs
[1 of 1] Compiling Graph ( Graph.hs, interpreted )
Ok, modules loaded: Graph.
*Graph> search diagonal 1 3
Just [1,2,3]

Search 関数が何をやっているかを見てみよう。第1引数は Graph 型で、検索するグラフだ。第2引数は経路の始点で、第3引数は経路の終点だ。

まず、経路の始点と終点が同じときは経路のノードはその始点だけだ。関数は始点だけのリストを戻り値として返して終了する。そうでないときは、search' el を使って終点に至るまでの経路のノードを探す事になる。引数の el はエッジのリストだ。

Search' 関数の引数 el が空リストのときは、経路が見つからなかった事を示しているので Nothing が戻り値になる。El が空リストでないときはパターンマッチ ((u,v, _):es) でエッジのリストの先頭の要素をとりだし、エッジの始点を u にバインドし、終点を v にバインドする。エッジのラベルは使わないので _ で読み捨てる。Es はエッジの残りのリストだ。パターンの記述が g@((u,v,_):es) となっているが、g はパターン ((u,v_):es) の別名になる。

Search' の処理はエッジのリストの先頭のエッジについて行われることに注目しておくとソースが読みやすい。Src == u は経路の始点がエッジの始点と同じ場合だ、この場合は search g v dst が実行される。これは、g すなわち、search のパターンで取り出した先頭の要素を含めたエッジのリストから始点が先頭の要素の終点で、終点が目的の経路の終点であるような経路を探す。

Case search g v dst of 1 になっているので、case 文によるパターンマッチは search g v dst の値にたいして行われる。Search 関数が再帰的に用いられているが、このような再帰関数がソースに現れたときは、search g v dst の値が既知のものであると仮定すると読みやすい。Search 関数の戻り値は、始点から終点までのノードのリストだから、search g v dst の戻り値は [v, ... , dst] のような v から dst までの経路を示すノードのリストになる。これが case 文に渡される値になる。

したがって、Just p で経路のリスト p が存在していたときは、始点の u を p の先頭に追加したリストを search' の値として Just (u:p) で返す。そうでないときは、先頭のエッジの始点からの経路に終点が含まれるものがなかった事を示しているので、エッジの残りのリスト es の先頭の要素のエッジについて、検索を続ける。

Search' の引数のエッジリストの先頭の要素(エッジ)の始点が経路の始点と一致していないときは、単に残りのリスト es について検索する。

このアルゴリズムは、検索が失敗したときの情報が Nothing だけだし、最初に発見した経路しか検索できない。また、経路が循環していたときはプログラムが止まらなくなる。しかし、最初のたたき台としてこのアルゴリズムを理解しておく事が重要だ。

YAHT 本文の search2 は Maybe 型の代わりに Failable a 型を用いる事によって、検索が失敗したときの情報を返すようにしている。Prelude では Either a b という標準のデータ型があるが、ここでは自前の Failure a 型を定義してある。Failure 型の定義は次のようになる。

data Failable a = Success a | Fail String

Search2 のアルゴリズムは search のものの直訳になるので、説明は省略する。

同じように search3 は複数の経路について検索して、経路のリスト [[Int]] を返すように改良してあるが、基本的なアルゴリズムは search と同じだ。

これらの search, search2, search3 の3つのプログラムには共通点があり、これをタイプクラスにまとめる事ができる。それは、関数の計算の成功と失敗を戻り値として表現できる事や、成功した二つの結果を結びつける事、成功した複数の値をまとめあげた結果を作る事だ。

このような操作(関数)をまとめたタイプクラス Computation は次のようになる。

class Computation c where
  success :: a -> c a
  failure :: String -> c a
  augment :: c a -> (a -> c b) -> c b
  combine :: c a -> c a -> c a

Computation タイプクラスのインスタンスは c 型(タイプコンストラクタ)で、インスタンスのデータ型のデータには、success, failure, augment, combine の4つの関数を関数適用させる事ができる。

関数 success は a 型のデータひとつを引数にとり、c a 型のデータを返す。failure 関数は、引数に文字列(String)をとり、c a 型の値を返す。combine は2つの c a 型の引数をとり、ca 型の値を返す。argument 関数はやや複雑で、c a 型の値と (a -> c b) 型の関数を引数にとり、c b 型の値を返す。YAHT 本文の例では c a -> (a -> c a) -> c a でも構わないのだが、一般性を持たせるために ca -> (a -> c b) -> c b になっている。

Computation タイプクラス の定義だけでは抽象的なままなので、インスタンスを宣言して4つの関数の実装をしなければならない。そこで、instance キーワードで Maybe 型を Computation タイプクラスのインスタンスに宣言してみる。(関数の部分適用を利用して、success などの関数の a 型の引数は定義から省略してある。)

instance Computation Maybe where
  success = Just
  failure = const Nothing
  augment (Just x) f = f x
  augment Nothing _ = Nothing
  combine Nothing y = y
  combine x _ = x

ところで、Failable a 型は Maybe の Nothing の代わりに、Fail String で失敗の情報を返すように工夫したデータ型だが、基本的には Maybe と同じ使い方をするので、やはり、Computation のインスタンスにする事ができる。

instance Computation Failable where
  success = Success
  failure = Fail
  augment (Success x) f = f x
  augment (Fail s) _ = Fail s
  combine (Fail _) y = y
  combine x _ = x

さらに、全ての経路を検索する場合の戻り値は [[Int]] という Int 型のリストのリストだったから、リスト型 [] も Computation のインスタンスにする事ができる。

instance Computation [] where
  success a = [a]
  failure = const []
  augment l f = concat (map f l)
  combine = (++)

リスト型がインスタンスの場合、success の戻り値は要素が a だけの singleton list だ。Failure は空のリストを返す。combine は二つの success の値になるリストを結合する。augment は第1引数のリストの要素全てに関数 f を関数適用させたリストを返す。

このリスト型を利用したバージョンの search 関数の実行可能なソースを次に示す。search 関数の3つのバージョンに共通した処理は、Computation タイプクラスの関数として記述されており、3つのバージョンに共通する論理構造が分かりやすくなっている。

module Graph2 where

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]
  deriving Show

diagonal = Graph
  [(1,"A"),(2,"B"),(3,"C"),(4,"D")]
  [(1,2,"a"),(2,3,"b"),(4,3,"c"),(1,4,"d"),(1,3,"e"),(4,2,"f")]

class Computation c where
  success :: a -> c a
  failure :: String -> c a
  augment :: c a -> (a -> c b) -> c b
  combine :: c a -> c a -> c a

instance Computation [] where
  success a = [a]
  failure = const []
  augment l f = concat (map f l)
  combine = (++)

searchAll :: Graph v e -> Int -> Int -> [[Int]]
searchAll g@(Graph vl el) src dst
  | src == dst = success [src]
  | otherwise = search' el
  where
    search' [] = failure "no path"
    search' ((u,v,_):es)
      | src == u =
        (searchAll g v dst `augment`
        (success . (u:)))
        `combine` search' es
      | otherwise = search' es

実行例

Prelude> :l Graph2.hs
[1 of 1] Compiling Graph ( Graph2.hs, interpreted )
Ok, modules loaded: Graph.
*Graph> searchAll diagonal 1 3
[[1,2,3],[1,4,3],[1,4,2,3],[1,3]]

このプログラムを理解すれば、Haskell の最も理解が困難で、有用性の高い概念である「モナド」が理解できた事になる。

実際、Computation タイプクラスは Monad タイプクラスとほとんど同じものだ。ただ、Monad タイプクラスでは success は return で、failure は fail で、augment は >>= (bind) だ。combine が モナドにはないが、MonadPlus タイプクラスに現れる。

追記

Computaion タイプクラスを導入する事で驚くべき事がおきる。上のプログラムのリストを Computation のインスタンスにする instance 宣言文を、Maybe を Computation のインスタンスにする instance 宣言文と置き換えると、次のように、ほとんど変更なしで、searchAll :: Graph v e -> Int -> Int -> [[]] 関数を search :: Graph v e -> Int -> Int -> Maybe [Int] 関数に置き換える事ができる。Monad タイプクラスのパワーを感じさせる事例だ。

module Graph3 where

data Graph v e = Graph [(Int, v)] [(Int, Int, e)]
  deriving Show

diagonal = Graph
  [(1,"A"),(2,"B"),(3,"C"),(4,"D")]
  [(1,2,"a"),(2,3,"b"),(4,3,"c"),(1,4,"d"),(1,3,"e"),(4,2,"f")]

class Computation c where
  success :: a -> c a
  failure :: String -> c a
  augment :: c a -> (a -> c b) -> c b
  combine :: c a -> c a -> c a

instance Computation Maybe where
  success = Just
  failure = const Nothing
  augment (Just x) f = f x
  augment Nothing _ = Nothing
  combine Nothing y = y
  combine x _ = x

search :: Graph v e -> Int -> Int -> Maybe [Int]
search g@(Graph vl el) src dst
  | src == dst = success [src]
  | otherwise = search' el
  where
    search' [] = failure "no path"
    search' ((u,v,_):es)
      | src == u =
        (search g v dst `augment`
        (success . (u:)))
        `combine` search' es
      | otherwise = search' es

Prelude> :l Graph3.hs
[1 of 1] Compiling Graph3 ( Graph3.hs, interpreted )
Ok, modules loaded: Graph3.
*Graph3> search diagonal 1 3
Just [1,2,3]

Yet Another Haskell Tutorial 20 へ続く ...
[PR]
by tnomura9 | 2013-02-25 07:56 | Haskell | Comments(0)

Yet Another Haskell Tutorial 18

8.4 Classes

このセクションでは、自前のタイプクラスの作り方について解説してある。8.4.1 Pong では、テレビゲーム Pong (テレビテニス)を例にとって自前のタイプクラスの作り方を述べている。8.4.2 Computations ではグラフの演算を行うためのタイプクラス Computation を定義して、それがモナドとして働くように設計してみせている。記事の中では、モナドを全面に押し出してはいないが、最後の所で実はモナドであった事を披露している。

8.4.1 Pong

Pong とは昔のテレビゲームで、テレビの中で四角いボールを左右の、上下にスライドするパッドで打ち返して遊ぶものだ。(注:日本ではテレビテニスとして売り出されていた。)Pong ではテレビの画面に3つのものが表示される。ボールと2つのパッドだ。ボールとパッドは動作が異なるが、共通する部分もある。そこで、ボールとパッドの計算に共通な関数をタイプクラス Entity にまとめてみる。

(注:タイプクラスをオブジェクト指向言語のクラスの類推で考えると混乱する。オブジェクト指向言語のクラスはオブジェクトの鋳型だが、タイプクラスはオブジェクト指向言語でいう演算子や関数のオーバーロードのための仕組みだからだ。オブジェクト指向言語では、オブジェクトの間の共通性に注目するが、Haskell では異なるデータ型の間で、演算の共通性に注目する。)

YAHT の解説は概念的なものでそのままでは動作確認ができない。そこで、Entity タイプクラスを ghci 上で定義できるようにするには次のように工夫する。

Prelude> :set +m
Prelude> data Color = Color deriving Show
Prelude> data Shape = Shape deriving Show
Prelude> class Entity a where
Prelude|   getPosition :: a -> (Int,Int)
Prelude|   getVelocity :: a -> (Int,Int)
Prelude|   getAcceleration :: a -> (Int,Int)
Prelude|   getColor :: a -> Color
Prelude|   getShape :: a -> Shape
Prelude|

パドルを表す Paddle データ型は次のようになる。

Prelude> data Paddle = Paddle {
Prelude|   paddlePosX, paddlePosY,
Prelude|   paddleVelX, paddleVelY,
Prelude|   paddleAccX, paddleAccY :: Int,
Prelude|   paddleColor :: Color,
Prelude|   paddleHeight :: Int,
Prelude|   playerNumber :: Int
Prelude|   } deriving Show

タイプクラス Entity の関数を Paddle 型で使えるようにするには、instance 宣言で Paddle 型を Entity タイプクラスのインスタンスにしないといけない。

Prelude> instance Entity Paddle where
Prelude|   getPosition p = (paddlePosX p, paddlePosY p)
Prelude|   getVelocity p = (paddleVelX p, paddleVelY p)
Prelude|   getAcceleration p = (paddleAccX p, paddleVelY p)
Prelude|   getColor = undefined
Prelude|   getShape = undefined
Prelude|

準備が整ったので foo という名前でパドルを作る。

Prelude> let foo = Paddle 1 2 1 2 1 2 Color 3 1
Prelude|

foo に Entity タイプクラスの関数 getPostition が関数適用されるかどうか見てみる。

Prelude> getPosition foo
(1,2)

(注:このように、Haskell のタイプクラスは関数のオーバーロードを行うための仕組みであることを把握していると、オブジェクト指向言語のクラスと混同しないので混乱しない。タイプクラスの宣言、インスタンスの宣言、タイプクラスの関数の実装などやや複雑な手順になるが、順序よく理解しながら実例を作っていけば、そう複雑なことをやっているのではないことが分かる。)

上の Paddle 型は Entity のインスタンスではあるが、Eq のインスタンスではないので、Paddle 型の foo について foo == foo のような同等演算が使えない。Entity タイプクラスのデータに同等演算を導入したいときは、class 宣言のときに

class Eq a => Entity a where

のように型変数 a が Eq クラスのインスタンスである事を宣言しておくとよい。

この場合、instance 宣言で Paddle 型を Entity タイプクラスのインスタンスにするときに、Paddle 型が Eq タイプクラスのインスタンスである必要があるが、data 宣言で Paddle 型を作るときに deriving キーワードで Eq タイプクラスのインスタンスにしておけばいい。

(注:この辺りは少々複雑なので、class 宣言や instance 宣言や data 宣言や deriving キーワードを使っていろいろ実験しておいた方が理解しやすい。プログラム言語を習得する難しさは、言外の知識をどうやって貯めるかという事だ。結局、地道に文書を読んで、自分で簡単なプログラムを書いて、実験してという泥臭い仕事を積み重ねるしかない。運・鈍・根は何の分野でも同じだろう。)

Yet Another Haskell Tutorial 19 へ続く ...
[PR]
by tnomura9 | 2013-02-21 03:36 | Haskell | Comments(0)

Yet Another Haskell Tutorial 17

8.3 Datatypes

8.3.1 Strict Fields

Haskell の遅延評価は便利だが、効率が問題になることがある。この問題を解決する方法の一つとしてデータタイプに strict field を使う方法がある。Strict field について理解する前に、まず、bottom について説明しておく必要がある。

Bottom は値を持たないデータ型だ。そうして、それはどのようなデータ型のサブタイプにも含まれる。(管理人注:Bottom については、Haskell/Denotational semantics に詳しい。)。次のような Unit 型はデータコンストラクタ Unit 1つしかないが、このような Unit 型ですら、bottom を含んでいる。

Prelude> data Unit = Unit

Bottom は無限ループになって停止しないプログラムの型として考える事ができる。(管理人注:Bottom には値がないので、Haskell で bottom を表示する事ができないが、次のようにしてその存在がわかる。つまり、つぎのような無限ループをする関数 foo は値を返さないが、この foo の値として返されないという戻り値が bottom だ。Foo を実行してもプログラムは終了しないので ^C で強制終了しなくてはならない。)

Prelude> let foo = foo
Prelude> foo
^CInterrupted.

このような関数は Unit 型の関数として定義する事ができる。つまり、bottom は Unit 型のデータコンストラクタのひとつだ。

Prelude> :set +m
Prelude> let
Prelude| foo :: Unit
Prelude| foo = foo
Prelude|

Haskell には、bottom を値とする undefined という値がある。undefined はどの型にも含まれるので、その型は型変数で表される。

Prelude> :t undefined
undefined :: a

この bottom は _|_ で表される。このようにどのような型にも _|_ が含まれているので、Maybe Unit 型は、_|_, Nothing, Just _|_, Just Unit の4つの値を持つ事ができる。しかし、プログラマにとっては、Just _|_ は意味がないので、Just のフィールドを strict にすることで、Just _|_ が現れたらエラーにする事ができる。

次の SMaybe a 型は、!a によって、Just のフィールドを strict にすることができる。

Prelude> data SMaybe a = SNothing | SJust !a deriving Show

Maybe と SMaybe を使った関数 printJust、printSJust を次のように定義すると、

Prelude> let
Prelude| printJust :: Maybe () -> IO ()
Prelude| printJust Nothing = putStrLn "Nothing"
Prelude| printJust (Just x) = do putStr "Just "; print x
Prelude|
Prelude> let
Prelude| printSJust :: SMaybe () -> IO ()
Prelude| printSJust SNothing = putStrLn "Nothing"
Prelude| printSJust (SJust x) = do putStr "Just "; print x
Prelude|

Just undefined に対する応答は次のように異なる。

Prelude> printJust (Just undefined)
Just *** Exception: Prelude.undefined
Prelude> printSJust (SJust undefined)
*** Exception: Prelude.undefined

フィールドの値が非正格な Maybe a 型の printJust は最初に Just が印刷されて、エラー表示になるが、正格の Maybe a! の場合は Just が印刷される事なくエラー表示になる。

(この説明だけでは、strict field 正格なフィールドのありがたみがわからないが、非正格、正格の動作に bottom が関係しているという事は分かった。)

Yet Another Haskell Tutorial 18 に続く ...
[PR]
by tnomura9 | 2013-02-17 22:17 | Haskell | Comments(0)

ひま (最近の動画)

どこまで進化するのだろう。クオリティを保つのは大人でも大変なのに。

【ひま】Keep Only One Loveを踊ってみた【祝8000人+ひな祭り】
【ひま】告白予行練習を踊ってみた
【ひま】lllトゥルティンアンテナlllを踊ってみた【nanashi ver.】
【ひま】スウィートタイムを踊ってみた【マロン&ぴえる ver.】
【ひま】too Cute!を踊ってみた
【ひま】メルトを踊ってみた
【ひま】Colorful Worldを踊ってみた
【ひま】CLAP HIP CHERRY を踊ってみた
[PR]
by tnomura9 | 2013-02-16 07:56 | ボーカロイド | Comments(0)

Yet Another Haskell Tutorial 16

8 Advanced Types

Haskell では型システムは必須のものだ。この章の題名が高度な型となっているが、この章の内容を省略することはできない。

8.1 Type Synonyms

Haskell の type synonym (型の別名) は利用上の便宜のために使われている。この機能がなくても Haskell の動作に支障をきたすということはない。たとえば、3次元の空間の点の座標を表すトリプルのリストについて考えてみよう。これを扱う関数の型を一々 [(Double, Double, Double)] -> Double -> [(Double, Double, Double)] と書いていたのでは煩わしくて仕方がない。そこで、データ型の[(Double, Double, Double)] に別名をつけることを考えてみる。

type List3D = [(Double, Double, Double)]

すると、先ほどの関数の型は List3D -> Double -> List3D と書けるので随分すっきりする。

型の別名は再帰的な書き方はできない。次のような書き方はエラーになる。

type BadType = Int -> BadType

Haskell はコンパイルの段階で type synonym は実際の型に置き換えてしまうが、上の定義だと無限ループに陥ってしまうからだ。

Type synonym (型の別名) の定義には、型変数も使える。次のような定義は正しい定義だ。

type List3D a = [(a, a, a)]

この場合 [(Double, Double, Double)] は List3D Double で表すことができる。

8.2 Newtypes

type キーワードによる型の別名の定義は、便利だけれど別に無くても困らないというものだったが、newtype キーワードによる新しい方の定義は、型に別名をつけるのとは意味合いが異なる。newtype で定義されるデータ型は、元々の型の構造を保つものになる。

newtype で定義されるデータ型の例については、YAHTのものより、「やさしい Haskell 入門」の例の方が分かりやすい。「やさしい Haskell 入門では」 Int (整数) 型から Natural (自然数) 型を導出している。

自然数は整数と性質が似ているが、負の数はないし、引き算は答えがマイナスになる場合はエラーになる。したがって整数と全く同じというわけではない。しかし、加減乗除算など整数の性質と共通するものが多い。したがって、自然数は newtype 宣言文によって Int 型から導出するのが実用的だ。

newtype の使い方は data キーワードと似ている。Integer 型から Natural 型を作るには次のようにする。

newtype Natural = MakeNatural Integer

data キーワードの時と同じく、Natural がタイプコンストラクタで、MakeNatural がデータコンストラクタだ。newtype で新しい型を宣言するときは、データコンストラクタは必ず1個のパラメータをとる。パラメータなしや複数のパラメータは文法エラーになる。

次の例は ghci 上で newtype による Natural 型の宣言をしたものだ。

Prelude> :set +m
Prelude> newtype Natural = MakeNatural Integer deriving Show
Prelude> MakeNatural 3
MakeNatural 3

次に必要なのは Integer -> Natural の変換をする toNatural 関数の定義と、

Prelude> let
Prelude| toNatural :: Integer -> Natural
Prelude| toNatural x
Prelude| | x < 0 = error "Can't create negative naturals!"
Prelude| | otherwise = MakeNatural x
Prelude|

Natural -> Integer の変換をする fromNatural 関数の定義だ。

Prelude> let
Prelude| fromNatural :: Natural -> Integer
Prelude| fromNatural (MakeNatural i) = i
Prelude|

さらに Natural 型同士の加減乗除ができるように Natural 関数を Num クラスのインスタンスに宣言する。

次の例では、Naural 型を Num クラスのインスタンスに宣言し、(+) 演算の実装を定義している。

Prelude> instance Num Natural where
Prelude| fromInteger = toNatural
Prelude| x + y = toNatural (fromNatural x + fromNatural y)
Prelude|

:18:10:
Warning: No explicit method nor default method for `*'
In the instance declaration for `Num Natural'

:18:10:
Warning: No explicit method nor default method for `abs'
In the instance declaration for `Num Natural'

:18:10:
Warning: No explicit method nor default method for `signum'
In the instance declaration for `Num Natural'

Num クラスの他の演算が定義されていないとの警告がでるが、それでも、Natural 型の数値同士の加算ができるようになっているのが分かる。

Prelude> MakeNatural 3 + MakeNatural 5
MakeNatural 8

newtype キーワードによるデータ型の定義は data キーワードによる定義と比べて計算効率の上で利点がいろいろあるようなのだが、初心者には区別がつかない。最初のうちは、データコンストラクタのパラメータが1つだけの特殊な型の宣言法くらいの理解でも構わない気がする。

ちなみに、YAHTの例で定義された MyInt、

newtype MyInt = MyInt Int

は整数の一種だが、大小演算 > で偶数と奇数を比較したら必ず偶数が小さくなるという数の集合を表している。

instance Ord MyInt where
 MyInt i < MyInt j
  | odd i && odd j = i < j
  | even i && even j = i < j
  | even i = True
  | otherwise = False
  where odd x = (x ‘mod‘ 2) == 0
        even = not . odd

Yet Another Haskell Tutorial 17へ続く ...
[PR]
by tnomura9 | 2013-02-14 04:37 | Haskell | Comments(0)

みこ

ソロ

【みこ】too Cute!【踊ってみた】
【みこ】夏恋花火を踊ってみた
【みこ】うにを踊って歌ってみた【こかぜ】
【みこ】桃色スパークリングを踊ってみた
【みこ】メルトを踊ってみた
【みこ】トゥインクルを踊ってみた
【みこ】『プラチナ』-shin'in future Mix-【in神戸】

コラボ

【おちょみこ】アイラビューアイニジュー【誕生日】
【おちょみこ】つけまつける【踊ってみた】
【おちょみこ】ロミオとシンデレラ【踊ってみた】
【綾波みか】くれよんを踊ってみた【七河みこ】

チャンネル

みこ 七河
[PR]
by tnomura9 | 2013-02-13 08:11 | ボーカロイド | Comments(0)

Yet Another Haskell Tutorial 15

7.11 Layout

このセクションでは Haskell のレイアウトについて説明する予定だったようだが、本文が書かれていない。Haskell のレイアウトのルールはオフサイドルールと呼ばれるが、あまり美しくない。

オフサイドルールをかいくぐって、Ruby 風のスペース2個のインデントでプログラムを作るのは大抵の場合可能だ。このブログの「Haskell の インデント」という記事でそれをやってみている。

7.12 The Final Word on Lists

The final word というのを辞書で調べたら、「鶴の一声」と訳されていた。「社長の鶴の一声で議題は採択された。」というときの鶴の一声だ。しかし、本文の内容を読むと、「リストについてどうしても言っておきたい事」という意味のような気がする。

何をどうしても言っておきたかったのだろうか。それは、単純な再帰的定義は全て foldr で記述できるという事だ。再帰的定義はそのまま定義すればいいのではないかと思うが、foldr は初期条件を含めて一行でプログラムできるので便利と言えば便利だ。

foldr の定義は次のようになる。

foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

この定義に従って foldr を展開すると次のようになる。

foldr f z [a1,a2,a3, ... , an]
= f a1 (foldr f z [a2, a3, ... , an])
= f a1 (f a2 (fldr f z [a3, ... , an]))
= f a1 (f a2 (f a3 ( ... (f an z)...)))

一方、リストを引数とする単純な再帰関数 g は次のように定義できる。

g [] = z
g (x:xs) = g' x (g xs)

g' はリストの要素と同じ型の引数2つをとる関数だ。このような g を展開すると次のようになる。

g [a1,a2,a3, ... , an]
= g' a1 (g [a2,a3, ... , an])
= g' a1 (g' a2 (g [a3, ... , an]))
= g' a1 (g' a2 (g' a3 (...(g' an (g[])) ...)))
= g' a1 (g' a2 (g' a3 (...(g' an z))...)))

これを foldr の展開と比較すると f == g' となるような f をみつければ、g xs を foldr g' z xs で表す事ができる。

YAHT のこの節は上のアプローチとは別の角度から再帰関数を foldr で表す方法を紹介している。

最初に紹介されているのは map を foldr で表す方法だ。

map2 f = foldr (\a b -> f a : b) []

上のラムダ記法の部分の束縛変数を省略した書き方では、上の式は次のように簡略化できる。

map2 f = foldr ((:) . f) []

再帰関数で次の形式をしているものは全て foldr に書き直す事ができる。

myfunc [] = z
myfunc (x:xs) = f x (myfunc xs)

関数の f を infix form にするともっと foldr との対応が分かりやすくなる。

myfunc [] = z
myfunc (x:xs) = x ‘f‘ (myfunc xs)

関数 filter の再帰的定義は次のようになるので、

filter p [] = []
filter p (x:xs) =
  if p x then x : b else b

次のように foldr で書き直せる。

filter p = foldr (\a b -> if p a then a:b else b) []

(++) の再帰的定義は、

(++) [] ys = ys
(++) (x:xs) ys = x : (xs ++ ys)

変数を省略した書き方では、次のようになるので、

(++) [] = id
(++) (x:xs) = (x:) . (++) xs

次のように foldr に書けてしまう。

(++) = foldr (\a b -> (a:) . b) id

同様に concat は、

concat [] = []
concat (x:xs) = x ++ concat xs

だから、

concat = foldr (++) []

だ。もう一度、一般的な次の例について考えてみると、

myfunc [] = z
myfunc (x:xs) = x ‘f‘ (myfunc xs)

Foldr を使った定義は次のようになる。

myfunc = foldr f z

管理人注:再帰関数を foldr で記述する方法が可読性にも優れているかどうかは議論があるだろう。しかし、foldr という畳み込み関数の働き方の構造を浮き立たせてくれる事は間違いない。このブログの Haskell のリスト操作の 5. リストの再帰関数の項では foldr 以外に foldl の例について述べている。

Yet Another Haskell Tutorial 16 に続く ...
[PR]
by tnomura9 | 2013-02-13 00:55 | Haskell | Comments(0)

Too Cute !

オリジナル

【鏡音リン】 too Cute!【VOCALOID】

歌ってみた

【リシェ】 too Cute!【歌ってみた】
too Cute!を歌ってみた あやぽんず*
too Cute! @しゅーず【歌ってみた】

踊ってみた

【みこ】too Cute!【踊ってみた】
【ひま】too Cute!を踊ってみた
【わた】 too Cute! 踊ってみたたノ。・o・。ヽ【真夏】HD
【MMD-DMC4】too Cute!【リンちゃんとネコミミサンタ】【HD】
[PR]
by tnomura9 | 2013-02-11 20:21 | ボーカロイド | Comments(0)

Yet Another Haskell Tutorial 14

7.9 Arrays

この節では配列について解説されているが、分かりやすいとは言い難い。Arry 型について調べてみたのを参考に以下にまとめてみた。YAHT本文の内容からもそう外れていないはずだ。

Haskell では手続き型言語の配列ではなく、リストを使う。リストは柔軟な加工ができるが、インデックスに対応する値を取り出すという操作はリストの先頭から検索するので、効率が悪い。Data.Array モジュールの Array 型を使うとインデックスに対応した値をすぐに検索できる。

ただし、Array 型は配列の値を書き換えるなどの用途には向かない。配列の値を書き換えることはできるが、その関数は新しい配列のコピーを出力するだけだ。基本的に最初に作った配列の値をインデックスで取り出すという用途に適している。

Array 型のデータを作成する関数は array だ、array の型は次のようになる。

Prelude> :m +Data.Array
Prelude Data.Array> :t array
array :: Ix i => (i, i) -> [(i, e)] -> Array i e

arry はインデックスの上限と下限のペアを第1引数に、インデックスと値のペアのリストを第2引数にとり、Array 型のデータを返す。

Prelude Data.Array> array (1,3) [(1,"foo"),(2,"bar"),(3,"buz")]
array (1,3) [(1,"foo"),(2,"bar"),(3,"buz")]

インデックスと値のペアのリスト(連想リスト)の配列の出現順序は不定でいいが、インデックスは1回だけしか使えない。

Prelude Data.Array> array (1,3) [(2,"bar"),(1,"foo"),(3,"buz")]
array (1,3) [(1,"foo"),(2,"bar"),(3,"buz")]

二次元配列も作れる。

Prelude Data.Array> array ((2,2),(5,5)) [((i,j),i*j) | (i,j) <- range ((2,2), (5,5))]
array ((2,2),(5,5)) [((2,2),4),((2,3),6),((2,4),8),((2,5),10),((3,2),6),((3,3),9),((3,4),12),((3,5),15),((4,2),8),((4,3),12),((4,4),16),((4,5),20),((5,2),10),((5,3),15),((5,4),20),((5,5),25)]

上のプログラムの range はインデックスをリストに変換する関数だ。

Prelude Data.Array> range (1,5)
[1,2,3,4,5]
Prelude Data.Array> range ((1,1),(2,3))
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]

Array 型のインデックスに対応する値は ! 演算子で取り出せる。

Prelude Data.Array> let myArray = array (1,3) [(1,"foo"),(2,"bar"),(3,"buz")]
Prelude Data.Array> myArray ! 2
"bar"

Array 型を作る関数には array の他に、listArray, accumArray がある。

ListArray 関数は第2引数に値だけのリストをとり、インデックスを自動生成して対応づける。

Prelude Data.Array> listArray (1,3) ["foo","bar","buz"]
array (1,3) [(1,"foo"),(2,"bar"),(3,"buz")]

AccumArray 関数は、第1引数に演算子、第2引数に初期値、第3引数にインデックス、第4引数に連想リストをとる。ただし、連想リストのインデックスは重複してもよく、同じインデックスの値については積算されて Array 型のデータが作られる。

Prelude Data.Array> accumArray (+) 0 (1,3) [(1,2),(2,2),(3,1),(2,1),(1,3),(1,4)]
array (1,3) [(1,9),(2,3),(3,1)]

Array 型の値の変更は // 演算子を使って行うが、変更してない値を含んだ全てのデータの Array 型データが新しく作られる。

Prelude Data.Array> myArray // [(2,"hello")]
array (1,3) [(1,"foo"),(2,"hello"),(3,"buz")]
Prelude Data.Array> myArray // [(2,"hello"),(3,"world")]
array (1,3) [(1,"foo"),(2,"hello"),(3,"world")]

その他、YAHT には次のような配列関係の関数が紹介されている。

bounds (インデックスの下限と上限を求める)
indices (インデックスのリストを作る)
elems (配列の値のリストを作る)
assocs(配列を連想リストに変換する)

Prelude Data.Array> bounds myArray
(1,3)
Prelude Data.Array> indices myArray
[1,2,3]
Prelude Data.Array> elems myArray
["foo","bar","buz"]
Prelude Data.Array> assocs myArray
[(1,"foo"),(2,"bar"),(3,"buz")]

7.10 Finite Maps

Finite Map についての YAHT の内容は少し古いので、Programming Haskell の 3.2 Finite MapsHaskell Reference Manual の Data.Map.Strict からの情報をまとめてみた。

Finite Maps は手続き型言語の連想配列と考えられる。連想配列の実装はハッシュだが、Finite Map の実装は木構造 (size balanced binary trees) である。Finite Map を使うためには Data.Map モジュールをインポートする。このモジュールの関数は Prelude と衝突するものがあるので、quarified import が必要だ。

Prelude> import qualified Data.Map as Map

Finete Map は本質的には連想リスト [(key, value)] と同じだから fromList 関数から FiniteMap を作ることができる。

Prelude Map> :set +m
Prelude Map> let
Prelude Map| days = Map.fromList
Prelude Map|   [ ("Sun","Sunday")
Prelude Map|   , ("Mon","Monday")
Prelude Map|   , ("Tue","Tuesday")
Prelude Map|   , ("Wed","Wednesday")
Prelude Map|   , ("Thu","Thrsday")
Prelude Map|   , ("Fri","Friday")
Prelude Map|   , ("Sat","Saturday") ]
Prelude Map|

Finite Map から連想リストを取り出すには toList 関数を使う。

Prelude Map> Map.toList days
[("Fri","Friday"),("Mon","Monday"),("Sat","Saturday"),("Sun","Sunday"),("Thu","Thrsday"),("Tue","Tuesday"),("Wed","Wednesday")]

キーのリストを取り出すには keys 関数を使う。

Prelude Map> Map.keys days
["Fri","Mon","Sat","Sun","Thu","Tue","Wed"]

値のリストを取り出すには elems 関数を使う

Prelude Map> Map.elems days
["Friday","Monday","Saturday","Sunday","Thrsday","Tuesday","Wednesday"]

キーから値を検索するには lookup 関数を使う (Prelude で連想リストの検索も lookup 関数を使うので名前の衝突が起きる。)

Prelude Map> Map.lookup "Tue" days
Just "Tuesday"

キーに一致するものがないときは Nothing が返る。

Prelude Map> Map.lookup "Thor" days
Nothing

要素を追加するときは insert 関数を使う。Haskell では破壊的代入はできないので、新しい Finite Map が作成される。

Prelude Map> let days' = Map.insert "foo" "bar" days
Prelude Map|
Prelude Map> days'
fromList [("Fri","Friday"),("Mon","Monday"),("Sat","Saturday"),("Sun","Sunday"),("Thu","Thrsday"),("Tue","Tuesday"),("Wed","Wednesday"),("foo","bar")]

データを加工するときは insertWith を使う。第1引数の関数が、第2引数のキーに対応する値と第3引数の値に適用され、その結果が第2引数のキーの新しい値になる。

Prelude Map> Map.insertWith (++) "foo" "buz " days'
fromList [("Fri","Friday"),("Mon","Monday"),("Sat","Saturday"),("Sun","Sunday"),("Thu","Thrsday"),("Tue","Tuesday"),("Wed","Wednesday"),("foo","buz bar")]

Finite Map の要素を削除するには delete 関数を用いる。

Prelude Map> Map.delete "foo" days'
fromList [("Fri","Friday"),("Mon","Monday"),("Sat","Saturday"),("Sun","Sunday"),("Thu","Thrsday"),("Tue","Tuesday"),("Wed","Wednesday")]

Yet Another Haskell Tutorial 15へ続く ...
[PR]
by tnomura9 | 2013-02-11 19:27 | Haskell | Comments(0)

Yet Another Haskell Tutorial 13

7.7 Datatypes Revisited

この節では、代数的データ型のデータコンストラクタがパラメータを持つとき、個々のパラメータにフィールド名をつける名前付きフィールド (named field) の使い方を説明してある。

本文の例が必ずしも分かりやすいものではなかったので、簡単に named field の要点をまとめてみた。

Named field とは、代数的データ型の定義の際に次のようにフィールド名をつける方法だ。C 言語の構造体のようなものをイメージすると分かりやすい。

名前付きフィールド (named field) を定義する方法は次のようになる。

Prelude> :set +m
Prelude> data Person = Person {
Prelude|   name :: String ,
Prelude|   age :: Int
Prelude|   } deriving Show

上のようにデータ型を定義したとき、通常のようにデータコンストラクタの後にパラメータを並べる方法も使えるが、

Prelude> Person "Ken" 24
Person {name = "Ken", age = 24}

{ ... } で括ってフィールド名を指定することもできる。

Prelude> let ken = Person {name = "Ken", age = 24}
Prelude|

名前付きフィールどで定義したデータ型は、自動的にフィールド名でアクセサが定義される。

Prelude> name ken
"Ken"
Prelude> age ken
24

フィールドの値の更新は、フィールド名を指定するだけで行われる。

Prelude> ken {age = 26}
Person {name = "Ken", age = 26}

関数の引数のパターンマッチにフィールド名を使うことができる。

Prelude> :m +Data.Char
Prelude Data.Char> let nameToUpper (Person {name = x}) = map toUpper x
Prelude Data.Char|
Prelude Data.Char> nameToUpper ken
"KEN"

以上のことを押さえていれば、YAHT の本文が読めると思う。

7.8 More Lists

この節では、リストに関するさらに詳しい説明がされているが、未完のようだ。

7.8.1 Standard List Functions

Prelude 標準のリスト処理関数の説明がしてある。それぞれの関数の定義が紹介してあるのでリスト関数の中身が見られて面白い。名前の先頭に my をつけて再定義してみたが、ちゃんと動く。

map

Prelude> :set +m
Prelude> let
Prelude| mymap _ [] = []
Prelude| mymap f (x:xs) = f x : map f xs
Prelude|
Prelude> mymap (^2) [1,2,3,4,5]
[1,4,9,16,25]

filter

Prelude> let
Prelude| myfilter _ [] = []
Prelude| myfilter p (x:xs) |
Prelude|    p x = x : myfilter p xs
Prelude|  | otherwise = filter p xs
Prelude|
Prelude> myfilter odd [1,2,3,4,5]
[1,3,5]

foldr

Prelude> let
Prelude| myfoldr _ z [] = z
Prelude| myfoldr f z (x:xs) = f x (myfoldr f z xs)
Prelude|
Prelude> myfoldr (+) 0 [1,2,3,4,5]
15

foldl

Prelude> let
Prelude| myfoldl _ z [] = z
Prelude| myfoldl f z (x:xs) = myfoldl f (f z x) xs
Prelude|
Prelude> myfoldl (flip (:)) [] [1,2,3,4,5]
[5,4,3,2,1]

zip

Prelude> let
Prelude| myzip [] _ = []
Prelude| myzip _ [] = []
Prelude| myzip (x:xs) (y:ys) = (x,y) : myzip xs ys
Prelude|
Prelude> myzip [1,2,3] [4,5,6]
[(1,4),(2,5),(3,6)]

unzip

Prelude> unzip [('f',1),('o',2),('o',3)]
("foo",[1,2,3])

7.8.2 List Comprehensions

このセクションでは、いろいろなリストの定義方法(内包的定義を含め)を紹介してある。他の文書とも重複する内容なので実行例を示すにとどめる。どれも結果をみれば定義の意味は分かりやすいものばかりだ。

Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> [1,3..10]
[1,3,5,7,9]
Prelude> [1,4..10]
[1,4,7,10]

[1..] は無限リストになるが、遅延評価のおかげで take 3 [1..] とすれば、無限ループにはならず、先頭の3要素からなるリストが得られる。

Prelude> take 3 [1..]
[1,2,3]
Prelude> take 3 (drop 5 [1..])
[6,7,8]

無限リスト [1..] を利用すれば、リストの要素にインデックスをつける関数が簡潔に書ける。

Prelude> let
Prelude| assignID l = zip l [1..]
Prelude|
Prelude> assignID ["foo","bar","buz"]
[("foo",1),("bar",2),("buz",3)]

次の例は一般的な map を使ったリストの定義の例だが、

Prelude> :m +Data.Char
Prelude Data.Char> map toLower (filter isUpper "Hello World")
"hw"

map を使った上の定義をリストの内包的定義で書くとつぎのようになる。

Prelude Data.Char> [toLower x | x <- "Hello World", isUpper x]
"hw"

内包的定義を使うと2重のループが必要なプログラムも集合演算で簡単に書ける。

Prelude Data.Char> [(x,y) | x <- [1..5], y <- [x..7]]
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,3),(3,4),(3,5),(3,6),(3,7),(4,4),(4,5),(4,6),(4,7),(5,5),(5,6),(5,7)]

リストの内包的な定義は、集合の内包的定義とよく似た方法で、リストを定義することができる。たとえば、[1..10] のうち偶数だけを集めたリストは、内包的定義で次のように書ける。

Prelude Data.Char> [x | x <- [1..10], even x == True]
[2,4,6,8,10]

これは filter を使った次の方法と同じ結果になる。

Prelude Data.Char> filter even [1..10]
[2,4,6,8,10]

問題の種類によっては内包的定義を使うと見通しのよいプログラムを書くことができるが、内包的定義を多用するかどうかはプログラマの好みによるようだ。

Yet Another Haskell Tutorial 14 に続く ...
[PR]
by tnomura9 | 2013-02-10 18:37 | Haskell | Comments(0)