所有遞歸結構都可以被非遞歸解決方案替代嗎？

例如，你可以在沒有定義遞歸結構的情況下在Haskell中定義一個列表嗎？或者用一些函數替換所有列表？所有遞歸結構都可以被非遞歸解決方案替代嗎？

data List a = Empty | (a, List a) -- <- recursive definition

編輯

我給列表作爲一個例子，但我真的問一般所有的數據結構。也許我們只需要一個遞歸數據結構來處理需要遞歸的所有情況？就像Y combinator是唯一需要的遞歸函數一樣。 @TikhonJelvis的回答讓我想到了這一點。現在我很確定這篇文章更適合cs.stackexchange。

關於當前選擇的答案

我真的找了一個看起來更像@DavidYoung & @TikhonJelvis給出的那些答案，但他們只給了部分答案，我很欣賞他們。所以，如果有任何使用功能概念的答案，請分享。

來源

2015-05-19 Lay González

你是在暗示[遞歸計劃]（http://patrickthomson.ghost.io/an-introduction-to-recursion-schemes/）什麼的？ – Carsten

@CarstenKönig我只讀過那篇文章的標題，我不知道它可能是這個問題的答案，但它是有道理的，因爲我確實試圖重構一個應用程序以使用f＃更加反應，擴展。讓我檢查一下。非常感謝。 –

好吧，最後會有一些遞歸定義，它的類型取決於你所看到的列表的定義屬性 - 例如，你可以將列表等同於「摺疊」操作，並且它不會有遞歸在它的數據結構（它只是一個函數），但它很可能會在它的評價 - 或者你可以看到它作爲一個長陣列或... – Carsten

我認爲這個問題分解成考慮到Haskell中提供了三種不同功能的子集：

設施定義新的數據類型。
內置類型的曲目。
允許與語言外部功能接口的外部函數接口。

只看（1），本機類型定義工具並不真正提供除遞歸以外的任何無限大類型的定義。（2），然而，Haskell 2010 provides the Data.Array module，它提供的數組類型與（1）一起可以用來構建許多不同結構的非遞歸定義。即使語言沒有提供數組，（3）意味着我們可以將它們作爲FFI擴展插入到語言中。 Haskell實現還允許提供可用於此的額外功能，而不是FFI，許多GHC庫都利用這些功能（例如，vector）。

所以我想說，最好的答案是Haskell只允許你定義非遞歸集合類型，只是它提供了基本的內建元素，你可以使用它作爲更復雜的構建塊。

來源

2015-05-20 20:44:13

也許最令人興奮的答案，但簡單而真實。數組，循環，gotos，int和float都足夠用於一切。遞歸數據類型可以由其他解決方案取代，甚至可能不是數據類型。所以，如果你可以在haskell中建立一個程序集或c解釋器，那麼這將是一個解決方案。 –

這是一個奇怪的問題。我認爲答案是不是真的，但數據類型的定義不必直接遞歸。

最終，列表是遞歸數據結構。如果沒有某種遞歸，你就無法定義它們。這是它們本質的核心。

但是，我們不必對List遞歸進行實際定義。相反，我們可以將遞歸分解爲單個數據類型Fix，然後使用它定義所有其他遞歸類型。從某種意義上說，Fix只是捕捉了數據結構遞歸意義的本質。（這是fix函數，該函數用於功能同樣的事情的類型級版本。）

data Fix f = Roll (f (Fix f))

的想法是，Fix f對應f反覆應用到自身。爲了使它與Haskell的代數數據類型一起工作，我們必須在每個級別都拋出一個Roll構造函數，但這不會改變該類型所代表的內容。

從本質上講，f重複應用於自身，這是遞歸的本質。現在

我們可以定義一個非遞歸模擬List接受一個額外的類型參數f，取代我們先前的遞歸：

data ListF a f = Empty | Cons a f

這是不遞歸一個簡單的數據類型。

如果我們將兩者結合起來，我們會得到舊的List類型，除了在每個遞歸步驟中使用一些額外的Roll構造函數。

type List a = Fix (ListF a)

這種類型的值是這樣的：

Roll (Cons 1 (Roll (Cons 2 (Roll Empty))))

它承載相同的信息(Cons 1 (Cons 2 Empty))甚至只是[1, 2]，但一些額外的構造灑通過。

因此，如果您獲得Fix，則可以在不使用遞歸的情況下定義List。但這並不特別特殊，因爲在某種意義上，Fix是遞歸。

來源

2015-05-19 17:23:13

現在我想知道是否有一個除了'* - > *'以外的''Fix'版本。 – dfeuer

我不確定是否全部遞歸結構可以被非遞歸版本替換，但一些肯定可以，包括列表。一種可能的方法是使用所謂的Boehm-Berarducci encoding。這一種方式來表示的結構作爲一個函數，具體地摺疊在該結構（foldr在列表中的情況下）：

{-# LANGUAGE RankNTypes #-} 

type List a = forall x . (a -> x -> x) -> x -> x 
         -- ^^^^^^^^^^^^^ ^
         -- Cons branch  Nil branch

（來自具有稍微不同的格式以上的鏈接）

這種類型也是類似於列表中的案例分析。第一個參數代表cons情況，第二個參數代表無情況。

通常，和類型的分支變成函數的不同參數，並且產品類型的字段變爲具有每個字段的參數的函數類型。請注意，在上面的編碼中，nil分支（通常）是非函數，因爲nil構造函數不接受任何參數，而cons分支有兩個參數，因爲cons構造函數接受兩個參數。定義的遞歸部分用「N」類型（這裏稱爲x）「替換」。

來源

2015-05-19 18:12:09

上面的編碼通常足以涵蓋絕大多數的遞歸定義。也許某些未被覆蓋的是多態遞歸，例如數據A a =空|分支a（A（a，a））' - 注意'A a'不是用'A a'而是用'A（a，a）'來定義的。所以它是'A'，它是根據自身定義的，而不是'A a'。 – chi

@chi這是一個很好的觀點。我想知道是否有*功能類型的編碼，可以用於那種非常規的數據類型... –

所有遞歸結構都可以被非遞歸解決方案替代嗎？

回答

相關問題