On Vox: Объясните, а?

[migmit]

Вот есть хаскельный код (пример упрощён до предела):

data P a = P a (forall b. b -> P (a, b))

Нормально компилится, если указать прагму LANGUAGE RankNTypes в GHC или ключик -98 в Hugs-е.
Можно написать несколько "генераторов" для такого P:

sameValue :: a -> P a
sameValue x = P x (\y -> sameValue (x, y))

firstRest :: a -> a -> P a
firstRest x y = P x (\z -> sameValue (y, z))

switching :: a -> a -> P a
switching x y = P x (\z -> switching (y, z) (x, z))

Как сделать это на C++???
Я попробовал, моего плюс-фу не хватило. Светилы, если вы есть, можете подсказать?
Хочется что-то вроде этого:

#include <map>
template <class A> class P {
  A car;
  template <class B> virtual P<std::pair<A,B> > cdr (B) = 0;
};

Не заработает, ибо template и virtual вместе не живут. Убрать virtual нельзя - класс определяется как абстрактный, реализация функции cdr будет разной (см. выше), но эту разницу надо скрыть "под капотом", указывая везде базовый класс.
Как?

Originally posted on migmit.vox.com

Comments

[mr-aleph.livejournal.com]

имхо, "типобезопасно" никак не сделать... а вот типонебезопасно легко... гоню, я не знаю как типонебезопастно сделать тоже самое... имхо никак...

о я начинаю прозревать... такого в С++ нельзя сделать, пальцевое рассуждение следуюшее:

шаблон сам по себе не существует, существуют лишь его инстанциирования, это раз.
два, template<class B> != "forall b", вот допустим ты захочешь сделать такую реализацию:

template <class B> virtual P<std::pair<A,B> > cdr (B b) {
  zzzz(b);
  return std::pair<A,B>(car, b)
}

С++ компилятор не будет разбираться с типами и наличием правильной перегрузки zzzz до момента инстанциирования... А у тебя есть желание, чтобы происходило инстанциирование не этого шаблона, а того который задаётся у предка... Т.е. у компилятора нет связи между точкой инстанциирования и точкой определения шаблона... Вот собственно и всё. Получается "forall b" сделать нельзя. Я думаю можно сделать ограниченный forall, где b пробегает некоторый фиксированный список...

p.s. переслал знакомому C++ гуру (esil0x) =)

[migmit.vox.com (from livejournal.com)]

То, что template virtual не пройдёт - это ёжику понятно.

Скажу по секрету, я даже в курсе, что мой тип P изоморфен такому:

data P1 a = P1 a (P1 a)

а функцию можно написать отдельно:

cdr :: P1 a -> b -> P1 (a, b)
cdr (P1 x p) y = P1 (x, y) $ cdr p y

Из свободных теорем как-нибудь должно следовать, что они изоморфны - в конце концов, на y никакие ограничения не накладываются, так что ничего, кроме как всё время возвращать его же, мы сделать не в состоянии (не совсем правда, можно ещё жопу возвращать - ленивый язык возражать не будет).

Вот только подобное преобразование кода - вещь нетривиальная, и хорошо бы самому это не делать - а ещё лучше - вообще не делать.

[mr-aleph.livejournal.com]

о, мой мозг...

мой основной поинт в том, что для C++ не существует аналога forall в принципе.

[migmit.vox.com (from livejournal.com)]

Шо-то наглючил я с этой cdr, она иначе пишется. Но суть та же.

Фишка в том, что, убрав virtual, я как раз и получаю forall. Но непереопределяемый.

[mr-aleph.livejournal.com]

не совсем, в Haskell ежели написано forall, то это именно forall, статически доказанный.
В C++ ты можешь там написать зюзюзю(b) и всё будет окей, до тех пор пока ты непопробуешь передать туда B для которого нет зюзюзю(b)

[migmit.vox.com (from livejournal.com)]

Тру, однако. Вообще как-то мне кажется, что статическая типизация в C++ - это такой обман.

[esil0x.livejournal.com]

Понятно что template и virtual сделать вместе нельзя.

Но надо действительно понять, требуется ли virtual. Т. е. действительно ли нужен динамический полиморфизм, при котором один и тот же код (имеется в виду инстанцированный код) будет работать с разными типами, наследованными от P. Если это действительно так, то тогда множество типов, передаваемых в cdr, конечно и известно, и его можно описать например в виде параметра шаблона P (можно использовать например mpl::vector).

Если же динамический полиморфизм не требуется, то у шаблона P можно ввести дополнительный параметр, который будет предоставлять реализацию для cdr.

P. S. Вообще я себе не совсем ясно представляю что делает приведённый код на haskell. Надо будет разобраться в нём подробнее, чтобы точно говорить.

P. P. S. А при решении какой задачи возникла эта проблема? Есть такое ощущение, что эта маленькая проблема является частью некоторой задачи со списками типов.

[migmit.vox.com (from livejournal.com)]

Хочется делать потом что-то вроде

 < >   : <> {
  ( ) : <>(arg) {}
  < > <::<,> > ( ) {
    <::<,> > (::make_pair(->car, arg2));
     result;
  }
}

Это аналог функции sameValue выше.

[esil0x.livejournal.com]

А вот такой код не может подойти:



    

 <

     A,

     <

         XT1,

         XT2

    >  pair_maker

