[C++]代數數據類型與模式匹配

由於水平有限，我實在不敢亂講代數數據類型和模式匹配。

如果你學過函數式的語言，那應該對這兩個概念很熟悉。

如果沒學過，可以參考：

代數數據類型是什麼？ - 7 個回答, 154 人關注

以及我曾經提過的一個問題。

在這個問題下，答主們提供了各種各樣的實現方式，讓我大開眼界。我在他們的幫助下自己摸索著實現了一個簡陋的ADT庫。在這篇文章中，我想談談我在這次實驗中的收穫。由於C++模板的知識太繁雜，本文會適當省略。（其實是因為我又菜又懶，講不清楚，逃...

模式匹配中一個很重要的問題就是要分清左值和右值。例如Haskell中計算階乘的函數

factorial 1=1nfactorial n=n * factorial (n-1)n

在調用factorial 2時，會逐一匹配上述兩條規則。對於第一條factorial 1，匹配的操作是判斷2==1，而第二條factorial n，匹配的操作卻是把2賦值給n。我們在用C++實現模式匹配時，必須分清2和n。但是在c++中，不存在未定元這一概念，不管有沒有初始化，n這個變數一直是有值的。因此，如果我們的參數列表寫為

int factorial(int);n

那麼factorial(1)與factorial(n)沒有任何區別。

這時，我想到了C++里有一種傳參的方式叫傳引用，右值不能以傳引用的方式傳入函數。於是，我們可以寫出以下兩個函數的聲明。

int fun(int);nint fun(int&);n

但是，由於上述兩個函數均可以傳入左值，所以編譯器沒法判斷應該選擇哪種傳參方式。但令人高興的是，C++11提供了一種新的傳參方式，傳右值引用。於是，我們的函數聲明可以這樣寫。

int fun(int &&);nint fun(int &);n

這樣，右值傳入int fun(int &&)，左值傳入int fun(int &)。模式匹配也就很容易實現了。

另外，如果你想把左值轉換為右值進行匹配，可以通過std::move函數來產生一個右值引用。

模板實現的模式匹配函數的代碼在這裡 var_match.hpp

用起來是這樣的

#include <iostream>n#include "var_match.hpp"nnusing namespace std;nnint main()n{n // match with rvaluen // falsen if(var_match(2,1)) cout<<"2==1n";n else cout<<"2!=1n";nn // truen if(var_match(2,2)) cout<<"2==2n";n else cout<<"2!=2n";nn // match with lvaluen // always truen int x=3;n if(var_match(2,x)) cout<<"x="<<x<<endl;n else cout<<"failedn";nn // match with rvalue(made by move() function)n // falsen x=2;n if(var_match(4,move(x))) cout<<"4==2n";n else cout<<"4!=2n";nn // match with diffrent typesn // falsen if(var_match(2.33,x)) cout<<"x can be 2.33n";n else cout<<"x cant be 2.33n";n return 0;n}n

• 和類型(sum types)

和類型可以用tagged union實現。這裡我直接使用了boost::variant，省去了很多麻煩。

我的TypeAdd類僅僅是對boost::variant的一個封裝。

template<typename T1,typename...T>nclass TypeAdd:public boost::variant<T1,T...>{};n

• 積類型(product types)

積類型我是在std::tuple的基礎上擴展的。

template<typename T1,typename...T>nclass TypeMul:std::tuple<T1,T...>{};n

把std::get封裝進類裡面，並且提供了對tuple的模式匹配。

上面我們已經處理了單個變數的模式匹配問題，多個變數的要稍微麻煩一點，因為多個變數很多時候是左值和右值的混合。而可變參數模板的可變參數部分（即...部分）默認是按值傳遞的，這樣會導致左值右值信息的丟失。為了解決這個問題，我把模板的固定參數設為兩個，並用std::forward對第二個參數進行完美轉發。

template<typename MT1,typename MT2,typename...MT>nbool Match(MT1&& v,MT2 && t,MT... args)n{ntif(Match<MT2,MT...>(std::forward<MT2>(t),args...)==false) return false;ntreturn Get<count-sizeof...(args)-2>().Value()==v;n}nntemplate<typename MT1,typename MT2,typename...MT>nbool Match(MT1& v,MT2 && t,MT... args)n{ntif(Match<MT2,MT...>(std::forward<MT2>(t),args...)==false) return false;ntv=Get<count-sizeof...(args)-2>().Value();ntreturn true;n}n

說明：

1. Get函數是對std::get的封裝。

2. 所有對象都必須調用Value()才能拿到值，這點後面我會解釋。

• 遞歸類型

例如：列表List

data List a=Nil | Cons a (List a)n

C++里沒法簡單地實現上述遞歸類型。對於第二個構造器Cons a (List a)，C++會追問清楚這樣的遞歸一共有多少層，因而，擁有不同層數的List便不是同一種類型，那麼又要用奇怪的模板黑魔法來判斷一個類型到底是不是List......這樣就太繁瑣了。

所以我索性用了指針類型，繞過了C++的類型檢查。

我定義了一個模板類RecursiveCon，對指針的操作進行了封裝。

template<typename T>nclass RecursiveConn{nprivate:ntstd::shared_ptr<T> data=0;npublic:nttypedef T type;ntRecursiveCon(){}ntRecursiveCon(T* p)nt{nttdata=p;nt}ntRecursiveCon(const T& v)nt{nttdata = std::shared_ptr<T>(new T);ntt*data=v;nt}ntRecursiveCon(const RecursiveCon<T>& a)nt{nttdata=a.data;nt}nntT Value(){return *data;}n};n

為了統一介面，我又設計了一個普通的構造器GeneralCon，同樣以Value()返回值。

這樣，只要保證TypeMul的模板參數都是RecursiveCon或GeneralCon就能保證這套方案正常工作。

• 用宏實現的DSL

我就裝逼地稱它為DSL了（捂臉逃

由於知乎編輯器不太友好，我就上截圖了

然後用起來效果是這樣的

Data(List)ntEnum(Nil)ttttntMul(Cons,GeneralCon<int>,RecursiveCon<List>)nEndData(List,Nil,Cons)nnint Length(List l)n{ntWith(l)nttCase(List,Nil)ntttreturn 0;nttCase(List,Cons,_,l)ntttreturn Length(l)+1;ntEndWith()n}n

等價於

data List= Nil | Cons Int Listnlength::List->Intnlength Nil = 0nlength (Cons _ l) = 1 + length ln

最後，期待指針聚聚@孫明琦 用C++17給出更tricky的模板實現。

附上代碼：

ADT.hpp

若文中存在錯誤，歡迎在評論區指出，真誠地謝謝您對我的幫助。