Равные длины векторов

>да не вопрос. а давайте вы ответной мерой доброй воли перестанете обобщать своё мнение на всех присутствующих?
Не вопрос, хотя и не вижу в своей реплике особого криминала.

Не вопрос, хотя и не вижу в своей реплике особого криминала.

а я - в своих :)

не понятно, как массив может быть произвольного размера, если полей всего два.

http://lisper.ru/pcl/they-called-it-lisp-for-a-reason-list-processing

Ключом к пониманию списков, является осознание того, что они, по большей части, иллюзия, построенная на основе объектов более примитивных типов данных. Эти простые объекты - пары значений, называемые cons-ячейкой, от имени функции CONS, используемой для их создания

>> Вызов виртуального метода - это статика или ad-hoc полиморфизм?

Само понятие «виртуальный метод» означает, что используется ООП, причём в самом уродском варианте (C++). Следовательно - только ad-hoc

Я знаю два подхода - либо проверить в рантайме метки типов вовлеченных в операцию и выбрать подходящий обработчик из некоей таблицы либо вставить этот обработчик in-place, подобрав реализацию операции на основании статической сигнаруры типа. Первое очевидно это динамическая типизация, второе - статическая. Как можно реализовать второе основываясь не на константантных данных, а на данных полученных в рантайме из IO я лично не представляю. Вы наверное что-то путаете.

Функциональное программирование, говорите?

Вот вам Java:

import java.io.*;
abstract class ScalarProduct<A> {
    public abstract Integer scalarProduct(A second);
}
class Nil extends ScalarProduct<Nil>{
    Nil(){}
    public Integer scalarProduct(Nil second) {
        return 0;
    }
}
class Cons<A extends ScalarProduct<A>> extends ScalarProduct<Cons<A>>{
    public Integer value;
    public A tail;
    Cons(Integer _value, A _tail) {
        value = _value;
        tail = _tail;
    }
    public Integer scalarProduct(Cons<A> second){
        return value * second.value + tail.scalarProduct(second.tail);
    }
}
class _Test{
    public static Integer main(Integer n){
        return _main(n, 0, new Nil(), new Nil());
    }
    public static <A extends ScalarProduct<A>> Integer _main(Integer n, Integer i, A first, A second){
        if (n == 0) {
            return first.scalarProduct(second);
        } else {
            return _main(n-1, i+1, new Cons<A>(2*i+1,first), new Cons<A>(i*i, second));
            //return _main(n-1, i+1, first, new Cons<A>(i*i, second));
        }
    }
}
public class Test{
    public static void main(String [] args){
        System.out.print("Enter a number: ");
        try {
            BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
            String line = is.readLine();
            Integer val = Integer.parseInt(line);
            System.out.println(_Test.main(val));
        } catch (NumberFormatException ex) {
            System.err.println("Not a valid number");
        } catch (IOException e) {
            System.err.println("Unexpected IO ERROR");
        }
    }
}

MigMit:~ MigMit$ javac -Xlint Test.java
MigMit:~ MigMit$ java Test
Enter a number: 1
0
MigMit:~ MigMit$ java Test
Enter a number: 2
2
MigMit:~ MigMit$ javac -Xlint Test.java
MigMit:~ MigMit$ java Test
Enter a number: 1
0
MigMit:~ MigMit$ java Test
Enter a number: 2
3
MigMit:~ MigMit$ java Test
Enter a number: 3
23
MigMit:~ MigMit$ java Test
Enter a number: 17
38488

Допустим, но полиморфизм как правил реализуется через некое множество функций/методов.

«Как правило» в ООП-языках. И это относится именно к ad-hoc.

Потом не понятно, как массив может быть произвольного размера, если полей всего два.

Про связные списки слышали?

Я знаю два подхода - либо проверить в рантайме метки типов вовлеченных в операцию и выбрать подходящий обработчик из некоей таблицы либо вставить этот обработчик in-place, подобрав реализацию операции на основании статической сигнаруры типа.

Есть ещё третий подход. Использовать ТОЛЬКО ОДИН ОБРАБОТЧИК.

