在現代代數的系統裏，最重要的工作便是把不同的結構(元素與運算)抽象化出來而進行定義，再以此抽象化的結構，推導其相關定理，在往後的日子裏，只有要新的結構滿足結構的定義，就可順理成章的使用既有的定理。在函數式程式設計中，「高階類別」(High Kinded Type簡稱HKT)在抽象化的工作中扮演非常重要的角色，接下來我們將介紹HKT。

Higher Kinded Type

在強型別系統的函數式程式設計語言中，所謂的Kind就是型別建構子(型別容器)，你可以把它看成是型別的函數，我們可以用下列的方式來表示Kinds。

*是所有具體types所形成的kind，也就是一個變數或常數(包括函數)所能具備的型別，像number， string， Array，Option， Either<Error, string>…等。

* -> * 則是具有一個型別參數的型別建構子(型別容器)集合所成的Kind，像Option，IO，Task…等。

* -> * -> * 則是具有二個型別參數的型別建構子(型別容器)集合所成的Kind，像
Either，EitherTask，State…等

依此類推…

所謂類別就是具有相同介面的型別建構子(Kind)，支援HKT的程式語言中，可以直接定義這些高級類別支援HKT的程式語言會允許我們將滿足某些特定性質的型別建構子抽象化，讓我們可以撰寫適用於任何「容器」的函數，只要該容器滿足我們抽象化的性質。例如，具備map函數的型別建構子便是屬於Functor類別，以Haskell來說，它可以直接以下面的方式定義Functor類別：

-- Functor 型別類別需要一個型別參數 `f`。
-- 類別簽名顯示 `f` 必須是類別為 `* -> *` 的型別建構子。
class Functor f where
  fmap :: (a -> b) -> f a -> f b

我們便可以替任何的型別建構子定義相對應的fmap函數以便將這個型別建構子作為Functor實例化(Instance)，以陣列來說，fmap就是陣列內建的map函數，

instance Functor [] where
  fmap = map

最後我們便可以寫一個限制在Functor上使用的通用函數。

-- 型別簽名 `(Functor f, Show b) => (a -> b) -> f a -> String`
-- 顯示 `f` 可以是任何 Functor 型別建構子。
applyAndShow :: (Functor f, Show b) => (a -> b) -> f a -> String
applyAndShow f fa = show (fmap f fa) 

因為typescript並不支援這類更高階類別（Higher-Kinded Types, HKTs），fp-ts使用了所謂Lightweight higher-kinded polymorphism的手法，達到類似的目的。首先
fp-ts透過HKT型別來表示* -> *，也就是HKT<F, A>即代表F<A>，

HKT2 來表示 * -> * -> * ，即HKT<F, E, A>即代表F<E, A>

HKT3 來表示 * -> * -> * -> *，即HKT<F, R, E, A>即代表F<R, E, A>

HKT4 來表示 * -> * -> * -> * -> *，即HKT<F, S, R, E, A>即代表F<S, R, E, A>

如此，我們可以定義下列型別

type Map = <F, A, B>(f: (a: A) => B) => (fa: HKT<F, A>) => HKT<F, B>
// 實現下面不合法的概念
// type Map = <F, A, B>(f: (a: A) => B) => (fa: F<A>) => F<B>

模組擴充

在討論fp-ts的HKT實作之前，我們先了解typescript的介面合併(interface merge)和模組擴充。我們先說明介面合併，這也是interface和type非常不同之處。我們看看下面一段程式碼，

interface User {
  name: string
}
interface User {
  age: number
}
const user: User = {name: 'John', age: 18}

我們可以定義兩個interface User，typescript不會報錯，而會將這name和age兩個屬性都加入到User這個介面中，因此當你將user指定為User型別時，兩個屬性都必須賦予，否則typescript會報錯，這就是所謂的介面合併。

至於模組擴充則是用declare module關鍵字來進行模組擴充或修改，如下面的程式碼便會將my-module模組中新增prop1和prop2兩個屬性(如果MyInterface中並沒有這兩個屬性)，如此便達到了模組擴充的目的。

