Haskell类型类和C ++模板类

Is it possible to emulate the type class functionality of Haskell with C++ (or C#) templates?

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

Does it make sense or is there any payoff in doing that?

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

I was trying to make a Functor class in C++ and I wasn't able. I tried something like this:

我试图用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;
}

It does what it's supposed to do, but does it make any sense to use this pattern in C++? Is it really the same pattern as in haskell:

它做了它应该做的事情,但在C ++中使用这个模式是否有意义?它与haskell的模式是否真的相同:

data List a = -- some stuff 

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

instance (Functor List) where
-- some stuff    

It doesn't seem to be the same thing to me, cause in Functor f, f is a kind * -> * type constructor, and in my definition above in Functor<a>, a is not a template a<something>, but the "contained" data type itself.

它对我来说似乎不是一回事,因为在Functor f中,f是一种* - > *类型的构造函数,在我上面的Functor 中定义,a不是模板 ,但“包含”数据类型本身。

Is there a way out to this? And more importantly: it makes sense to try to copy this kinds of patterns to C++? It seems to me that C# is more akin to functional programming style than C++. Is there a way to do this in C#?

有没有办法解决这个问题?更重要的是:尝试将这种模式复制到C ++是有意义的吗?在我看来,C#比C ++更类似于函数式编程风格。有没有办法在C#中做到这一点?

5 个解决方案

#1