Собственно, это и есть определение параметрического полиморфизма. Ad-hoc-полиморфизм - одна и та же функция работает с разными типами, но при этом код этой функции пишется по-разному для разных типов. Параметрический полиморфизм - одна и та же функция работает с разными типами, и код этой функции всё время один и тот же.

Параметрический полиморфизм эмулируется в C++ шаблонами (и нарушается частичной специализацией шаблонов). Он реализуется в Java дженериками. Он вездесущ в Хаскеле.

Спасибо за пример. Суперская акробатика. Но смысл практического применения стремится к нулю.

Спасибо за пример.

Пожалуйста.

Суперская акробатика.

Да в чём там акробатика-то? В том, что класс наследуется от дженерика с собой же в качестве параметра? Так это i) стандартная для Java техника, когда нужно заюзать дженерик-класс внутри себя, и ii) необязательно - я могу переписать этот пример так, чтобы никакого наследования вообще не было.

Но смысл практического применения стремится к нулю.

Я знаю как минимум одного жаба-программера, работающего в Яндексе, который наверняка подобные вещи использует. Что касается Хаскеля, то для него код вообще совершенно идиоматичный.

, и ii) необязательно - я могу переписать этот пример так, чтобы никакого наследования вообще не было

Упс, виноват. Не могу. Нету в этой грёбаной жабе замыканий.

для обеспечения равенства длин *твоим* способом твои конс-ы вообще не нужны:

struct ScalarProductArg
{
  virtual double scalar_product() const = 0;
  virtual ScalarProductArg* one_up(double, double) = 0;
};
struct ScalarProductArgX: public ScalarProductArg
{
  const double x;
  const double y;
  const ScalarProductArg& tail;

  ScalarProductArgX(double x, double y, const ScalarProductArg& tail): x(x), y(y), tail(tail) {}

  virtual double scalar_product() const { return x*y + tail.scalar_product(); }
  virtual ScalarProductArg* one_up(double x, double y) { return new ScalarProductArgX(x,y,*this); }
};
struct ScalarProductArg0: public ScalarProductArg
{
  virtual double scalar_product() const { return 0; }
  virtual ScalarProductArg* one_up(double x, double y) { return new ScalarProductArgX(x,y,*this); }
};

#include <iostream>

int main(int argc, char** argv)
{
  int n=0;
  std::cout << "enter n: ";
  std::cin  >> n;
  ScalarProductArg* xy = new ScalarProductArg0();
  for( int i=0; i<n; i++ )
    xy=xy->one_up(2*i+1, i*i);
  std::cout << xy->scalar_product() << "\n";

  return 0;
}

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

> Enter a number: 2

2

в то время, как должно быть 3

_______________________________________

насчет полиморфизма — я так и не придумал, как на с++ красиво сделать type erasure, которым явовские дженерики (и видимо программа на хаскеле) отличаются от плюсов.

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

struct Nil {};

template<class T> struct Cons
{
  const double value;
  const T& tail;

  Cons(double value, const T& tail): value(value), tail(tail) {}
};
template<class T> Cons<T> cons(double value, const T& tail) { return Cons<T>(value, tail); }

struct ScalarProductArg
{
  virtual double scalar_product() const = 0;
  virtual ScalarProductArg* one_up(double, double) = 0;
};
struct ScalarProductArgX: public ScalarProductArg
{
  const double x;
  const double y;
  const ScalarProductArg* tail;

  ScalarProductArgX(double x, double y, const ScalarProductArg* tail): x(x), y(y), tail(tail) {}

  virtual double scalar_product() const { return x*y + tail->scalar_product(); }
  virtual ScalarProductArg* one_up(double x, double y) { return new ScalarProductArgX(x,y,this); }
};
struct ScalarProductArg0: public ScalarProductArg
{
  virtual double scalar_product() const { return 0; }
  virtual ScalarProductArg* one_up(double x, double y) { return new ScalarProductArgX(x,y,this); }
};

