Haskell类型类和C++模板类

Question

是否可以使用C++(或C#)模板模拟Haskell的类型类功能？

这样做有意义还是有任何回报？

我试图用C++编写一个Functor类,但我无法做到.我试过这样的事情:

#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

是否可以使用C++(或C#)模板模拟Haskell的类型类功能？

我不太熟悉C++模板来回答这个问题.我可以稍微谈谈C#泛型类型.

最简洁的答案是不."更高"类型的Haskell系统比C#中的泛型类型系统更强大.

对于那些仍在阅读这些不熟悉Haskell的读者而言,对"更高类型"的含义进行简要讨论可能对此有用.在C#中你可以这样做:

interface IEnumerable<T> { ... }

"通用"类型"一个类型参数的IEnumerable"本身并不是一个"类型",它是一种模式,您可以通过将类型参数("int")替换为类型参数来构造无限多个新类型(" T").从这个意义上讲,它比普通类型"更高".

您可以对泛型类型的类型参数设置约束:

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

通用类型C可以使用任何类型参数构造,只要类型参数是通过引用或装箱转换可隐式转换的类型IEnumerable<int>.

但是Haskell类型系统比这更进了一步.它支持"类型类",其中你可以对T赋予的约束是"T在其上定义了相等运算符"之类的东西.在C#中,运算符被定义为静态方法,并且静态方法的接口没有模拟.我们无法在基于任意静态方法的多种类型的C#中进行泛化.

通常为Haskell提供的一个例子是"monad"模式.在C#表示法中,假设我们有一个类型:

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

monad只是一种模式; monadic类型是任何泛型类型,因此它具有静态泛型方法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>>);
}

但那是不对的.这就是说monad是一个monad和一个返回monad的函数,并返回一个monad.这意味着,你可以有两种实现方式IMonad<T>,说Maybe<T>和Sequence<T>,然后有一种粘合剂,需要一个序列,并返回一个可能!这没有任何意义; 我们想要捕捉的模式是

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#中的序列运算符库中;它可以通过IEnumerable<T>用"ToList" 组合"选择"来构建.

随你.无所谓.关键是在Haskell的代码中:

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

你可以说,"这暴露了符合上述模式的映射操作的任何泛型类型被认为是一个'函子’",然后你就可以说采取函子方法.我们没有任何方法可以在C#中在用户级别概括"提供映射操作的所有类型" .

为了解决类型系统的这种限制,我们所做的就是选择一些最强大的更高类型,并将它们直接构建到语言中.语言本身识别更高类型,如序列模式(在foreach循环处理中),广义monad模式(在查询理解中;"SelectMany"在任意monad上是"Bind"),延续模式(在"await"中进入C#5),"Maybe"monad(可以为可空的值类型)等等.

因此,为了解决您的具体问题,是的,没有问题,在类型系统中没有捕获进行投影的概念,但是它使用LINQ查询理解的语言捕获.如果你说

from x in y select z

然后任何类型的表达式y都有一个带有y的Select方法和从x到z的映射.该模式已构建到C#语言中.但如果你想描述一些其他 "更高"的模式,那你就不走运了.

在类型系统中有一个工具来描述更高类型会很好,但更有可能的是我们将按原样保持类型系统,并根据需要将更多模式烘焙到语言中.

在这个问题中描述了我经常看到尝试在C#中模拟高阶类型的地方:

为什么这个泛型约束在它似乎有一个循环引用时编译

这里的想法是开发人员希望开发一种类型"动物",这样:

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

虚构的"T:THISTYPE"试图了解猫只能与另一只猫交朋友,狗只能和另一只狗交朋友,等等.(暂时忽略这样一个事实,即这意味着MakeFriends在形式参数类型上具有虚拟协方差,这种模式不会是类型安全的,因此可能会违反Liskov替换原则.)这个概念可以在更高的类型中表达,但不是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){ ... }
}

现在,狗可以成为猫的朋友,违反了动物作者的意图.C#类型系统的功能不足以代表您可能需要的所有类型的约束.您必须使用更高的类型才能使其正常工作.

Answer 2

C++ 0x将引入与Haskell类型类非常相似的概念,但该功能已被否决.再耐心等待十年,他们终于可以进入语言.

Answer 3

来自这篇关于Haskell和C++的博客文章的作者:

发现了在C++中进行编译时计算的能力,而不是内置于该语言中.

虽然可以在C++模板中模拟许多Haskell功能,但翻译的语法确实很难看.这主要是因为C++中的元编程是一个意外而不是最初设想的特征.