編程語言中的「組合性」是什麼意思？

01-02

在函數式語言中似乎經常強調其語言的「組合性」（composability），這裡的「組合性」是指什麼？
是指 f.g 這樣的函數組合么？但是它同其他編程語言中的 f(g(x)) 有什麼區別？
是指像
data MyType = MyType Int Double WhateverType
這樣的代數數據類型么？
它同

struct MyType{ int x, double y, Whatever z };
這樣的語法，在「組合性」上又有什麼區別？
所以：

編程語言中的」組合性「具體是指什麼？

函數式語言相對其他語言在」組合性「方面具有

謝邀, 安利一下, 剛好這周討論的文章跟這個問題有關

本周話題: Category: The Essence of Composition · Issue #27 · CNMDR3G/CNMDR3G · GitHub

曾經在到底什麼是函數式編程思維？回答說函數編程思維就是追求可組合性, 那個時候已經有模糊的感覺到現在還沒能夠像其他答案一樣"簡單來說"就能說出來, 等我範疇論學好了再回來答

f.g 表達複合函數（組合函數調用），是函數組合的一種形式；

其它語言的 f(g(x)) ，如果是scala的compose（或clojure的comp）則是一樣的，別的語言(沒有函數)手寫f"(x) = f(g(x)) 也是一樣的。

但是為什麼突然冒出ADT來，我不理解。

組合性

Function composition (computer science)

其實就是函數可組合的能力

函數組合，則是將多個函數並成一個函數的過程(比如&>&> 和 . 乃至 monad 此處寫做&>&>=更好)

例子：

id + const

&> :t id id :: a -&> a &> :t const const :: a1 -&> b -&> a1 &> :t const id const id :: b -&> a -&> a &> let scd = const id &> scd 1 2 2 -- &>&> 和 . 則直接得不到 scd &> :t const &>&> id const &>&> id :: a -&> a &> :t const . id const . id :: b -&> b1 -&> b &> :t id . const id . const :: a -&> b -&> a

組合的價值在於重用，重用就是DRY, 若是這麼結束就太無聊了，必須深挖一下這個話題，題主的問題很好啊！下面是我的一些總結：（沒啥深奧的，只是安利幾條common sense）

pure function

純函數為函數組合性有無的分界線，非純函數一定沒有組合性，只有純函數才可組合。（這話是不正確的，但是卻很有價值，價值在於鼓勵盡量少寫帶副作用的函數（Haskell里好像問題不大），帶副作用的函數組合得依靠monad）

組合性大小

也就是函數組合能力大小，或者是一個函數可重用的可能性大小

多態函數 &> 常態函數 (不同語言叫法不一樣哇)

&> :t id id :: a -&> a &> :t (+) (+) :: Num a =&> a -&> a -&> a &> let add x y = x + y :: Int &> :t add add :: Int -&> Int -&> Int

id &> (+) &> add

函數定義（類型）越抽象，可組合性就越大；顯然無拘無束的id是幾乎可與任何函數組合的（至於有沒有卵用，則就是需求問題了），而（+） &> add 也很明顯；

函數組合形式(基本組合子)

複合函數確實是很直觀的函數組合形式，但是函數組合則比.或&>&>（同scala的compose和andThen）自由的多，就如上面那個const + id; （其實是一次部分應用），不一定要拘泥於複合函數的形式, 我把.,&>&>等函數稱為函數組合的基本組合子（定義函數組合的基本規則）

-----下面跳到scala描述

函數組合主要來表達函數重用，那麼我通過foldRight來實現exists，forAll，filter還有map，flatMap也是函數組合：

def exists(p: A =&> Boolean): Boolean = foldRight(false){(a,b) =&> p(a) || b } //op = (a,b) =&> p(a) || b


  def forAll(p: A =&> Boolean): Boolean =

    foldRight(true){(a,b) =&> p(a)  b}
  def filter(p: A =&> Boolean): Stream[A] =

    foldRight(empty[A]){(h,t) =&> if(p(h)) cons(h,t) else t}
  def map[B](p: A =&> B): Stream[B] =

    foldRight(empty[B]){(h,t) =&> cons(p(h), t)}