template<class T> ScalarProductArg* scalar_product_arg(const Cons<T>& a, const Cons<T>& b)
{
  return new ScalarProductArgX(a.value, b.value, scalar_product_arg(a.tail,b.tail) );
}
template<> ScalarProductArg* scalar_product_arg<Nil>(const Cons<Nil>& a, const Cons<Nil>& b)
{
  return new ScalarProductArgX(a.value, b.value, new ScalarProductArg0() );
}

#include <iostream>

int main(int argc, char** argv)
{
  int n=0;
  std::cout << "enter n: ";
  std::cin  >> n;
  ScalarProductArg* xy = new ScalarProductArg0();
  for( int i=0; i<n; i++ )
    xy=xy->one_up(2*i+1, i*i);
  std::cout << xy->scalar_product() << "\n";

  /// а вот здесь твой пример немного расширен, и если это не нужно, то конс-ы вообще надо выбросить
  xy     = scalar_product_arg( cons(1,cons(2,Nil())), cons(3,cons(4,Nil())) );
  /// xy = scalar_product_arg( cons(1,cons(2,Nil())), cons(3,       Nil() ) ); // вот это не скомпилится
  std::cout << xy->scalar_product() << "\n";
  return 0;
}

кое-кто может его обозвать «стирание типов вручную», но я буду наверно придерживаться точки зрения, что определение scalar_product естественное, а дальше сделано два адаптера для Cons-ов

в то время, как должно быть 3

Да, туда попал кусок кода от тестирования предыдущей версии. После этого видна перекомпиляция.

я так и не придумал, как на с++ красиво сделать type erasure

Проблема не в type erasure, это деталь реализации. Проблема в том, что С++ не умеет делать тайпчекинг, если количество мономорфных типов не ограничено при компиляции.

C#, например, не делает type erasure, но туда пример из жабы переносится почти дословно.

для обеспечения равенства длин *твоим* способом твои конс-ы вообще не нужны:

i) ScalarProductArgX и ScalarProductArg0 - это такие по-другому названные Cons и Nil

ii) Я бы, всё-таки, хотел держать два списка более-менее раздельно. Ну, допустим, что второй список нужно перед вычислением произведения развернуть. Если они разделены, то это с гребенями, но сделается, причём код разворачивания можно будет изолировать (более-менее) от основного кода.

> Параметрический полиморфизм эмулируется в C++ шаблонами (и нарушается частичной специализацией шаблонов).

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

> Проблема в том, что С++ не умеет делать тайпчекинг, если количество мономорфных типов не ограничено при компиляции.

Ты уже N раз заявлял что С++ не умеет-что-то-там, но пока не привел конкретного кода, где бы эта разница была видна.

ScalarProductArgX и ScalarProductArg0 - это такие по-другому названные Cons и Nil

нет, это *пары*

ii) Я бы, всё-таки, хотел держать два списка более-менее раздельно. Ну, допустим, что второй список нужно перед вычислением произведения развернуть.

жду код на хаскеле

кое-кто может его обозвать «стирание типов вручную»

Да нет, это та же неинтересность.

В первом варианте - с циклом до n - два массива сцеплены жёсткой связкой. Опять-таки, допустим, один из них перед умножением переворачивается, или с ним ещё что-то делается, что длину точно не меняет. Соответственно, код, который это делает, должен учитывать это «спаривание».

xy = scalar_product_arg( cons(1,cons(2,Nil())), cons(3,cons(4,Nil())) );

А здесь - длина есть константа, известная на момент компиляции. Ещё менее интересно.

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

Да ради бога. С каким пунктом не согласны? С тем, что нарушается? Так это по определению параметрического полиморфизма (одна реализация для разных типов - соответственно, частичная специализация его нарушает). С тем, что эмулируется? Так если бы был настоящий параметрический полиморфизм, то жабский пример один в один переписался бы на плюсы.

> В первом варианте - с циклом до n - два массива сцеплены жёсткой связкой. Опять-таки, допустим, один из них перед умножением переворачивается, или с ним ещё что-то делается, что длину точно не меняет. Соответственно, код, который это делает, должен учитывать это «спаривание».

где код на хаскеле, демонстрирующий отсутствие «жесткой связки» на хаскеле?

ты вообще собираешься показать недостатки моего кода по сравнению с хаскелем, или продолжишь говорить страшные слова?

