かずきのBlog@hatena

日本マイクロソフトに勤めています。XAML + C#の組み合わせをメインに、たまにASP.NETやJavaなどの.NET系以外のことも書いています。掲載内容は個人の見解であり、所属する企業を代表するものではありません。

手軽なスクリプト言語としてのF# その25「判別共用体」

今日は、判別共用体というものをやってみようと思います。今までちょろっと使ってきたoption型とかも判別共用体だったりします。例えば、同じOption型なのに「Some 値」という値やNoneという違う種類の値を入れたりすることが出来ます。こういう特徴をもつものですね。似たようなイメージを受ける列挙型との違いは、任意の値を持たせることが出来る所だと思います。

let i : int option = Some 10
let s : string option = Some "aiueo"

このように、Someに対して10とかaiueoとか値を持たせることが出来てるのも判別共用体の特徴です。
定義は以下のような感じでやります。

type 型名 =
  | 識別子1 of 型名1 * 型名2 ...
  | 識別子2 of 型名1 * 型名2 ...
  | 識別子3 of 型名1 * 型名2 ...
  ...

何も型を受け取らない場合はofから後は省略することが出来ます。複数の型を受け取るケースはタプルを使って実現しています。では、実際に使ったプログラムを書いてみます。

// 値無しと値が1つと値が2つ(タプル)の場合がある判別共用体
type ValueHolder =
    | Nothing
    | Single of int
    | Pair of int * int

// こんな風に使える
let v1 : ValueHolder = Nothing
let v2 : ValueHolder = Single 1
let v3 : ValueHolder = Pair (1, 2)

let printValue (v : ValueHolder) =
    // パターンマッチで使い分けが出来る
    match v with
    | Nothing -> printfn "値無し"
    | Single x -> printfn "1つ値あり %d" x
    | Pair (x, y) -> printfn "2つ値あり %d %d" x y

// 印字
printValue v1
printValue v2
printValue v3

実行すると以下のような動きになります。

値無し
1つ値あり 1
2つ値あり 1 2

パターンマッチとの組み合わせが素敵な感じです。これがif文による分岐での判別だったら魅力半減ですよね。個人的にはC#とかも、このパターンマッチ取り入れてほしいと思ったり思わなかったりしてます。


さて、この判別共用体ですが、もうちょっと見てみようと思います。判別共用体が判別共用体を持つと・・・?という観点です。

// リンクリスト
type LinkedList =
    | Last
    | Item of int * LinkedList

// リンクリストの定義
let list = Item(0, Item(1, Item(2, Last)))

// リストを印字(再帰)
let rec printList (list : LinkedList) =
    match list with
    | Last -> ()
    | Item(i, tail) ->
        printfn "%d" i
        printList(tail)

// 印字してみる
printList list

こんな風に簡単にリンクリストを定義することが出来ます。実行結果は1 2 3と改行区切りで表示されるだけなので省略します。

その他に、ツリー構造とかも表せます。

// ツリー
type Tree =
    // ノードは値を左右に子を持つ
    | Node of int * Tree * Tree
    // リーフは値だけを持つ。ツリーの末端
    | Leaf of int

// ツリーを組み立ててみる
let tree =
    Node(1, 
        Node(1,
            Leaf 3,
            Leaf 5),
        Node(10,
            Node(100,
                Leaf 10,
                Leaf 3),
            Leaf 22))

// ツリーも再帰的に印字してみる
let rec printTree (tree : Tree) dept =
    // ツリーの値表示時のインデント
    let indent = Array.init dept (fun i -> "    ") |> String.concat ""
    match tree with
    | Node (v, l, r) ->
        // ノードは左側のツリーを印字してから自分の値を印字
        // そして、右側のツリーを印字
        printTree l (dept + 1)
        printf "%s" indent
        printfn "%d" v
        printTree r (dept + 1)
    | Leaf v ->
        // リーフは自分の値だけを印字
        printf "%s" indent
        printfn "%d" v 

// 表示してみよう
printTree tree 0

再帰とかがちょっと複雑?かもしれませんが、ちゃんと1行1行みると大したことないと思います。実行結果は以下のようになります。

        3
    1
        5
1
            10
        100
            3
    10
        22

いちおうツリーっぽくでてる・・・かなぁ・・・????さて、今回作った関数ってツリーのトラバースと、ツリーの要素に対する処理がごっちゃに混ざってます。ここらへん綺麗に分離するともうちょっとよさげですよね。案としては、要素に対してする処理を関数で渡すようにするというのがあります。だが、今回は却下します。

以下のように前やったシーケンスに変換してやるととてもいい感じになったりします。上の表示処理と同じ結果が出るものをシーケンスに変換してシーケンスの関数を適用して出力するプログラムを書いてみます。

// ツリー
type Tree =
    // ノードは値を左右に子を持つ
    | Node of int * Tree * Tree
    // リーフは値だけを持つ。ツリーの末端
    | Leaf of int

// ツリーを組み立ててみる
let tree =
    Node(1, 
        Node(1,
            Leaf 3,
            Leaf 5),
        Node(10,
            Node(100,
                Leaf 10,
                Leaf 3),
            Leaf 22))

// Treeをシーケンスに。(ツリーの深さ, 値)のタプルのシーケンスにする
let toSeq (tree : Tree) =
    let rec toSeqInner (tree : Tree) dept =
        seq {
            match tree with
            | Node(v, l, r) ->
                yield! toSeqInner l (dept + 1)
                yield (dept, v)
                yield! toSeqInner r (dept + 1)
            | Leaf v -> yield (dept, v)
        }
    toSeqInner tree 0

// 印字処理
toSeq(tree)
    |> Seq.iter (fun (dept, v) ->
        let indent = Array.init dept (fun i -> "    ") |> String.concat ""
        printf "%s" indent
        printfn "%d" v)

こんな感じにすることで、綺麗にツリーをたどる処理と印字処理を分けることができました。こんな風にわけておくとシーケンスの便利関数を使って夢ひろがりんぐになります。例えば以下のようなことがサクッとできるようになります。

// 検索処理
let dept, value = toSeq(tree) |> Seq.find (fun (dept, v) -> v = 100)
printfn "深さ%dに%dが見つかりました" dept value

結果は以下のようになります。

深さ2に100が見つかりました

以上、判別共用体でした。

過去記事