>  P {

:



  A car;



  P( A & a): car(a) {}

  

   < B>

   cdr_result {

     P<std::pair<A, B>, pair_maker> type;

  };

  

   < B> P< std::pair<A, B>, pair_maker > cdr ( B & b) {

     P< std::pair<A, B>, pair_maker >(pair_maker<A, B>()(car, b));

  }

};



 < T1,  T2>

 same_value {

    std::pair<T1, T2> ()( T1 & t1,  T2 & t2) {

         std::make_pair(t1, t2);

    }

};





 main() {

     P<, same_value> P1;

     P1::cdr_result<std::string>::type P2;

     P2::cdr_result<>::type P3;

    

    P1 p1();

    P2 p2 = p1.cdr(std::string());

    P3 p3 = p2.cdr();



    

     ;

}


?

Тут вместо виртуальных функций используется дополнительный параметр шаблона.

[migmit.vox.com (from livejournal.com)]

Так, что-то я не очень сообража...

Как будет выглядеть, например, firstRest из исходного поста? Если бы были template virtual, то всё ясно:

template <class A> class FirstRest : P<A> {
public:
  FirstRest(A first, A rest) : P<A>(first), rest_(rest) {}
  template<class B> P<std::pair<A,B> > cdr(B arg2) {
    // здесь именно SameValue, а не FirstRest!!!
    SameValue<std::pair<A,B> > result(std::make_pair(rest_, arg2));
    return result;
  }
private:
  A rest_;
}

Сорри, емакса под рукой нет, придётся обойтись без подсветки.

И ещё, чтобы два раза не бегать: в typedef-е внутри cdr_result мы не напоремся на тот же баг - что в определении шаблона сам шаблон предполагается полностью инстанцированным? (Компилятора у меня тоже под рукой нет)

[esil0x.livejournal.com]

Я сейчас попробовал реализовать FirstRest с дополнительным параметром шаблона и подумал вот о чём.
Какая задача у объекта P? У него имеется переменная car и шаблонная функция cdr. Если нас устраивает статический полиморфизм, то вообще не обязательно, чтобы SameValue и FirstRes являлись одним и тем же шаблоном. Будет достаточно, если они будут удовлетворять определённым ограничениям.

Например, можно реализовать это таким образом:

 < A>  SameValue {
:
  A car;

  SameValue(A arg): car(arg) {}
  
   < B>
   cdr_result {
     SameValue<std::pair<A,B> > type;
  };
  
  < B> SameValue<std::pair<A,B> > cdr(B arg2) {
    SameValue<std::pair<A,B> > result(std::make_pair(->car, arg2));
     result;
  }
};

 < A>  FirstRest {
:
  A car;

  FirstRest(A first, A rest): car(first), rest_(rest) {}

   < B>
   cdr_result {
     SameValue<std::pair<A,B> > type;
  };
  
  < B> SameValue<std::pair<A,B> > cdr(B arg2) {
    SameValue<std::pair<A,B> > result(std::make_pair(rest_, arg2));
     result;
  }
:
  A rest_;
};

 main() {
     FirstRest<> P1;
     P1::cdr_result<std::string>::type P2;
     P2::cdr_result<>::type P3;

    P1 p1(, );
    P2 p2 = p1.cdr(std::string());
    P3 p3 = p2.cdr();
        
     ;
} Но нужно понять, действительно ли не требуется динамического полиморфизма (например хранить указатели на объекты в одном и том же списке). Т. е. нужно учитывать то, какое будет использование. Если окажется, что всё-таки нужна иерархия классов, то тогда уже будут проблемы. ()

[migmit.vox.com (from livejournal.com)]

Гм. Вполне представляю себе использование типа int f(P a, P b) {... a.cdr(b.car) ...} - ну, или что-то в этом духе. Насчёт списков не задумывался пока. Ну и плюс - A car указывается в каждом из них, что есть бойлерплейт.

[esil0x.livejournal.com]

По поводу typedef: всё будет нормально, т. к. там в typedef стоит depended name, т. е. то, что зависит от параметра шаблона. Поэтому на момент определения шаблон не должен быть полностью инстанцирован.
Да, возможно Вам потребуется добавить typename в некоторых местах. Я тестировал на msvc, а они допускает вольности с typename'ами.

[migmit.vox.com (from livejournal.com)]

Про P.S. Делает-то он понятно что. Если у нас есть значение типа P Int, это значит, что
а) у нас есть значение типа Int.
б) для любого другого типа b и значения типа b есть значение типа (Int, b) - скажем, если есть строка, то есть и значение типа (Int, String)
в) для любых ДВУХ типов b и c и значений этих типов есть значение типа ((Int, b), c) - скажем, ((Int, String), Float).
... до бесконечности.
Пример, как я и сказал, упрощённый, поэтому более-менее ясно, каковы будут эти значения - но сие не имеет отношения к делу.

[migmit.vox.com (from livejournal.com)]

Про P.P.S.: Вообще-то я работал на хаскеле. У меня был некий код, который работал для любого класса C (скажем, для класса Ord, или Eq), для которого имеется инстанс (C a, C b) => C (a,b). То есть, если типы a и b относятся к классу C, то пара из них - тоже, автоматически. Абстрагировать класс в хаскеле нельзя, поэтому я попытался сделать тип, для которого что-то подобное содержится в нём самом:

  a   ( a) (forall b  b   (a, b))

Ну и просто заинтересовался, можно ли перенести соответствующую идиому в C++. К спискам типов оно отношения не имеет.