З.Ы. вовсе не обязательно сегодня — вялотекущая дискуссия меня устраивает

Ты уже N раз заявлял что С++ не умеет-что-то-там, но пока не привел конкретного кода, где бы эта разница была видна.

http://migmit.vox.com/library/post/поигрался-тут.html

Практически идентичный код, на жабе и на плюсах. У жабы настоящий ПП, всё работает. У плюсов - посредственная имитация, не работает.

нет, это *пары*

Я в курсе.

жду код на хаскеле

main' :: ScalarProduct a => Integer -> Integer -> a -> a -> Integer 
  main' 0 _ as bs = scalarProduct as bs

заменяем на

main' :: (DeepDown a, Reverse a, ScalarProduct a) => Integer -> Integer -> a -> a -> Integer 
  main' 0 _ as bs = scalarProduct as $ rev bs

class Reverse a where rev :: a -> a

instance Reverse Nil where rev Nil = Nil

class DeepDown a where deepDown :: a -> Integer -> Cons a
instance DeepDown Nil where deepDown Nil n = Cons n Nil
instance DeepDown a => DeepDown (Cons a) where deepDown (Cons n a) m = Cons n (deepDown a m)

instance (DeepDown a, Reverse a) => Reverse (Cons a) where rev (Cons n a) = deepDown (rev a) n

*Test> main 4
26

З.Ы. вовсе не обязательно сегодня — вялотекущая дискуссия меня устраивает

Может, не будешь тогда в трёх сообщениях подряд меня подгонять?

Практически идентичный код, на жабе и на плюсах. У жабы настоящий ПП

Сорри, забыл, что сам писал. Там, конечно, не жаба, а C#.

> *Test> main 4

26

желательно код целиком

вообще обычная практика в плюсах, когда встречается необходимость в type erasure, сделать опасную функцию с использованием void*, спрятать ее и выставить безопасную шаблонную версию, сделанную поверх нее

так что я достаточно низко оцениваю шансы с++ в сложном случае, но попробую

Да я, у прынцыпе, всё написал, но если надо:

module Test where 
data Nil = Nil deriving Show
data Cons a = Cons Integer a deriving Show 
class ScalarProduct a where scalarProduct :: a -> a -> Integer
instance ScalarProduct Nil where scalarProduct Nil Nil = 0
instance ScalarProduct a => ScalarProduct (Cons a) where scalarProduct (Cons n1 a1) (Cons n2 a2) = n1 * n2 + scalarProduct a1 a2
class DeepDown a where deepDown :: a -> Integer -> Cons a
instance DeepDown Nil where deepDown Nil n = Cons n Nil
instance DeepDown a => DeepDown (Cons a) where deepDown (Cons n a) m = Cons n (deepDown a m)
class Reverse a where rev :: a -> a
instance Reverse Nil where rev Nil = Nil
instance (DeepDown a, Reverse a) => Reverse (Cons a) where rev (Cons n a) = deepDown (rev a) n
main :: Integer -> Integer 
main n = main' n 0 Nil Nil where 
  main' :: (DeepDown a, Reverse a, ScalarProduct a) => Integer -> Integer -> a -> a -> Integer 
  main' 0 _ as bs = scalarProduct as $ rev bs 
  main' n i as bs = main' (n-1) (i+1) (Cons (2*i+1) as) (Cons (i^2) bs) 

Да, два раза deriving Show - это не обязательно (хотя и неплохо).

Вариант на шарпе:

