Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

 やっはろー。もう日付は過ぎていますけど、飛び入りで参加します。21日目と微妙にネタが被ってます! すみません!

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

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 を使うことで自身の配列と連想配列を含めることができます。

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 などが有名ですね。

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");
    }
}

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

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);
}
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

PhilippeSigaud/Pegged - GitHub

コンパイル時にも動くJSON パーサをサクっと作ってみる - Qiita

PEG 基礎文法最速マスター - @kmizu の日記

woxtu
世界の上にタンポポをのせる仕事をしています。
qiitadon
Qiitadon(β)から生まれた Qiita ユーザー・コミュニティです。
https://qiitadon.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away