declare module 'my-module' {
  interface MyInterface {
    prop1: string;
    prop2: number;
  }
}

fp-ts HKT實作探討

HKT型別是一個抽象層級，它的型別定義如下：

// fp-ts/HKT.ts
export interface HKT<URI, A> {
  readonly _URI: URI
  readonly _A: A
}

Kind才是fp-ts關於HKT的具體型別，fp-ts在HKT.ts中先定義了URItoKind、URIS和Kind。

// fp-ts/HKT.ts
export interface URItoKind<A> {}
export type URIS = keyof URItoKind<any>
export type Kind<URI extends URIS, A> = URI extends URIS 
    ? URItoKind<A>[URI] 
    : any

URItoKind是一個URI轉成具體型別(*)的表格，Kind可以接受一個型別參數URI得到具體的型別，起初在HKT定義的時候都是空的。fp-ts每個單一型別參數的型別建構子模組(例如Option、IO、Task…等)都會進行註冊，以Option為例，註冊的過程如下：

import { HKT } from 'fp-ts/HKT'
const URI = 'Option'
type URI = typeof RUI

接下來會以typescript模組擴充(module augmentation)的方式

declare module 'fp-ts/HKT' {
  interface URItoKind<A> {
    readonly Option: Option<A>
  }
}

當Option、IO和Task都註冊好了，URItoKind會長成這個樣子：

interface URItoKind<A> {
    readonly Option: Option<A>;
    readonly IO: IO<A>;
    readonly Task: Task<A>;
  }

因此Kind<'Option', number>會得到 URItoKind['Option']，也就是Option<number>這個具體型別，下圖說明了這整個HKT機制。

類別(Type Class)

接以下面的方式定義我們的Functor類別，

export interface Functor<F> {
  readonly URI: F
  readonly map: <A, B>(fa: HKT<F, A>, f: (a: A) => B) => HKT<F, B>
}
export interface Functor1<F extends URIS> {
  readonly URI: F
  readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}
export interface Functor2<F extends URIS2> {
  readonly URI: F
  readonly map: <E, A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
}
// 還有Functor2C、Functor3、Functor3C和Functor4，我們就不一一列出。

另外，applyAndShow這個函數還需要Show這個類別的的定義。

export interface Show<A> {
  readonly show: (a: A) => string
}

顯而易見的，Show<A>類別型別必須提供一個輸入為型別A，輸出為string的函數show。

那我們要如何寫出applyAndShow這個跨容器型別的函數呢？在typescript我們必須要用函數多載來實現這個目的。

在 TypeScript 裡，函數多載（overloading）是指一個函數名稱可以針對不同的參數型別，回傳值型別，定義多種不同的呼叫方式，當函數實際呼叫都能對應到單一的函數型別簽名。在定義一個多載函數時，我們需要定義多個函數的型別簽名，卻只能定義一個函數實作，而這個函數實作的型別簽名必須相容於其它多個函數的型別簽名，也就是它必須能處理所有情況，以下面的程式為例。

// 多載簽名 (只宣告型別，不寫實作)
function add(x: number, y: number): number;
function add(x: string, y: string): string;

// 單一實作 (必須能處理所有情況)
function add(x: number | string, y: number | string): number | string {
  if (typeof x === "number" && typeof y === "number") {
    return x + y;
  }
  if (typeof x === "string" && typeof y === "string") {
    return x + y;
  }
  throw new Error("參數型別必須一致");
}

// 正確使用
const n = add(1, 2);       // number
const s = add("a", "b");   // string
// 錯誤使用
add(1, "a") → 編譯錯誤

在編譯階段，當我們呼叫add函數時，typescript依次序檢查是否符合其中一個多載簽名，如果有，便會以第一個符合的型別簽名去推論回傳的型別，如果都不符合，便會出現編譯錯誤。

現在我們再重檢視applyAndShow的在Haskell型別簽名和函數實作：

applyAndShow :: (Functor f, Show b) => (a -> b) -> f a -> String

applyAndShow f fa = show (fmap f fa)