using System;
interface ScalarProduct<A> where A : ScalarProduct<A>{
  int scalarProduct(A second);
  Cons<A> deepDown(int n);
  A revert();
}
class Nil : ScalarProduct<Nil> {
  public Nil(){}
  public int scalarProduct(Nil second) {
    return 0;
  }
  public Cons<Nil> deepDown(int n) {
    return new Cons<Nil>(n, new Nil());
  }
  public Nil revert(){
    return new Nil();
  }
}
class Cons<A> : ScalarProduct<Cons<A>> where A : ScalarProduct<A> {
  public int value;
  public A tail;
  public Cons(int _value, A _tail) {
    value = _value;
    tail = _tail;
  }
  public int scalarProduct(Cons<A> second){
    return value * second.value + tail.scalarProduct(second.tail);
  }
  public Cons<Cons<A>> deepDown(int n) {
    return new Cons<Cons<A>>(value, tail.deepDown(n));
  }
  public Cons<A> revert() {
    return tail.revert().deepDown(value);
  }
}
class _Test{
  public static int main(int n){
    return _main(n, 0, new Nil(), new Nil());
  }
  public static int _main<A>(int n, int i, A first, A second) where A : ScalarProduct<A> {
    if (n == 0) {
      return first.scalarProduct(second.revert());
    } else {
      return _main(n-1, i+1, new Cons<A>(2*i+1,first), new Cons<A>(i*i, second)); // Works
      //return _main(n-1, i+1, first, new Cons<A>(i*i, second)); // Doesn't work
    }
  }
}
public class Test{
  public static void Main(){
    Console.Write("Enter a number: ");
    int val = Convert.ToInt32(Console.ReadLine());
    Console.WriteLine(_Test.main(val));
  }
}

MigMit:~ MigMit$ gmcs -o:Test.exe Test.csharp
MigMit:~ MigMit$ mono Test.exe
Enter a number: 17
12376

Может я опять какую чушь скажу. Какие ключевые технологии позволяют это сделать? Первое как я понимаю это параметрический полиморфизм и второе - дженерики. Может что-то ещё, плохо разбираюсь в этих языках. Но что-то мне подсказывает, что всё это возможности языков более высокого уровня, чем С++. И в Java и в С# работа с указателями скрыта. В С# объекты классов всегда передаются по ссылкам. И мне кажется, что по-этому эти концепции и поддержаны компилятором. На С++ можно работать как угодно и с чем угодно, отсюда и нет поддержки этого. Эти возможности будут выглядеть просто глупо, если они вообще возможны в таком низкоуровневом языке. В этих языках издержки рантайма выше чем в С++, что даёт им в чем-то преимущество. Про Хаскель ничего сказать не могу, никогда с ним дела не имел.

На С++ можно работать как угодно и с чем угодно, отсюда и нет поддержки этого

я один вижу здесь взаимоисключающие параграфы?

В этих языках издержки рантайма выше чем в С++, что даёт им в чем-то преимущество

рантайм в данном контексте не при чём

Вы наверно не совсем поняли, что я имел ввиду или я плохо донёс.

я один вижу здесь взаимоисключающие параграфы?

Я имею ввиду, что С++ более низкоуровневый язык и в нём больший доступ программиста к низкоуровневым сущностям, соответсвенно компилятор имеет меньший контроль над кодом и соответсвенно компилятор в чём-то более ограничен, чем Java или C#.

В этих языках издержки рантайма выше чем в С++, что даёт им в чем-то преимущество

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

Под «как угодно и с чем угодно» имелось ввиду, с точки зрения контроля программистом. Конечно комплятор вC++ много чего не умеет, по ставнению с другими.

> предлагаю вот такой код:

Функция one_up - это нечестный прием :)

Функция one_up - это нечестный прием

Почему же? Сам по себе приём «сделать функцию, возвращающую контейнер, содержащий данный объект» вполне разумен.

Сейчас векторы создаются внутри main. А если они пришли из разных источников? Тогда у нас не будет общего n. Придется вставлять run-time проверку, чего и хотелось бы избежать. В хаскельном же варианте будет compile-time проверка типов при непосредственном вызове scalarProduct.

Другое дело, что общий список Num a => [a] не преобразуешь к ScalarProduct, а это сужает применимость хаскельного метода.

> Параметрический полиморфизм - одна и та же функция работает с разными типами, и код этой функции всё время один и тот же.

В Хаскеле один и тот же машкод работает с разными типами данных? O_o Я думал, такое не практикуется со времен реализации Клу для Эльбруса :)

Нет, сделать список экземпляром ScalarProduct безусловно можно. Но там снова будет run-time проверка. Без списков неинтересно.

