如何把 Haskell 代码翻译到 C++ 呢？记一次不成功的瞎搞经历。

多态函数

这个是比较好办的，用 C++ 的模板可以实现同样的操作，而 typeclass 可以直接忽略掉。

ADT

这个是重头戏了。考虑 Maybe

data Maybe a = Nothing | Just a

该怎么把它翻译成 C++ 呢？一种比较显然的思路是这样的：

enum MaybeType {
  Nothing, Just
};
template <typename A>
struct Maybe {
  MaybeType type;
  A value;
};

看起来很不错，对吧！这样我们可以实现模式匹配：

template <typename A>
void foo (Maybe<A> v) {
  if (v.type == Nothing)
    return;
  else
    // do something
}

当然，也可以把 struct 换成 union，这样会省一点内存（Maybe 这个例子是不省的）。

然而，这样做会有一个很大的问题，考虑如下 Haskell 代码：

data Node a = Node2 a a | Node3 a a a
data FingerTree a
  | Empty
  | Single a
  | Deep (Digit a) (FingerTree (Node a)) (Digit a)


type Digit a = Digit [a]

infixr 5 <|

(<|) ::a -> FingerTree a -> FingerTree a
a <| Empty = Single a
a <| Single b = Deep (Digit [a]) Empty (Digit [b])
a <| Deep (Digit [b, c, d, e]) m r = Deep (Digit [a, b]) (Node3 c d e <| m) r
a <| Deep (Digit xs) m r = Deep (Digit (a:xs)) m r

来自 FingerTree

注意到 FingerTree a 中 Deep 里的子树的类型竟然是 FingerTree (Node a)，如此下去，嵌套层数会越来越多，变成 FingerTree (Node (Node a)) 之类的。这样，如果像刚才那样，在一个函数中判断 type 会导致编译器在实例化该模板时停不下来，直到达到限制。

那么应该怎么办呢？只需要使得不同 type 的 FingerTree 实例在不同的函数中被实例化就可以了。

我们可以写一个基类 FingerTree ，然后由它派生出 Empty，Single，Deep，这样以来，就可以利用函数重载，把它们分开了：

template<typename A>
Single<A> *pushFront(Empty<A> *t, A val) {
  return new Single<A>(val);
}

template<typename A>
Deep<A> *pushFront(Single<A> *t, A val) {
  return new Deep<A>(deque<A> {val}, new Empty<Node<A>>(), deque<A> {t->val});
}

template<typename A>
Deep<A> *pushFront(Deep<A> *t, A val) {
  if (t->digit1.size() < 4) {
    auto tmpdq = t->digit1;
    tmpdq.push_front(val);
    return new Deep<A>(tmpdq, t->subtree, t->digit2);
  } else {
    A b = t->digit1[0], c = t->digit1[1], d = t->digit1[2], e = t->digit1[3];
    return new Deep<A>(deque<A> {val, b}, pushFront<Node<A>>(t->subtree, Node3<A>(c, d, e)), t->digit2);
  }
}

FingerTree 的定义会在文章最末处给出。然而这样操作也会带来很多问题（这也是我弃坑的原因），考虑 Haskell 的表述：FingerTree 是类型名，而 Empty，Single，Deep 是值构造器（其实是函数）的名字。而这样操作，使得它们都是变成了类型，势必会带来一大堆锅。

enum NodeType {
  node2, node3
};
template<typename A>
struct Node {
  NodeType type;
};

template<typename A>
struct Node2 : public Node<A> {
  A v1, v2;
  Node2(const A &v1, const A &v2) : v1(v1), v2(v2) { this->type = node2; }
};

template<typename A>
struct Node3 : public Node<A> {
  A v1, v2, v3;
  Node3(const A &v1, const A &v2, const A &v3) : v1(v1), v2(v2), v3(v3) { this->type = node3; }
};

enum FingerTreeType {
  Fempty, Fsingle, Fdeep
};

template<typename A>
struct FingerTree {
  FingerTreeType type;
};

template<typename A>
struct Empty : public FingerTree<A> {
  Empty() { this->type = Fempty; }
};

template<typename A>
struct Single : public FingerTree<A> {
  A val;
  Single(const A &val) { this->val = val, this->type = Fsingle; }
};

template<typename A>
struct Deep : public FingerTree<A> {
  deque<A> digit1, digit2;
  FingerTree<Node<A>> *subtree;
  Deep(deque<A> digit1, FingerTree<Node<A>> *ptr, deque<A> digit2) {
    this->digit1 = digit1;
    this->digit2 = digit2;
    this->subtree = ptr;
    this->type = Fdeep;
  }
};