def flatMap_1[B](f: A =&> Stream[B]): Stream[B] = foldRight(empty[B]){(h,t) =&> f(h) #++ t}

以上就是通過foldRight組合子（函數）實現其它組合子的過程，foldRight與各種op的組合，比如map：

def map[B](p: A =&> B): Stream[B] = { foldRight(empty[B]){(h,t) =&> cons(p(h), t)} }

等價於，以下複合函數的形式

def f[B](op: (A, =&> Stream[B]) =&> Stream[B]): Stream[B] = foldRight(empty[B])(op) def g[B, C &>: A](p: C =&> B)(h: C ,t: =&> Stream[B]): Stream[B] = cons(p(h), t) def map_1[B](p: A =&> B): Stream[B] = (f[B] _ compose g[B, A])(p) //將foldRight(empty[B])和g組合起來

（filter+ other 又可組合出新的函數）

函數式本身就是一種組合邏輯，需要組合各種基本函數獲得更複雜功能更強大的函數的一種設計方式，俗稱：自底向上

所以最常見的組合形式，其實就是重用多個函數返回新的函數，只不過引入中間函數(如上面的f,g)（下面稱為轉換子）可轉為f.g的複合函數形式

Monad

Monad本身就是挖幾個坑，然後把函數填進去，（看&>&>=的形式），只舉個例子：

def f(x: Int) = Some(x) def g(y: String) = Some(y) def fg(x: Int, y: String) = for { a &<- f(x) b &<- g(y) } yield a + b

至於單子可以組合帶副作用的函數，這句話當然是錯的，單子只能組合純函數，但是可以將副作用推遲，或者隔離成純函數部分以及副作用部分，間接的來說就是組合了非純函數了，可腦補IO Monad

自定義組合

之前看到過抽象出Process[I, O]類型，並定義|&> 方法去組合Process:

def count[I]: Process[I,Int] = lift((i: I) =&> 1.0 ) |&> sum |&> lift(_.toInt)

如同&>&>= 是一種自定義的組合方式

函數類型與組合性

前面提到函數類型定義會關係到組合性的大小，其實函數類型是函數組合的基礎；函數組合可認為是一套基於函數類型的代數系統。

前面為何可以用foldRight實現exists，forAll，filter等函數？

看函數類型：

foldRight[B](z: B)(op: (A, =&> B) =&> B): B map[B](p: A =&> B): Stream[B] ...

已知map是A =&> B =&> Stream[B]的函數，

那麼就要把(z: B) =&> (op: (A, =&> B) =&> B) =&> B

變為(Stream[B]) =&> ((A, =&> Stream[B]) =&> Stream[B]) =&> Stream[B],

部分應用第一個參數後返回f: ((A, =&> Stream[B]) =&> Stream[B]) =&> Stream[B],

那麼g就是(A =&> B) =&> ((A , =&> Stream[B]) =&> Stream[B]), 返回部分可做op傳入，這樣g和f就可以組合起來了。

所以，函數類型決定了函數組合方式。

類型同構

(以下把compose 寫做.)

如果:

f: A =&> B

g: C =&> D

B ～ C (B與C是同構關係)

那麼f g可組合，只要引入同構函數fbc, 則：fg = f.fbc.g

同樣函數(高階函數)類型也可做同構

f: A =&> (B, C)

g: (A =&> (C, B)) =&> D

A =&> (B, C)和A =&> (C, B)同構，引入同構函數fabc

fg = f.fabc.g

部分應用與柯里化

f: (A, B, C) =&> D 柯里化為 A =&> B =&> C =&> D

部分應用後可得到

f": B =&> C =&> D, f"": C =&> D ...

f" uncurried為 f: (B, C) =&> D

如果有兩個函數

g: (A , B) =&> C 與 f: A =&> B

g2 = g": B =&> C （g的部分應用）

則 fg" = f.g2 = f.g"

總結

下面構建一套簡單代數系統(僅限理解,不可做運算) 來描述函數組合：

1. 定義基本組合子: + 用於組合函數如: ., &>&>, &>&>=, |&> 等等

2. 類型同構可看成一種轉換子: t

3. 部分應用也是一種轉換子: t"

4. 也可以引入任意的中間函數做轉換子: t"（可見t和t"為t"的特殊形式）

5. 任何類型的函數f和g,通過應用轉換子T: (t | t" | t")之後可以施用"+"的則稱f和g是可組合的:

fg = T(f) + T"(g)

(本人數學sense缺乏)

綜上, 函數組合的基本組合子是可以有多個的（多種定義), 他們（., &>&>, &>&>=）也滿足這個代數系統（., &>&>, &>&>=本身就是函數）,就是也具有組合性, 也可以做轉換(至於用.做基本組合子的組合形式能否轉為用&>&>=或別的組合子的形式, 不知道怎麼證明)