> В Хаскеле один и тот же машкод работает с разными типами данных? O_o Я думал, такое не практикуется со времен реализации Клу для Эльбруса

насколько я понимаю, в cyclone тоже полиморфизм с type erasure (один и тот же машкод работает с разными типами данных).

Функция one_up - это нечестный прием

это ровно тот же прием, что применен в хаскеле в main'

но как правильно указал мигель, ScalarProductArg слишком жестко сцеплен с Cons-ами (и даже фактически их подменяет)

правильным было бы что-то типа

struct ScalarProductArg
{
  const AbstractCons& a;
  const AbstractCons& b;
  ...
};

и статически обеспечить конс-ы равной длины; х.з. хватит ли у плюсов на это компилятора

моя идея сейчас состоит в том, чтобы перегрузить оператор -> и все операции над конс-ами внутри экземпляра ScalarProductArg делать параллельно; однако у AbstractCons может быть нехороший метод bad(int), который допустим увеличивает на 1 длину в случае нечетного аргумента, и не меняет в случае четного — от этого как-то надо защититься

еще интереснее написать шаблон AnyTypeEraser (или хотя бы IntTypeEraser)

на все это нужно дофига времени, а еще надо ответить мигелю в теме зависимых типов :-)

Сейчас векторы создаются внутри main. А если они пришли из разных источников? Тогда у нас не будет общего n.

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

Другое дело, что общий список Num a => [a] не преобразуешь к ScalarProduct, а это сужает применимость хаскельного метода.

Вообще ничего не понял.

В Хаскеле один и тот же машкод работает с разными типами данных? O_o Я думал, такое не практикуется со времен реализации Клу для Эльбруса :)

Напрасно. Скажем, если мы считаем длину списка, то что в этом списке - нам пофигу; так зачем тратить место на повторение кода.

Другое дело, что общий список Num a => [a] не преобразуешь к ScalarProduct, а это сужает применимость хаскельного метода.

Вообще ничего не понял.

А, хотя стоп. Понятно. Ну дык тут по условию задача такая, чтобы подобные «общие» преобразования не проходили.

> В Хаскеле один и тот же машкод работает с разными типами данных? O_o Я думал, такое не практикуется со времен реализации Клу для Эльбруса :)

Напрасно. Скажем, если мы считаем длину списка, то что в этом списке - нам пофигу; так зачем тратить место на повторение кода.

Как понимаю не всегда это катит. Как в C# да, гомоморфными типами предаваемыми по ссылке/указателю. Иначе без кодогенерации получим в лучшем случаи ещё одну издержку рантайма, в худщем не будет работать. И вообще странный какой-то этот параметрический полиморфизм, так можно просто передавать void*.

> И вообще странный какой-то этот параметрический полиморфизм, так можно просто передавать void*.

... до тех пор, пока нам не потребуется, чтобы оба void* были одинаковыми типами, как в этой задаче.

>> В Хаскеле один и тот же машкод работает с разными типами данных? O_o Я думал, такое не практикуется со времен реализации Клу для Эльбруса :)

Напрасно.

Может быть. Но я всё же думаю, что ты ошибаешься как минимум отчасти. Есть ссылка на описание кодогенерации в Хаскеле?

Скажем, если мы считаем длину списка, то что в этом списке - нам пофигу; так зачем тратить место на повторение кода.

А если мы суммируем элементы списка, нам уже не пофигу.

Есть ссылка на описание кодогенерации в Хаскеле?

В Хаскеле - нет, потому что это язык.

В GHC - наверняка, поищи.

А если мы суммируем элементы списка, нам уже не пофигу.

Естественно. Поэтому сложение в значительно меньшей степени полиморфно, чем вычисление длины списка.

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

> сложение в значительно меньшей степени полиморфно, чем вычисление длины списка.

/me записал новый термин: «степень полиморфизма».

Какие из приведенных примеров будут компилироваться, какие — нет, и как компилятор это определяет?

http://linux.org.ru/wiki/en/User:eugine_kosenko:VectorLength

То есть, я правильно понял, что речь идет о том, как все плохо в C++, а не о том, как все хорошо в Хаскеле?