Is it possible to emulate the type class functionality of Haskell with C++ (or C#) templates?

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

I am not sufficiently versed in C++ templates to answer the question. I can talk about C# generic types a bit though.

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

The short answer is, no. The Haskell system of "higher" type classes is more powerful than the generic type system in C#.

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

A brief discussion of what we mean by "higher types" might be useful at this point for any readers that are still reading this who are not familiar with Haskell. In C# you can do this:

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

interface IEnumerable<T> { ... }

The "generic" type "IEnumerable of one type parameter" is not really a "type" per se, it is a pattern from which you can construct infinitely many new types, by substituting type arguments ("int") for type parameters ("T"). In that sense it is "higher" than a normal type.

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

You can put constraints on type parameters of generic types:

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

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

Generic type C can be constructed with any type argument, so long as the type argument is a type that is implicitly convertible via reference or boxing conversion to IEnumerable<int>.

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

But the Haskell type system goes one step further than that. It supports "type classes" where the constraints you can put on the T are things like "T has an equality operator defined on it". In C#, operators are defined as static methods, and there is no analogue of an interface for static methods. We have no way in C# of generalizing across many types based on arbitrary static methods.

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

An example usually given for Haskell is the "monad" pattern. In C# notation, suppose we have a type:

通常给出Haskell的一个例子是“monad”模式。在C#表示法中,假设我们有一个类型:

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

A monad is just a pattern; a monadic type is any generic type such that it has a static generic method Bind and a constructor that matches the pattern above. In Haskell you can use higher types to describe that pattern; in C#, we have no facility in the type system for generalizing on things like static methods and constructors.

monad只是一种模式; monadic类型是任何泛型类型,因此它具有静态泛型方法Bind和与上述模式匹配的构造函数。在Haskell中,您可以使用更高的类型来描述该模式;在C#中,我们在类型系统中没有用于泛化静态方法和构造函数的工具。

Or, you might say that it would be more idiomatic to use an instance binder:

或者,您可能会说使用实例绑定器会更加惯用:

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

Does that help? No. Even leaving the problem with the constructor aside, we cannot come up with an interface that captures this pattern. We can try:

这有帮助吗?没有。即使抛开构造函数的问题,我们也无法想出一个捕获这种模式的接口。我们可以尝试:

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

But that is not right. That says that a monad is something that takes a monad and a function that returns a monad in, and returns a monad. That means that you could have two implementations of IMonad<T>, say Maybe<T> and Sequence<T> and then have a binder that takes a sequence and returns a maybe! That doesn't make any sense; the pattern we want to capture is

但那是不对的。这就是说monad是一个monad和一个返回monad的函数,并返回一个monad。这意味着你可以有两个IMonad 的实现,比如说Maybe 和Sequence ,然后有一个绑定器接受一个序列并返回一个可能!这没有任何意义;我们想要捕捉的模式是

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

but we have no way of expressing that in C#.

但我们无法在C#中表达这一点。

Let's consider your Functor example. In C# we might have a type

让我们考虑你的Functor示例。在C#中我们可能有一个类型

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

Or, perhaps more idiomatically, an instance method:

或者,或许更惯用,实例方法:

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

Or, again more idiomatically, we might have the static method as an extension method. (In fact, this method does exist in the sequence operator library in C#; it can be built by composing "Select" on IEnumerable<T> with "ToList").

或者,再次更惯用,我们可能将静态方法作为扩展方法。 (实际上,这个方法确实存在于C#中的序列运算符库中;它可以通过在IEnumerable 上用“ToList”组合“Select”来构建。

Whatever. Doesn't matter. The point is that in your code in Haskell:

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

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

You can say that "any generic type which exposes a mapping operation that meets the pattern above is said to be a 'Functor'", and then you can make methods that take Functors. We don't have any way of generalizing "all the types that provide mapping operations" at the user level in C#.

您可以说“任何公开符合上述模式的映射操作的泛型类型都被称为'Functor'”,然后您可以制作采用Functors的方法。我们没有任何方法可以在C#中在用户级别概括“提供映射操作的所有类型”。

To get around this limitation of the type system, what we've done is chosen a few of the most powerful higher types and built them directly into the language. The language itself recognizes higher types like the sequence pattern (in the foreach loop processing), the generalized monad pattern (in query comprehensions; "SelectMany" is "Bind" on an arbitrary monad), the continuation pattern (in "await" coming in C# 5), the "Maybe" monad (in nullable value types) and so on.

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

So to solve your specific problem, yes, no problem, the notion of making a projection is not captured in the type system but it is captured in the language with LINQ query comprehensions. If you say

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

from x in y select z

then any expression y of a type that has a Select method that takes y and a mapping from x to z will work. That pattern has been built into the C# language. But if you want to describe some other "higher" pattern, you're out of luck.

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

It would be nice to have a facility in the type system to describe higher types, but what is more likely is that we will keep the type system as-is, and bake more patterns into the language as-needed.

在类型系统中有一个工具来描述更高类型会很好,但更有可能的是我们将按原样保留类型系统,并根据需要在模式中加入更多模式。

A place where I commonly see an attempt to emulate higher-order types in C# is described in this question:

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

Why does this generic constraint compile when it seems to have a circular reference

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

The idea here is that the developer wishes to develop a type "Animal" such that:

这里的想法是开发人员希望开发一种类型“动物”,以便:

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

The fictional "where T : THISTYPE" is attempting to get across the idea that a Cat can only make friends with another Cat, a Dog can only make friends with another Dog, and so on. (Ignore for the moment the fact that such a pattern, which implies that MakeFriends has virtual covariance on formal parameter types, would not be typesafe and would probably thereby violate the Liskov Substitution Principle.) That concept is expressible in higher types, but not in the C# type system. People sometimes use a pattern like:

虚构的“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){ ... }
}

However, this fails to actually enforce the desired constraint, because of course there is nothing whatsoever stopping you from saying:

但是,这实际上无法强制执行所需的约束,因为当然没有什么可以阻止你说:

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

And now a Dog can be friends with a Cat, violating the intention of the author of Animal. The C# type system is simply not powerful enough to represent all the sorts of constraints that you might want. You'd have to use higher types to make this work properly.

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

#2

C++0x was going to introduce concepts which are quite similar to Haskell's type classes, but the feature got voted out. Be patient for another ten years, and they may finally make their way into the language.

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

#3

From the author of this blog post on Haskell and C++:

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

The ability to do compile-time calculations in C++ was discovered rather than built into the language.

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

While it's possible to emulate many Haskell features in C++ templates, the translated syntax is indeed ugly. That's mostly because metaprogramming in C++ was an accident rather than an originally conceived feature.

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

#4

Even though C# and C++ were singled out in the post, it may be interesting to compare with Scala (2.8, target is JVM) instead. Scala is quite similar to C# as it is a strong/static single-dispatch "OO" language -- but it has a more powerful type-system than C#3/4 (the features aren't a full overlap, however).

尽管在帖子中挑出了C#和C ++,但与Scala(2.8,目标是JVM)进行比较可能会很有趣。 Scala与C#非常相似,因为它是一种强大/静态的单一调度“OO”语言 - 但它具有比C#3/4更强大的类型系统(但是这些功能并不完全重叠)。

I am not familiar with Haskell, but I have read various articles and heard a number of arguments over the years, and I believe that the typeclass functionality you are looking for can be derived with implicits (an example), even if not nearly as idiomatic as in Haskell.

我对Haskell并不熟悉,但是我已经阅读过各种文章并且多年来听过很多论点,我相信你正在寻找的类型类功能可以用implicits(一个例子)推导出来,即使它几乎不是惯用的就像在Haskell中一样。

On the other hand, F#, a "functional language", has poor (or non-existent? once again, not my area, but I believe it's not possible to create a Monad type in F#) support for typeclasses constructs. It definitely pays to play off the strengths of the language.

另一方面,F#是一种“函数式语言”,它对于类型类构造的支持很差(或者不存在?再次,不是我的区域,但我认为不可能在F#中创建Monad类型)。发挥语言的优势绝对是值得的。

Happy coding.

#5

Maybe I'm missing some Haskell meta level here, but your actual example, without the declarations would look like this using the STL:

也许我在这里缺少一些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() );
....