安利某大神的博客：名著類 - ajoo

-----------------更新 2015-10-22

http://www.haskellforall.com/2012/08/the-category-design-pattern.html 這篇文章，從Cat的角度描述compositional programming，category laws可視為compositional design pattern，從普通的函數範疇到"Kleisli" category 再到Monad，以及最後作者安利自己的Pip type，可認為Cat是普遍存在的一種設計模式（描述組合性），只要你定義的type符合 category laws。

這是一種新的角度去描述函數組合，category laws （a Composition law (°)）作為一種design pattern符合我說的基本組合子(描述函數組合的方式的運算)，你可以抽象出不同的(°)去組合functions。

在lz的例子里2種寫法其實意義差不多。。以hakell為例子，不僅有一般的複合函數f.g，而且還有在某一背景下複合的函數-monad,寫作f&>&>g，可以把&>&>看成 . ，但是&>&>在複合函數的時候，可以有額外的作用，比如可以根據f的返回值，來決定是否執行g (maybe monad)

F#文檔里摘了一段(官方翻譯太爛, 尼瑪機翻的吧):

函數組合和流水線處理

F# 中的函數可以由其他函數組合得到。由 function1 和 function2 這兩個函數組合而成的另一個函數表示先應用 function1，接著應用 function2：

let function1 x = x + 1

let function2 x = x * 2

let h = function1 &>&> function2

let result5 = h 100

結果為 202。

流水線處理方式可以讓函數調用鏈接在一起形成連續的操作。以下是流水線處理方式：

let result = 100 |&> function1 |&> function2

結果再次為 202。

組合運算符返回一個函數；相反，管道運算符返回一個值。下面的代碼指出了管線和組合運算符之間的區別以及函數簽名和用法。

// Function composition and pipeline operators compared.

let addOne x = x + 1

let timesTwo x = 2 * x

// Composition operator

// ( &>&> ) : ("T1 -&> "T2) -&> ("T2 -&> "T3) -&> "T1 -&> "T3

let Compose2 = addOne &>&> timesTwo

// Backward composition operator

// ( &<&< ) : ("T2 -&> "T3) -&> ("T1 -&> "T2) -&> "T1 -&> "T3

let Compose1 = addOne &<&< timesTwo

// Result is 5

let result1 = Compose1 2

// Result is 6

let result2 = Compose2 2

// Pipelining

// Pipeline operator

// ( &<| ) : ("T -&> "U) -&> "T -&> "U

let Pipeline1 x = addOne &<| timesTwo x

// Backward pipeline operator

// ( |&> ) : "T1 -&> ("T1 -&> "U) -&> "U

let Pipeline2 x = addOne x |&> timesTwo

// Result is 5

let result3 = Pipeline1 2

// Result is 6

let result4 = Pipeline2 2

我認為組合至少有兩個好處:

惰性求值

流式處理