型別簽名限制了我們的ｆ必須是Functor類別，b必須是Show類別；(fmap f fa)是輸出型別會是f b(相當於fp-ts的Kind<F, B>型別)，所以show函數的輸入型別f b，因此轉換為fp-ts，我們要提供一個Show<Kind<F, B>>給applyAndShow，以下面便是applyAndShow的實作：

import { Show } from 'fp-ts/Show';
// 其它import省略
function applyAndShowWithShow<F extends URIS, A, B>(
  F: Functor1<F>,  // 參考前面的定義
  S: Show<Kind<F, B>>
): (f: (a: A) => B) => (fa: Kind<F, A>) => string {
     return (f) => (fa) => S.show(F.map(fa, f));
}

要應用這個函數，我們實作一個Show<number>型別和Show<O.Option<number>>的實作

const showNumber: Show<number> = {
  show: (n) => `Number(${n})`,
};

const showOption = <A>(S: Show<A>): Show<O.Option<A>> => ({
  show: O.match(
    () => 'None',
    (a) => `Some(${S.show(a)})`
  ),
});

最後我們可以應用這個applyAndShow函數。

const showOptionDouble = applyAndShowWithShow(
  O.Functor,
  showOption(showNumber)
)(double);
console.log(showOptionDouble(O.some(5))); // 輸出: Some(Number(10))
console.log(showOptionDouble(O.none)); // 輸出: None

一切看起來還不錯，但是這不是一個多載函數，所以這個函數只能提供給像Option這種只有一個型別參數的型別建構子使用，若我們想提供給Either這種需要兩個型別參數的建構子使用，我們必須用函數多載的方式，新增兩個型別參數的型別建構子為參數的函數型別簽名：

function applyAndShowWithShow<F extends URIS2, E, A, B>(
  F: Functor2<F>, // 參考前面的定義
  S: Show<Kind2<F, E, B>>
): (f: (a: A) => B) => (fa: Kind2<F, E, A>) => string;

最後我們還要提供一個函數實作，因為這個函數實作的型別簽名必須和前面兩個型別簽名相容，Kind和Kind2的部分將由HKT代替，而實作的內容則和單一函數時完全一樣，程式碼如下：

function applyAndShowWithShow<F, A, B>(
  F: Functor<F>, // 參考前面的定義
  S: Show<HKT<F, B>>
): (f: (a: A) => B) => (fa: HKT<F, A>) => string {
  return (f) => (fa) => S.show(F.map(fa, f));
}

最後，我們建立showEither和showEitherDouble函數：

const showEither = <L, A>(SA: Show<A>): Show<E.Either<Error, A>> => ({
  show: E.match(
    (e) => `Left(${e.message})`,
    (a) => `Right(${SA.show(a)})`
  ),
});

const showEitherDouble = applyAndShowWithShow(
  E.Functor,
  showEither(showNumber)
)(double);

console.log(showEitherDouble(E.right(6))); // 輸出: Right(Number(12))
console.log(showEitherDouble(E.left(new Error('Something error')))); // 輸出: Left(Something error)

經過函數多載定義，applyAndShow函數便可應用在不同的型別建構子上，如果這個函數希望再應用於三個型別參數的型別建構子上，可以再多定義新的多載型別簽名。

實測這個函數時發現typescript的型別推論能力不夠強，必須將tsconfig.json的strict改為false才不會報錯。

今日小結

我們今天學會了如何建立應用於某些特定介面的函數，以今天所提供的applyAndShow函數來說，我們不用替Option、Task、IO、Either和TaskEither各寫一個applyAndShow功能的函數，而且分別命名，只需用同一個函數名，而提供不同的Functor和Show的實例(Instance)即可，大大的增添了函數的彈性，大大的展現了函數式程式設計高度抽象化的威力。

另一方面，畢竟typescript並非替函數式程式設計的型別系統，fp-ts雖然設計了HKT的型別，而透過函數多載來模擬這種類別限制的函數，但是相較於Haskell來說，程式碼顯得冗長許多，這也是莫可奈何的事。今天的分享就到此為止，明天再見。