Аппликативность диагонального функтора

[thedeemon]

Занимался тут исследовательским/экспериментальным кодом, а там получилось, что одни и те же действия делаются с двумя похожими наборами данных (горизонтальные и вертикальные координаты), большую часть времени независимо. И захотелось вместо того, чтобы писать одинаковый код и следить, как бы не передать куда иксы вместо игреков, просто лифтануть имеющиеся функции, чтобы они работали сразу с парами значений.
На хаскеле для этого достаточно описать, каким образом диагональный функтор (гомогенные туплы) является аппликативным. Что-то вроде:

data Pair a = P a a 
  deriving (Functor, Show)

instance Applicative Pair where
  pure x = P x x
  P fa fb <*> P xa xb = P (fa xa) (fb xb)

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

Но у меня тот проектик был не на хаскеле, а на D. Там подход чуть иной. Сперва как оно выглядит в использовании:

unittest {
    int  f1(string s)                { return s.length; }
    int  f2(int x, int y)            { return x + y; }
    bool f3(int a, string b, bool c) { return c && (a <= b.length); }

    auto r1 = tmap!f1( tuple("aa", "bbb") );
    writeln(r1); // (2,3)

    auto r2 = tmap!f2( tuple(10,20), r1 );
    writeln(r2); // (12, 23)

    auto r3 = tmap!f3( r2, tuple("one", "five"), tuple(true, false));
    writeln(r3); // (false, false)
}

А вот как это реализовано:

alias Dbl(T) = Tuple!(T,T);
alias Double(Ts...) = staticMap!(Dbl, Ts);

auto tproject(int pos, Ts...)(Ts args) {
    enum projStr = iota(args.length).map!(i => format("args[%s][%s]", i, pos)).join(", "); 
    return mixin("tuple(" ~ projStr ~ ")");
}

auto tmap(alias f)(Double!(Parameters!f) args) {
    return tuple(f(args.tproject!0.expand), f(args.tproject!1.expand));
}

По шагам:
tmap получает некоторую функцию f в качестве compile-time-known параметра, и набор рантайм-аргументов args, типы которых вычисляются как Double!(Parameters!f). Parameters - это типовая ф-я из стандартной библиотеки, она возвращает список типов аргументов переданной ей ф-ии. К этому списку мы применяем типовую функцию Double, которая просто маппит список, преобразуя каждое значение функцией Dbl, которая всякий Т превращает в Tuple!(T,T), где Tuple - контейнер из стандартной библиотеки. В результате, например, если исходная функция f принимала аргументы типов (string, bool, int[]), то tmap!f будет принимать аргументы типов (Tuple!(string, string), Tuple!(bool, bool), Tuple!(int[], int[])).
Возвращает tmap, понятное дело, тоже тупл, полученный применением исходной ф-ии к соответствующим элементам входных туплов. Для этого ей надо разделить набор входных туплов на два набора - левые и правые половины оных. Для такой проекции из набора туплов в набор их частей описана ф-я tproject. В принципе, ее наверняка можно реализовать более чистым образом, но я использовал тупую кодогенерацию. Если args это набор туплов, то args[0] это первый тупл, а args[0][0] это первое значение из первого тупла. Т.е. чтобы взять все первые значения нам нужен tuple(args[0][0], args[1][0], args[2][0]...). Такая строчка генерится в компайл-тайме в первой строке tproject и тут же вставляется во вторую строчку, так получается нужное значение.
А, насчет синтаксиса. args.tproject!0 это (благодаря Universal Function Call Syntax) то же самое, что tproject!(0)(args), т.е. передаем компайл-тайм аргумент 0 (это будет pos), и рантайм-аргумент args, а второй компайл-тайм аргумент Ts - это список типов args, он выводится/извлекается автоматически. Три точки говорят, что это не одно значение, а набор значений (несколько аргументов). Чтобы развернуть библиотечную структуру Tuple в набор передаваемых значений, делается .expand.
Вот и все, дешево и сердито. А как такое делается на вашем языке программирования?

Comments

[levgem.livejournal.com]

я честно пытался.

Представляю...

[Александр Костриков (from livejournal.com)]

Пришёл человек код править, а там "аппликативность диагонального функтора"

