Классы типов Haskell и классы шаблонов C ++

Question

Можно ли эмулировать функциональность класса типов в Haskell с помощью шаблонов C ++ (или C #)?

Имеет ли смысл или есть какая-то отдача от этого?

Я пытался создать класс Functor на C ++, но не смог. Я пробовал что-то вроде этого:

#include <iostream>
using namespace std;

//A function class to make types more readable
template <class input, class output> class Function {
private:
  output (*ptrfunc )(input);
public:
  Function(output (* ptr)(input)) {
    ptrfunc = ptr;
  }
  output call(input x) {return  (*ptrfunc)(x);}
  output operator() (input x) { return call(x);}
};


//the functor "typeclass"
template <class a> class Functor{
public:
  template <class b> Functor<b> fmap(Function<a,b> func);
};

// an container type to be declared "instance" of functor:
template <class a> class List : public Functor<a> { 
private:
  a * ptrList;
  int size;
public:
  List(int n) {  //constructor;
    ptrList = new a[n]; 
    size = n;
  }
  List(List<a> const& other) { //copy constructor
    size = other.size;
    ptrList = new a[size];
    for(int i = 0; i<size; i++)
      (*this)[i] = other[i];
  }
  ~List() { delete ptrList;} //destructor
  a& operator[](int i) { return ptrList[i];} // subscript operator just for easy notation
  const a& operator[](int i) const { return ptrList[i];}// subscript operator just for easy notation

  template <class b> List<b> fmap(Function<a,b> func) { //"instance" version of fmap
    List<b> temp(size);
    for(int i = 0; i < size; i++)
      temp[i] = func((*this)[i]);
    return temp;
  }
};


int test(int k) { return 2 * k;}

int main(void) {
  Function<int, int> func(&test);
  List<int> lista(10);
  for(int i = 0; i < 10; i++)
    lista[i] = i;
  List<int> lista2(lista.fmap(func));
  for(int i = 0; i < 10; i++)
    cout << lista2[i] << " ";
  cout << endl;
  return 0;
}

Он делает то, что должен, но имеет ли смысл использовать этот шаблон в C ++? Это действительно тот же шаблон, что и в haskell:

data List a = -- some stuff 

class  Functor f  where
fmap :: (a -> b) -> f a -> f b

instance (Functor List) where
-- some stuff    

Мне кажется, что это не одно и то же, потому что в Functor f, f является добрым конструктором типа * -> *, а в моем определении выше в Functor<a>, a не является шаблон a<something>, но сам «содержащийся» тип данных.

Есть ли выход к этому? И что еще более важно: имеет смысл пытаться скопировать этот тип шаблонов в C ++? Мне кажется, что C # больше похож на функциональный стиль программирования, чем C ++. Есть ли способ сделать это в C #?

Answer 1

Можно ли эмулировать функциональность класса типов в Haskell с помощью шаблонов C ++ (или C #)?

Я недостаточно разбираюсь в шаблонах C ++, чтобы ответить на вопрос. Хотя я могу немного рассказать о родовых типах C #.

Краткий ответ: нет. Система Haskell «более высоких» классов типов более мощная, чем система универсальных типов в C #.

Краткое обсуждение того, что мы подразумеваем под «высшими типами», может быть полезным на этом этапе для любых читателей, которые все еще читают это, которые не знакомы с Haskell. В C # вы можете сделать это:

interface IEnumerable<T> { ... }

«Универсальный» тип «IEnumerable одного параметра типа» на самом деле не является «типом» как таковым, это шаблон, из которого вы можете создавать бесконечно много новых типов, подставляя аргументы типа («int») для типа параметры («Т»). В этом смысле он «выше» обычного типа.

Вы можете наложить ограничения на параметры типа универсальных типов:

class C<T> where T : IEnumerable<int>

Универсальный тип C может быть создан с любым аргументом типа, при условии, что аргумент типа является типом, который неявно преобразуется посредством преобразования ссылки или бокса в IEnumerable<int>.

Но система типов Хаскелла делает еще один шаг вперед. Он поддерживает «классы типов», где ограничения, которые вы можете наложить на T, - это такие вещи, как «T имеет определенный оператор равенства». В C # операторы определены как статические методы, и не существует аналога интерфейса для статических методов. В C # мы не можем обобщать многие типы на основе произвольных статических методов.

Примером, обычно приводимым для Хаскелла, является образец "монады". Предположим, что в C # мы имеем тип:

class MyMonad<T>
{
    public static MyMonad<TOut> Bind<TIn, TOut>(MyMonad<TIn>, Func<TIn, MyMonad<TOut>>) { ... }
    public MyMonad(T t) { ... }
}

Монада - это просто образец; Монадический тип - это любой универсальный тип, такой, что у него есть статический универсальный метод Bind и конструктор, который соответствует шаблону выше. В Haskell вы можете использовать более высокие типы для описания этого паттерна; в C # у нас нет средств в системе типов для обобщения таких вещей, как статические методы и конструкторы.

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

class MyMonad<T>
{
    public MyMonad<TOut> Bind<TOut>(MyMonad<T>, Func<T, MyMonad<TOut>>) { ... }
    public MyMonad(T t) { ... }
}

Это помогает? Нет. Даже оставляя проблему с конструктором в стороне, мы не можем придумать интерфейс, который фиксирует этот шаблон. Мы можем попробовать:

interface IMonad<T>
{
    public IMonad<TOut> Bind<TOut>(IMonad<T>, Func<T, IMonad<TOut>>);
}

Но это не правильно . Это говорит о том, что монада - это то, что принимает монаду и функцию, которая возвращает монаду и возвращает монаду. Это означает, что вы можете иметь две реализации IMonad<T>, скажем, Maybe<T> и Sequence<T>, а затем иметь связыватель, который принимает последовательность и возвращает значение Maybe! Это не имеет никакого смысла; шаблон, который мы хотим запечатлеть,

highertype Monad makes a pattern with TheImplementingType<T> like
{
    public TheImplementingType<TOut> Bind<TOut>(TheImplementingType<T>, Func<T, TheImplementingType<TOut>>);
}

но у нас нет возможности выразить это в C #.

Давайте рассмотрим ваш пример с Functor. В C # у нас может быть тип

class List<T> 
{
    public static List<TOut> Map<TIn, TOut>(Func<TIn, TOut> mapper, List<TIn> list) 
    { ... }

Или, возможно, более идиотски, метод экземпляра:

class List<T> 
{
    public List<TOut> Map<TOut>(Func<T, TOut> mapper) 
    { ... }

Или, опять же, более идиотски, у нас может быть статический метод в качестве метода расширения. (На самом деле, этот метод существует в библиотеке операторов последовательности в C #; его можно построить, составив «Select» в IEnumerable<T> с «ToList»).

Whatever. Не имеет значения Дело в том, что в вашем коде на Haskell:

class  Functor f  where 
fmap :: (a -> b) -> f a -> f b 

Вы можете сказать, что «любой универсальный тип, который предоставляет операцию отображения, соответствующую описанному выше шаблону, называется« функтором »», а затем вы можете создавать методы, которые принимают функторы. У нас нет никакого способа обобщить «все типы, которые обеспечивают операции отображения» на уровне пользователя в C #.

Чтобы обойти это ограничение системы типов, мы выбрали несколько наиболее мощных типов высшего уровня и встроили их непосредственно в язык.Сам язык распознает более высокие типы, такие как шаблон последовательности (в обработке цикла foreach), обобщенный шаблон монады (в пониманиях запросов; «SelectMany» - это «Bind» для произвольной монады), шаблон продолжения (в «await», приходящий вC # 5), монада «Maybe» (в типах значений, допускающих значение NULL) и т. Д.

Итак, для решения вашей конкретной проблемы, да, нет проблем, идея создания проекциине фиксируется в системе типов , но фиксируется на языке с пониманием запросов LINQ.Если вы скажете

from x in y select z

, тогда любое выражение y типа, у которого есть метод Select, который принимает y, и отображение от x до z будет работать.Этот шаблон был встроен в язык C #.Но если вы хотите описать какой-то другой «более высокий» шаблон, вам не повезло.

Было бы неплохо, чтобы в системе типов была возможность описывать более высокие типы, но более вероятно, что мы сохраним систему типов как есть и добавим больше шаблонов в язык по мере необходимости..

Место, где я обычно вижу попытку эмулировать типы высшего порядка в C #, описано в этом вопросе:

Почему это общее ограничение компилируется, когда кажется, что оно имеетциклическая ссылка

Идея заключается в том, что разработчик желает разработать тип «Животное», такой что:

abstract class Animal
{
    public abstract void MakeFriends<T>(T newFriend)
    where T : THISTYPE;
}

Вымышленное «где T: THISTYPE» пытается получитьчерез идею о том, что кошка может дружить только с другой кошкой, собака может дружить только с другой собакой и так далее.(На данный момент игнорируем тот факт, что такой шаблон, который подразумевает, что MakeFriends имеет виртуальную ковариацию по формальным типам параметров, не будет безопасным для типов и, вероятно, тем самым нарушит принцип подстановки Лискова.) Эта концепция выразима в более высоких типах, но не всистема типов C #.Иногда люди используют такой шаблон, как:

abstract class Animal<T> where T : Animal<T>
{
    public abstract void MakeFriends(T newFriend);
}
class Cat : Animal<Cat>
{
    public override void MakeFriends(Cat newFriend){ ... }
}

Однако, это не может фактически обеспечить желаемое ограничение, потому что, конечно, ничто не мешает вам сказать:

class Dog : Animal<Cat>
{
    public override void MakeFriends(Cat newFriend){ ... }
}

А теперьСобака может дружить с кошкой, нарушая замысел автора Animal.Система типов C # просто недостаточно мощна, чтобы представлять все виды ограничений, которые вы можете захотеть.Вы должны использовать более высокие типы, чтобы сделать это правильно.

Answer 2

C ++ 0x собирался представить концепции , которые очень похожи на классы типов Haskell, но эта функция была исключена.Будьте терпеливы еще десять лет, и они, наконец, смогут проникнуть в язык.

Answer 3

От автора этого сообщения в блоге на Haskell и C ++:

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

Хотя многие возможности Haskell можно эмулировать в шаблонах C ++, переведенный синтаксис действительно ужасен.Это в основном потому, что метапрограммирование в C ++ было скорее случайностью, чем изначально задуманной функцией.

Answer 4

Несмотря на то, что C # и C ++ были выделены в посте, может быть интересно сравнить с Scala (2.8, цель - JVM). Scala очень похож на C #, поскольку является сильным / статическим языком "OO" с одной диспетчеризацией, но имеет более мощную систему типов, чем C # 3/4 (однако функции не полностью перекрываются).

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

С другой стороны, F #, «функциональный язык», имеет слабую (или не существующую? Еще раз, не мою область), но я считаю, что невозможно создать тип Monad в F #) для поддержки конструкций классов типов. Это определенно оправдывает сильные стороны языка.

Удачного кодирования.

Answer 5

Может быть, мне не хватает некоторого метауровня Haskell, но ваш реальный пример без объявлений будет выглядеть так с использованием STL:

struct Test : public std::unary_function<Foo,SomeResult> {
    SomeResult operator()( const Foo& foo ) const;
};

std::vector<Foo> foos;
...

std::vector<SomeResult> results;
std::transform( foos.begin(), foos.end(), results.begin(), Test() );
....