Scheme：使用fold實現n參數

Question

我試圖在Scheme中找到多個參數「compose」的「最佳」實現（我知道這是在某些實現中的內建，但假設我現在是使用一個沒有這個的）。

對於2參數構建功能我有這樣的：

(define compose 
    (lambda (f g) 
    (lambda x 
     (f (apply g x))))) 

這樣做的好處是，如果最右側的功能需要額外的參數，這些仍然可以通過組合功能通過。這具有令人滿意的特性，即在某物上組合身份功能不會改變該功能。

例如：

(define identity 
    (lambda (x) x)) 

(define list1 
    (compose identity list)) 

(define list2 
    (compose identity list1)) 

(list2 1 2 3) 
> (1 2 3) 

現在做一個「正論證」撰寫我可以這樣做：

(define compose-n 
    (lambda args 
    (foldr compose identity args))) 

((compose-n car cdr cdr) '(1 2 3)) 
> 3 

但這不再保留那該多好「身份」屬性：

((compose-n identity list) 1 2 3) 
> procedure identity: expects 1 argument, given 3: 1 2 3 

問題是用於foldr命令的「初始」函數。它已內置：

(compose identity (compose list identity)) 

所以......我不確定最好的解決方法。 「與foldl」似乎是天然的更好的選擇，因爲我想將它與「身份」開始對左不是權 ...

但天真的實現：

(define compose-n 
    (lambda args 
    (foldl compose identity args))) 

其中工程（必須扭轉的功能應用程序的順序）：

((compose-n cdr cdr car) '(1 2 3)) 
> 3 

因爲現在我最終把身份功能左側沒有解決不了的問題！這就像，我需要使用「foldr」，但需要一些不同的「初始」值比身份函數...或更好的身份函數？顯然我很困惑！

我想實現它無需編寫明確的尾遞歸「循環」 ...這似乎應該有一個優雅的方式來做到這一點，我只是卡住了。

Answer 1

你可能想嘗試this version（使用reduce從SRFI 1）：

(define (compose . fns) 
    (define (make-chain fn chain) 
    (lambda args 
     (call-with-values (lambda() (apply fn args)) chain))) 
    (reduce make-chain values fns)) 

這不是火箭科學：當我張貼這對#scheme IRC頻道，Eli指出，這是標準的落實compose 。 :-)（作爲獎勵，它也適用於你的例子。）

Answer 2

雖然它會一直爲「空」名單下放給身份功能不錯，交出這似乎導致在下面，這是不是太糟糕：

(define compose-n 
    (lambda (first . rest) 
    (foldl compose first rest))) 

((compose-n cdr cdr car) '(1 2 3)) 

((compose-n list identity identity) 1 2 3) 

Answer 3

這裏的問題是你正在嘗試混合不同的程序。你可能想咖喱列表，然後做到這一點：

(((compose-n (curry list) identity) 1) 2 3) 

但這並不是很令人滿意。

你可能會考慮n元身份功能：

(define id-n 
    (lambda xs xs)) 

然後你就可以創建一個撰寫程序專爲撰寫n元功能：

(define compose-nary 
    (lambda (f g) 
    (lambda x 
     (flatten (f (g x)))))) 

撰寫的N-任意數量ary功能與：

(define compose-n-nary 
    (lambda args 
    (foldr compose-nary id-n args))) 

其中的作品：

> ((compose-n-nary id-n list) 1 2 3) 
(1 2 3) 

編輯：它有助於思考的類型。讓我們爲我們的目的發明一種類型符號。我們將表示作爲(A . B)對類型，並且作爲[*]列表的類型，與約定[*]相當於(A . [*])其中A是列表的car（的類型，即一個列表是一個對的原子的和一個列表）。讓我們進一步將函數表示爲(A => B)，意思是「帶一個A並返回一個B」。 =>和.都與右側相關，所以(A . B . C)等於(A . (B . C))。

那麼現在，因爲，這裏有list（讀::爲 「有型」）類型：

list :: (A . B) => (A . B) 

而這裏的身份：

identity :: A => A 

有實物的區別。 list的類型由兩個元素構成（即，列表的類型具有種類* => * => *），而identity的類型由一種類型構建（身份的類型具有種類* => *）。

組合物具有這種類型：

compose :: ((A => B).(C => A)) => C => B 

見，當你申請compose到list和identity會發生什麼。 A與list函數的域統一，所以它必須是一對（或空列表，但我們會對此進行說明）。 C與identity函數的域統一，所以它必須是一個原子。那麼兩者的組成就必須是一個函數，它需要一個原子C併產生一個列表B。如果我們只給這個函數原子，這不是一個問題，但是如果我們給它列表，它會窒息，因爲它僅僅期待一個參數。

這裏的咖喱如何幫助：

curry :: ((A . B) => C) => A => B => C 

應用curry到list，你可以看到發生了什麼。輸入到list與(A . B)統一。由此產生的功能需要一個原子（汽車）並返回一個函數。該函數反過來將剩下的列表（B類型的cdr），並最終生成列表。

重要的是，咖喱的list功能與identity的功能相同，因此它們可以毫無問題地組成。這也適用於其他方式。如果創建一個帶有成對的身份識別功能，則可以使用常規的list功能組成該功能。

Answer 4

OP提到（在我的回答評論中）他的Scheme的實現沒有call-with-values。這是僞造它的一種方法（如果您可以確保<values>符號從未在您的程序中使用過：您可以用(void),(if #f #f)或任何您不喜歡的未使用的代碼替換它，並且您的實現支持這一功能）：

(define (values . items) 
    (cons '<values> items)) 

(define (call-with-values source sink) 
    (let ((val (source))) 
    (if (and (pair? val) (eq? (car val) '<values>)) 
     (apply sink (cdr val)) 
     (sink val)))) 

這樣做的目的是通過以<values>符號爲首的列表僞造一個多值對象。在call-with-values網站上，它會檢查該符號是否存在，如果不存在，則將其視爲單個值。

如果鏈中最左邊的函數可能返回一個多值，那麼您的調用代碼必須準備好解壓<values>-heads列表。 （當然，如果你的實現沒有多個值，這可能不會讓你太擔心。）