Можно ли вообще реализовать оператор amb в D? - PullRequest
Новая
       27

Можно ли вообще реализовать оператор amb в D?

10 голосов
/ 31 августа 2010

Можно ли вообще реализовать оператор amb в D?

http://www.haskell.org/haskellwiki/Amb
http://www.randomhacks.net/articles/2005/10/11/amb-operator

Сортировка того, о чем я думаюof is: 

amb([1, 2]) * amb([3, 4, 5]) == amb([3, 4, 5, 6, 8, 10])
amb(["hello", "world"]) ~ amb(["qwerty"]) == amb(["helloqwerty", "worldqwerty"])
amb(["hello", "world"]) ~ "qwerty" == amb(["helloqwerty", "worldqwerty"])
amb(["hello", "very long string"]).length = amb([5, 16])

В последних двух примерах действительно необходимо «поднять» ~ и .length в «контекст» amb (монаду?).В первых двух примерах операторы должны быть просто применены к содержимому окружения.

Я сделал небольшую попытку, но у меня возникают проблемы при попытке поднять операторы / методы обернутого типа /свойства (*, ~ и .length в этом примере).Как это сделать в D?

Спасибо,

Крис.

1 Ответ

12 голосов
/ 31 августа 2010

Да, это возможно. Вот что я придумал. 

import std.range;
import std.algorithm;
import std.stdio;
import std.functional;
import std.math;
import std.string;

struct AmbRange(R1, R2, alias Op)
{
public:
    this(R1 _r1, R2 _r2) { r1 = _r1; r2 = r2c = _r2; }

    void popFront()
    {
        r2.popFront();
        if (r2.empty) { r2 = r2c; r1.popFront(); }
    }

    @property auto front() { return Op(r1.front, r2.front); }
    @property bool empty() { return r1.empty; }

private:
    R1 r1;
    R2 r2, r2c;
}

struct Amb(R)
{
    alias ElementType!(R) E;

public:
    this(R r) { this.r = r; }

    auto opBinary(string op, T)(T rhs) if (!is(T U : Amb!(U)))
    {
        alias binaryFun!("a"~op~"b") Op;
        return map!((E e) { return Op(e, rhs); })(r);
    }

    auto opBinaryRight(string op, T)(T lhs) if (!is(T U : Amb!(U)))
    {
        alias binaryFun!("a"~op~"b") Op;
        return map!((E e) { return Op(lhs, e); })(r);
    }

    auto opBinary(string op, T)(T rhs) if (is(T U : Amb!(U)))
    {
        alias binaryFun!("a"~op~"b") Op;
        return AmbRange!(R, typeof(rhs.r), Op)(r, rhs.r);
    }

    auto opDispatch(string f, T ...)(T args)
    {
        mixin("return map!((E e) { return e."~f~"(args); })(r);");
    }

    auto opDispatch(string f)()
    {
        mixin("return map!((E e) { return e."~f~"; })(r);");
    }

private:
    R r;
}

auto amb(R)(R r) { return Amb!R(r); }

void main()
{
    auto r1 = 2 * amb([1, 2, 3]);
    assert(equal(r1, [2, 4, 6]));

    auto r2 = amb(["ca", "ra"]) ~ "t";
    assert(equal(r2, ["cat", "rat"]));

    auto r3 = amb(["hello", "cat"]).length;
    assert(equal(r3, [5, 3]));

    auto r4 = amb(["cat", "pat"]).replace("a", "u");
    assert(equal(r4, ["cut", "put"]));

    auto r5 = amb([1, 2]) * amb([1, 2, 3]);
    assert(equal(r5, [1, 2, 3, 2, 4, 6]));
}

Большое спасибо BCS за выяснение того, как разрешить неоднозначности binaryOp.

Мне пришлось создать новый диапазон для обхода результата бинарной операции между двумя Amb, но я думаю, что в любом случае это работает лучше.

Для тех, кто новичок в D и любопытен, все эти вещи string выполняются во время компиляции, так что нет никакого синтаксического анализа во время выполнения или чего-то подобного - это в значительной степени так же эффективно, как и ручное кодирование в к.

...