Re: Представляю...

[levgem.livejournal.com]

а рядом сидит начальник типа меня и спрашивает: какого хера не получается быстро ебануть тут красненьким!

[kodt-rsdn.livejournal.com]

На питоне

def tmap(fs, *xyzs):
  '''
  tmap((f1,...,fn), (x1,...,xn), (y1,...,yn), ..., (z1,...,zn))
  = (f1(x1,y1,...,z1),...,fn(xn,yn,...,zn))
  '''
  return tuple(fi(*xyzi) for fi,xyzi in zip(fs,zip(*xyzs)))

def pure(n,x):
  return tuple([x]*n)


def unary(x):
  return '<%s>' % x

def binary(x,y):
  return '{%s,%s}' % (x,y)

def ternary(x,y,z):
  return '[%s,%s,%s]' % (x,y,z)

N = 10
print tmap(pure(N,unary), range(0,N))
print tmap(pure(N,binary), range(0,N), range(100,N+100))
print tmap(pure(N,ternary), range(0,N), range(100,N+100), range(200,N+200))

При желании, можно добавить инспекцию, следящую за арностью.
При очень большом желании, можно создавать функцию нужной арности - чтобы какой-нибудь purefun(fs) правильно инспектировался и вызывался

fN = purefun(pure(N,ternary))
print fN(range(0,N), range(100,N+100), range(200,N+200))

[zeit-raffer.livejournal.com]

Только это не диагональный функтор
Диагональный функтор выдает последовательность одинаковых типов Delta: С -> C x C
А мы ее здесь дополнительно перемножаем.

Это у нас http://ncatlab.org/nlab/show/power

[thedeemon.livejournal.com]

Описанный в начале data Pair a = P a a
не диагональный?
У меня везде сохраняется гомогенность пар.

[zeit-raffer.livejournal.com]

Ну, это вопрос терминологии. Диагональным называется функтор C->CxC, который просто копирует два раза тип, но не перемножает. У него есть сопряженные, откуда берется монада и комонада на С. Вы записали, фактически, тот функтор C->C, на котором есть структура монады (изоморфный Reader Bool). А в ТК он называется power.

[thedeemon.livejournal.com]

А, да, понятно. Ну будем в кавычках его так величать.

[109.livejournal.com]

public Tuple<TResult, TResult> Apply<T1, TResult>(
	Func<T1, TResult> f,
	Tuple<T1, T1> t1)
{
	return new Tuple<TResult, TResult>(
		f(t1.Item1), 
		f(t1.Item2));
}
public Tuple<TResult, TResult> Apply<T1, T2, TResult>(
	Func<T1, T2, TResult> f,
	Tuple<T1, T1> t1,
	Tuple<T2, T2> t2)
{
	return new Tuple<TResult, TResult>(
		f(t1.Item1, t2.Item1), 
		f(t1.Item2, t2.Item2));
}
public Tuple<TResult, TResult> Apply<T1, T2, T3, TResult>(
	Func<T1, T2, T3, TResult> f,
	Tuple<T1, T1> t1,
    Tuple<T2, T2> t2,
    Tuple<T3, T3> t3)
{
	return new Tuple<TResult, TResult>(
		f(t1.Item1, t2.Item1, t3.Item1),
		f(t1.Item2, t2.Item2, t3.Item2));
}

[109.livejournal.com]

ну и да, конечно это всё легко кодогенерировать на лету (тут как бы написан результат кодогенерации), но смысла большого нет, потому что ну кто использует функции с больше чем тремя аргументами?

[sleepy-drago.livejournal.com]

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

[binf.livejournal.com]

Прочитал у Вас, что в D можно относительно легко сделать тип функтором, да ещё и со статической проверкой законов функторов. Я так понимаю, что (>>=) тоже не проблема. А имеется ли там возможность сделать do нотацию или вычислительное выражение как F#?

[thedeemon.livejournal.com]

Увы, мне приемлемого способа это сделать пока не удалось придумать, синтаксис не настолько гибкий. В смысле, чтобы это все еще был код на языке, а не чистый DSL, как в том же Pegged или Diet шаблонах vibe.d.

[binf.livejournal.com]

Спасибо. Что ж, идеального не бывает.