Haskell 始めてみる(06)

プログラミング Haskell

再帰型より。

型は再帰的に構成することもできます。たとえば、二分木の型を考えてみましょう。 

data Tree a             = Leaf a | Branch (Tree a) (Tree a)

ここでは多相型の二分木を定義しました。その要素はa型の値を含む「葉」のノードかあるいは(再帰的に)ふたつのサブツリーを含む「枝」のノードです。

これも前回までと基本的に同じ。
Branch の引数が、Tree a 型になっている。 Tree a の定義に Tree a が使われているところが再帰的な構成ということ。
この後に出てくる fringe という関数の定義がこれ以上ないほどすっきりしていてうなってしまった。 fringe は、木を引数に取って、木の葉を左の方から集めたリストを返す関数。木の根は上にあるとしている。
で、実装は、

fringe                     :: Tree a -> [a]
fringe (Leaf x)            =  [x]
fringe (Branch left right) =  fringe left ++ fringe right

だけ。うーん、これが Haskell の強力さなのか。

今まで右辺のデータ構築子の引数が型変数だったところを具体的な型にしても良い。左辺に具体的な型を入れると怒られる。

data Member = Id Integer | Name String  -- OK

Integer と String は組み込みの型。何かの会員を、番号か名前で指定するような雰囲気。
右辺で、型変数の代わりに具体的な型を入れている。これは OK。

data Member Integer = Id Integer | Name String
 *Main> :l type.hs
 Compiling Main             ( type.hs, interpreted )

 type.hs:3:12: Type found where type variable expected
 Failed, modules loaded: none.

怒られた。

まとめ。

  • 型構築子は再帰的に定義できる
  • 右辺のデータ構築子の引数は、具体的な型でもよい
    • Tree a の定義でも、右辺データ構築子の引数は Tree a という具体的な型(Tree だけだと型ではない)。