Recursive Data Type

我們除了裡用 product 或者 sum 來組成的我們 type 以外，還可以使用 recursive 的概念來定義 type，簡單來說就是一個 type 的定義包含他自己本身。

從一個我們最常見的 List 來看，還記得 [1,2,3,4,5] 其實只是 1:2:3:4:5:[] 的語法糖，所以其實我們可以說 List 是一個要馬是空的不然就是有一個值的 type。

data List = Empty | Cons Int List deriving(Show)

那我們使用 Cons 這個 value constructor 時大概會像是這樣

lt1 = Cons 1 Empty
:t lt -- lt :: List

lt2 = Cons 2 lt
lt2 -- Cons 2 ( Cons 1 Empty)
:t lt2 -- lt2 :: List

lt3 = 3 `Cons` lt2 
lt3 -- Cons 3 (Cons 2 (Cons 1 Empty))
:t lt3 -- lt3 :: List

lt' = 1 `Cons` Empty
lt' -- Cons 1 Empty
:t lt' -- lt' :: List

會發現大致上就跟 list 的 : 很像，還記得 [1,2,3] 跟 1:2:3:[] 是同一回事，就如同我們上面先從 Cons 1 Empty 開始串接。

而且我們一樣也可以用 infix 的呼叫方式 1 Cons Empty 讓這個我們重新實作的 List 更趨近於原生的 list 。

再更進階點我們能指定特殊字元來當作我們的 value constructor

infixr 5 :!
data List' = Empty' | Int :! List' deriving (Show)

這裡會看到新的語法 fixity 宣告 infixr ，當我們需要將 function 定義成 operator 且需要改變優先權的時候就會使用到它，而 fixity 的宣告有三種 infixl、infix、infixr 分別代表左結合、無結合、右結合，而旁邊的數字 5 則是代表優先權。

就像原本的 * 、+ 這些 operator 一樣，他們也有優先權之分，像是我們都知道 * 比 + 更優先所以 3 * 3 + 3 就是等同於 (3 * 3) + 3 。

那我們也能用 :info 來看一下我們常見的 operator 的資訊

:info :
type [] :: * -> *
data [] a = ... | a : [a]
  	-- Defined in ‘GHC.Types’
infixr 5 :

:info +
type Num :: * -> Constraint
class Num a where
  (+) :: a -> a -> a
  ...
  	-- Defined in ‘GHC.Num’
infixl 6 +

這邊告訴我們大致告訴我們 : 及 + 怎麼使用、優先級、適用的 type 。

回到我們的 List' ，我們已經用了 :! 來當作我們的 value constructor 所以程式碼就會變成

lt1' = 1 :! Empty'
lt2' = 2 :! lt1'
lt3' = 3 :! lt2'

lt1' -- 1 :! Empty'
lt2' -- 2 :! (1 :! Empty')
lt3' -- 3 :! (2 :! (1 :! Empty'))

會看到我們原本的 Cons 都已經變成 :! 看起來舒服許多。

那既然 + 、* 這些 operator 也是 function ，而且現在我們也知道我們自己定義 operator ，那我們是不是可以自己創造來類似 ++ 的operator 串接 List' ？

沒錯當然可以，而且在 Haskell 實作起來也相當簡單

infixr 5  .++
(.++) :: List' -> List' -> List'
Empty' .++ ys = ys
(x :! xs) .++ ys = x :! (xs .++ ys)

我們就把他設計的跟 ++ 很像，首先看到我們定義 .++ 的 fixity 為 infixr 5 ，以及 (.++) 這個 function 的 type 是 (.++) :: List' -> List' -> List' ，也就是他接受兩個 List' 並最後回傳一個 List' 。

再來就是pattern matching 的部分，首先我們說如果Empty' 與 ys 進行 .++ 也就是會回傳 ys

(x :! xs) .++ ys = x :! (xs .++ ys) ，這邊就是運用到遞迴的概念，如果匹配到 x:! xs 及 ys 的形式時，就是將 x 使用 :! value constructor 塞進 xs .++ ys 然後不斷遞迴直到最後一個與 Empty' 進行 .++ 運算

lt1' .++ lt2' -- 1 :! (2 :! (1 :! Empty'))

這幾天大致上把 ADT 比較重要的概念都講到了那對我來說 ADT 帶給我最大的啟發大概是用另外一種角度看 type 到底是什麼東西，它是可以組合、遞迴的而不單單只是一個描述 valuable 的語法。

在我學習 ADT 之前我一直覺得這是一個非常難以親近的概念，但實際用起來其實跟我在使用 typescript 時的概念是部分重疊，當然 typescript 的型別機制無法跟 Haskell 相比，但至少我們可以知道這些概念是可以放到其他程式語言是部分共通。

比如說 sum type 跟 ts 的 union type 好了，先有一個前提「他們兩個絕對不等價」

簡單來說的話就是，一個是 union 一個是 disjoint union

但就我們在使用的思路上會有一點雷同，通常都是我們在限制一個 valuable 只有某幾種 type 時會用到，但 Haskell 因為有 pattern matching 所以使用起來更舒服，而在 ts 大部分就是寫利用 type guard （就是一堆 predicate 跟 if/else ）協助我們確定這個 valuable 到底是什麼 type 。