немного D

[thedeemon]

xeno_by спрашивает:
"Как в D написать функцию map, которая: 1) определена для всех коллекций (листов, векторов, чего угодно, соответствующего базовому интерфейсу), 2а) на выходе выдает ту же самую коллекцию, параметризованную типом результата маппера, 2б) за исключением случая, когда маппер возвращает Boolean - в таком случае возвращаемый тип map должен быть BitVector."

Отвечаем. В D контейнерам принято уметь представлять себя в виде range - дивного итератора. Для рэнджей определены всевозможные алгоритмы и комбинаторы (filter/map/reduce/chain/zip/take etc.), они возвращают тоже range и работают "лениво". Соответственно, чтобы описать искомую функцию, нужно лишь уметь превратить range отмапленных значений обратно в исходный контейнер. У многих из них уже есть подходящий для этого конструктор, и основная сложность лишь одна: на вход нам приходит уже конкретизированный тип (например, "список интов"), а нам нужен конструктор типов ("список"), чтобы сконструлить тип результата. Для ее преодоления добавим к общим умениям контейнеров способность отображать типы помимо текущего. Определим немного своих контейнеров на базе имеющихся в стандартной библиотекe:

struct MyList(T) {
    SList!T data;  
    this(R)(R rng) { data = SList!T(rng); }  
    alias data this; 
    template Mapped(U) { alias Mapped = MyList!U; }
}

struct MyArray(T) {
    T[] data;
    this(R)(R rng) { data = rng.array; }
    alias data this;
    template Mapped(U) { alias Mapped = MyArray!U; }
}

В каждой такой структуре мы указываем реально используемый контейнер, делаем конструктор, принимающий range с данными, экспортируем все свойства и умения внутреннего контейнера как свои, и определяем функцию на типах, дающую тип применения данного шаблона к любому другому типу U. Теперь опишем искомую функцию map:

auto mymap(C,A,B)(C xs, B delegate(A) f)
{
    static if (is(B==bool)) {
        Array!bool arr;
        arr.insert(xs[].map!f);
        return arr;
    } else
        return C.Mapped!B( xs[].map!f );  
}

Она берет контейнер xs типа C, оператором [] получает range из его элементов, для него вызывает стандартную функцию map, применяющую переданную функцию f из А в В, получаем range из значений типа В, из которых строим контейнер типа C.Mapped!B, т.е. ту же структуру, но с элементами типа В. Все это делается в случае, когда В это не bool. Если B==bool, то в качестве контейнера мы выбираем Array из стандартной библиотеки, который как раз хранит булевы значения в виде вектора битов, а не массива bool'ов. Проверяем:

void show(T)(T xs) { writeln(T.stringof, " ", xs[]); }

void main(string[] argv)
{
    auto lst = MyList!int([1,2,3]);
    show(lst);

    auto arr = MyArray!int([4,5,6]);
    show(arr);
   
    mymap(lst, (int x) => x.to!string).show;
    mymap(arr, (int x) => x.to!string).show;
    mymap(lst, (int x) => (x & 1) > 0).show;
    mymap(arr, (int x) => (x & 1) > 0).show;
}

Выводит:
MyList!(int) [1, 2, 3]
MyArray!(int) [4, 5, 6]
MyList!(string) ["1", "2", "3"]
MyArray!(string) ["4", "5", "6"]
Array!(bool) [true, false, true]
Array!(bool) [false, true, false]

На самом деле можно было проще, без создания своих оберток над контейнерами. Как-то так:

auto mymap(alias C,A,B)(C!A xs, B delegate(A) f)
{
    static if (is(B==bool)) {
        Array!bool arr;
        arr.insert(xs[].map!f);
        return arr;
    } else
        return make!(C!B)( xs[].map!f );  
}

Тут С оказывается не конкретным типом, а шаблоном-конструктором типа, на входе получаем штуку типа С!А, и выдаем в общем случае С!В, кроме специального случая для bool'ов. Так тоже работает, но имя контейнера теряется, выводится:
C!(string) ["1", "2", "3"]
C!(string) ["4", "5", "6"]

Comments

[xeno-by.livejournal.com]

А можно увидеть тестовые вызовы функций, которые запускались для "так тоже работает"?

[thedeemon.livejournal.com]

    auto lst = SList!int([1,2,3]);
    show(lst);

    auto arr = MyArray!int([4,5,6]);
    show(arr);
    
    mymap(lst, (int x) => x.to!string).show;
    mymap(arr, (int x) => x.to!string).show;
    mymap(lst, (int x) => (x & 1) > 0).show;
    mymap(arr, (int x) => (x & 1) > 0).show;

выводит
SList!(int) [1, 2, 3]
MyArray!(int) [4, 5, 6]
C!(string) ["1", "2", "3"]
C!(string) ["4", "5", "6"]
Array!(bool) [true, false, true]
Array!(bool) [false, true, false]

[xeno-by.livejournal.com]

Интересные у ди возможности по выводу типов. Неплохо! А С!(string) это, получается, баг?

[thedeemon.livejournal.com]

Скорее, не баг, а надо было выбирать, что при инстанциировании такого шаблона считать именем типа, и сделали такой вот выбор, видимо для более понятных сообщений об ошибках.

[xeno-by.livejournal.com]

Кроме того, можно ли переписать mymap так, чтобы он не был подвержен expression problem?

[thedeemon.livejournal.com]

Разверни, где именно ее видишь.

[xeno-by.livejournal.com]

Чтобы можно было, не перекомпилируя mymap, написать свою коллекцию, которая будет обрабатываться специальным образом.

[thedeemon.livejournal.com]

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

[xeno-by.livejournal.com]

Если делать на интерфейсах, то тогда возвращаемый тип mymap будет неточным.

[kodt-rsdn.livejournal.com]

(недовольно бурча)
Есть ли хоть один язык, в котором шаблоны-женерики выглядели бы нормально, а не ярким пятном на сером фоне остального синтаксиса?
Пожалуй, только в хаскелле к ним однородно подошли (я имею в виду классы типов). Хотя это я ещё темплит-хаскелл не курил... но темплит-хаскелл - это макросы, а макросам всё можно.

[thedeemon.livejournal.com]

Имхо, тут они довольно органично вписались.

[kodt-rsdn.livejournal.com]

Ну не знаю. В плюсях перегрузили меньше-больше, в Д - восклицание (отрицание).

Во-первых, это читается вприпрыжку:
map! bool! О шея лебедя! о грудь! о барабан!

Во-вторых, ещё один оператор стал унарным+бинарным.

В-третьих, сигнатура шаблона выглядит так же, как сигнатура функции, а применение - не так же. В отличие от плюсей или жабы.

auto foo(A,B,C)(C,B,A) {}
auto bar(A,B,C) {}

[thedeemon.livejournal.com]

Да, это все правда. Но это мелочи, к которым быстро привыкаешь.
Зато в некоторых языках, не будем показывать пальцем, A.b и A . b имеют совершенно разный смысл, а также $x и $ x.

[kodt-rsdn.livejournal.com]

оператор вайтспейс во всей красе :)
не будем туда же тыкать пальцем про оператор табуляции, который позаковыристее будет, чем в питоне.

[nivanych.livejournal.com]

Нууу, в агдочке ещё, хотя это и немного спорно.
Ну и в CoQ есть совсем напрямую классы типов.