代数的データ型と再帰的なデータ構造のこと

　やっはろー。もう日付は過ぎていますけど、飛び入りで参加します。[21日目](http://qiita.com/k3_kaimu/items/05f220ae0c93697e1941)と微妙にネタが被ってます！ すみません！

　D言語の標準ライブラリの中でも影の薄い `std.variant`、の中でも影の薄い `Algebraic` は、その名の通り代数的データ型の役割を担っています。

```d
import std.variant;

void main() {
    struct Foo {}
    alias Bar = Algebraic!(int, string, Foo);

    auto bar = Bar(42);
    assert(bar.type == typeid(int));
    assert(bar.get!int == 42);
    
    bar = Bar("answer");
    assert(bar.type == typeid(string));
    assert(bar.get!string == "answer");
    
    bar = Bar(Foo());
    assert(bar.type == typeid(Foo));
    assert(bar.get!Foo == Foo());
}
```

リファレンスには、再帰的な定義ができないと書かれていますが、実は `This` を使うことで自身の配列と連想配列を含めることができます。

```d
import std.stdio;
import std.variant;

void main() {
    alias Spam = Algebraic!(string, This[], This[string]);
    
    auto spam = Spam([Spam("spam"), Spam("spam"), Spam("spam")]);
    writeln(spam); // [spam, spam, spam]
    
    spam = Spam(["egg": Spam("spam"), "bacon": Spam([Spam("egg"), Spam("spam")])]);
    writeln(spam); // ["egg":spam, "bacon":[egg, spam]]
}
```

これを利用すれば、連結リストや二分木、JSON とかも定義できそうです。

　ということで、`Algebraic` と Pegged を使ってオレオレ JSON パーサを書いてみました。Pegged は、D言語で書かれているコンパイルタイムパーサジェネレータです。他に、@youxkei さんの [ctpg](https://github.com/youkei/ctpg) などが有名ですね。

```d
import pegged.grammar;
import std.algorithm, std.array, std.conv, std.string, std.typecons, std.variant;

alias JSON = Algebraic!(This[string], This[], string, double, int, bool, typeof(null));

mixin(grammar(`
JSONParser:
    Value < Object / Array / String / Float / Integer / True / False / Null
    Pair < String ":" Value
    Object < :"{" (Pair (:"," Pair)*)* :"}"
    Array < :"[" (Value (:"," Value)*)* "]"
    String < :doublequote (!doublequote .)* :doublequote
    Float <- Integer "." [0-9]+
    Integer <- ("+" / "-")? ("0" / [1-9] [0-9]*)
    True <- "true"
    False <- "false"
    Null <- "null"
`));

JSON convert(ParseTree tree) {
    switch (tree.name) {
        case "JSONParser":
            return convert(tree.children.front);

        case "JSONParser.Value":
            return convert(tree.children.front);

        case "JSONParser.Object":
            JSON[string] object = null;
            foreach (pair; tree.children) {
                object[pair.children[0].matches.join] = convert(pair.children[1]);
            }
            return JSON(object);

        case "JSONParser.Array":
            return JSON(tree.children.map!convert.array);

        case "JSONParser.String":
            return JSON(tree.matches.join); 

        case "JSONParser.Integer":
            return JSON(tree.matches.join.to!int);

        case "JSONParser.Float":
            return JSON(tree.matches.join.to!double);

        case "JSONParser.True":
            return JSON(true);

        case "JSONParser.False":
            return JSON(false);

        case "JSONParser.Null":
            return JSON(null);

        default:
            throw new Exception(tree.name ~ " is not implemented yet");
    }
}
```

適当にパースしてみます。

```d
import std.stdio;

void main() {
    enum tree = JSONParser(`[{"foo": 42}, ["bar", -42, true], 4.2, false, null]`);
    writeln(tree);

    auto result = convert(tree);
    writeln(result);
}
```

```d
JSONParser [0, 51]["f", "o", "o", ":", "4", "2", "b", "a", "r", "-", "4", "2", "true", "]", "4", ".", "2", "false", "null", "]"]
 +-JSONParser.Value [0, 51]["f", "o", "o", ":", "4", "2", "b", "a", "r", "-", "4", "2", "true", "]", "4", ".", "2", "false", "null", "]"]
    +-JSONParser.Array [0, 51]["f", "o", "o", ":", "4", "2", "b", "a", "r", "-", "4", "2", "true", "]", "4", ".", "2", "false", "null", "]"]
       +-JSONParser.Value [1, 12]["f", "o", "o", ":", "4", "2"]
       |  +-JSONParser.Object [1, 12]["f", "o", "o", ":", "4", "2"]
       |     +-JSONParser.Pair [2, 11]["f", "o", "o", ":", "4", "2"]
       |        +-JSONParser.String [2, 7]["f", "o", "o"]
       |        +-JSONParser.Value [9, 11]["4", "2"]
       |           +-JSONParser.Integer [9, 11]["4", "2"]
       +-JSONParser.Value [14, 32]["b", "a", "r", "-", "4", "2", "true", "]"]
       |  +-JSONParser.Array [14, 32]["b", "a", "r", "-", "4", "2", "true", "]"]
       |     +-JSONParser.Value [15, 20]["b", "a", "r"]
       |     |  +-JSONParser.String [15, 20]["b", "a", "r"]
       |     +-JSONParser.Value [22, 25]["-", "4", "2"]
       |     |  +-JSONParser.Integer [22, 25]["-", "4", "2"]
       |     +-JSONParser.Value [27, 31]["true"]
       |        +-JSONParser.True [27, 31]["true"]
       +-JSONParser.Value [34, 37]["4", ".", "2"]
       |  +-JSONParser.Float [34, 37]["4", ".", "2"]
       |     +-JSONParser.Integer [34, 35]["4"]
       +-JSONParser.Value [39, 44]["false"]
       |  +-JSONParser.False [39, 44]["false"]
       +-JSONParser.Value [46, 50]["null"]
          +-JSONParser.Null [46, 50]["null"]

[["foo":42], [bar, -42, true], 4.2, false, null]
```

パーサジェネレータつよい。お粗末さまでした。

> [std.variant - D Programming Language](http://dlang.org/phobos/std_variant.html)

> [PhilippeSigaud/Pegged - GitHub](https://github.com/PhilippeSigaud/Pegged)

> [コンパイル時にも動くJSON パーサをサクっと作ってみる - Qiita](http://qiita.com/youxkei/items/001ff5ac3640017859ce)

> [PEG 基礎文法最速マスター - @kmizu の日記](http://kmizu.hatenablog.com/entry/20100203/1265183754)