一道有趣的函數式建模練習

領域建模在於不斷挖掘領域的本質，然後用優秀的代碼簡潔地表現出來。而函數式非常適合將領域映射到數學本質上。前一陣子學習erlang，用erlang做了一些練習，分享其中的一個。

practice 1 : count tiangle

題目： 數數如下圖形中一共包含多少三角形？

答案是24，你數對了嗎？回憶一下你剛纔是怎麼數的？

這道題如果由人來數，每個人數法各異！但是如果要交給電腦來做，就必須將數的方法描述成電腦可以執行的形式化演算法。這種描述方法可以有非常多種，而我們希望找到一套抽象層次高的和領域非常貼切的描述，以降低後續理解、維護成本。

對於該問題，我們首先站在領域角度定義什麼是三角形？

triangle([A, B, C]) ->
    connected(A, B) andalso
    connected(B, C) andalso
    connected(C, D) andalso
    (not in_same_line(A, B, C)).

如上，我們定義了一個三角形就是三個點，兩兩相連，但是三個點不同時在一條直線上。

對於如上描述，關鍵是如何定義connected和in_same_line。
對於connected，就是兩個點同時在一條直線連接上。那麼什麼是一條直線連接？
由於我們關註的是點線上上的關係，所以我們定義一條直線為在直線上所有點得集合。
例如對以上例，我們存在直線：[a, b, h],[a, c, g, i]等等。

我們把上圖中所有直線用erlang描述出來：

lines() ->
    ["abh", "acgi", "adfj", "aek", "bcde", "hgfe", "hijk"].

由於我們用單字元表示點，而字元串在erlang中實際就是list，所以我們將一條直線簡寫為線上上所有點的字元的字元串。

有了對直線的定義，接下來，一個點是否在直線上，那就是元素與集合的屬於關係；而兩個點是否相連就是集合與集合之間的包含關係。

subset([], _S) -> true;
subset([H|T], S) -> 
    lists:member(H, S) andalso subset(T, S).

belong(_, []) -> false;
belong(S, [H|T]) -> subset(S, H) orelse belong(S, T).

connected(P1, P2) -> belong([P1, P2], lines()).

in_same_line(P1, P2, P3) -> belong([P1, P2, P3], lines()).

可以看到，connected的定義是兩個點組成的集合屬於所有直線的集合的任一個的子集。而in_same_line則是三個點的集合屬於所有直線的集合的任一個的子集。
我們在這裡將該問題映射到熟悉的集合領域。

在有了對connected和in_same_line的定以後，我們就可以對triangle進行測試了！

test() ->
    true = triangle("abc"),
    false = triangle("abh").

下來我們來進行數三角形。要能夠數三角形，我們需要找到所有三個點的組合，用來驗證是否滿足triangle？將滿足triangle的進行統計，這樣我們就得到了結果！

在這裡我們已經有了所有點的集合：

Points = "abcdefghijk"

為了得到所有3個點的組合，我們實現一個演算法，對於集合L，求其N個元素的所有組合的集合。

comb(L, 1) -> [[I] || I <- L];
comb(L, N) when length(L) =:= N -> [L];
comb([H|T], N) -> 
    [[H|R] || R <- comb(T, N - 1)] ++ comb(T, N).

Points = "abcdefghijk",
TriplePoints = comb(Points, 3),

下麵我們實現一個count方法，用來數滿足要求的三角形個數：

count(Triple) -> count(Triple, 0).

count([], N) -> N;
count([H|T], N) ->
    case triangle(H) of
        true -> count(T, N + 1);
        false -> count(T, N)
    end.

最後可以調用run測試一下是不是24！

run() ->
    Points = "abcdefghijk",
    TriplePoints = comb(Points, 3),
    count(TriplePoints).