std.variant.Algebraic test use case

[dlangBugzillaToGithub]

bearophile_hugs reported this on 2010-10-10T14:42:54Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=5037

CC List

• andrei (@andralex)

Description

Created attachment 781
One memory/runtiume performance test for the compiler/binary for the flatten

This isn't a bug report.

In dmd 2.049 the docs for std.variant.Algebraic state:

> BUGS: Currently, Algebraic does not allow recursive data types.
> They will be allowed in a future iteration of the implementation. 


Once that limit is lifted, the following problem may be used to see if the API
of Algebraic is well designed. The problem is, given an arbitrary nested list
of values and sublists:

[[1], 2, [[3,4], 5], [[[]]], [[[6]]], 7, 8, []]

To flatten it fully into this result:
[1, 2, 3, 4, 5, 6, 7, 8]

This is a solution that minimizes heap activity, it doesn't use Algebraic but
it uses a tagged union:


import std.stdio: writeln;
import std.conv: to;

struct TreeList(T) {
    union {
        TreeList!T[] arr;
        T data;
    }
    bool isArray = true;

    static TreeList!T opCall(Types...)(Types items) {
        TreeList!T result;

        foreach (i, el; items)
            static if (is(Types[i] == T)) {
                TreeList!T item;
                item.isArray = false;
                item.data = el;
                result.arr ~= item;
            } else
                result.arr ~= el;

        return result;
    }

    TreeList!T flatten() {
        TreeList!T result;

        if (this.isArray)
            foreach (el; this.arr)
                result.arr ~= el.flatten().arr;
        else
            result.arr ~= this;

        return result;
    }

    string toString() {
        if (isArray)
            return to!string(arr, "[", ", ", "]");
        else
            return to!string(data);
    }
}

void main() {
    alias TreeList!(int) L; // 12 bytes if T is int
    auto l = L(L(1), 2, L(L(3,4), 5), L(L(L())), L(L(L(6))), 7, 8, L());
    writeln(l);
    writeln(l.flatten());
}


Well implemented Algebraic types are supposed to allow a shorter, simpler and
equally runtime/memory-efficient solution to this problem (the efficiency may
be tested with the large list literal in the attach file).

!!!There are attachements in the bugzilla issue that have not been copied over!!!

[dlangBugzillaToGithub]

andrei (@andralex) commented on 2016-10-14T13:14:16Z

We have limited support for self-referential structures now, so we should be able to work on this.