爲什麼Haskell不能爲一維數組提供摺疊？

Question

Data.Array不提供Array類型的摺疊。 （第12章）

在真實世界哈斯克爾，原因據說是Array小號可能以不同的方式根據程序員的需要進行摺疊：

首先，有幾種摺疊有意義。我們仍然可能想要摺疊單個元素，但是現在我們也可以摺疊行或列。除此之外，對於每次元素摺疊，不再只有兩個序列用於遍歷。

這與List s不完全對應嗎？代表例如具有多維List的矩陣，但仍存在爲一維List s定義的摺疊。

我失蹤的微妙之處是什麼？是否多維Array與Array的Array完全不同？

編輯：嗯，甚至多維數組確實有褶皺定義，在Data.Foldable實例的形式，[0]那麼，如何適應，在與真實世界哈斯克爾報價？

[0] http://hackage.haskell.org/packages/archive/base/4.6.0.0/doc/html/Data-Foldable.html

Answer 1

由於您提到「多維」Array和Array的Array s之間的差異，這將很好地說明這一點，並與列表進行比較。

摺疊（在Foldable類的意義上）是一種固有的線性操作，就像列表本身是線性結構一樣;右對齊通過將其構造函數與參數foldr進行一對一匹配來充分表徵列表。雖然您也可以定義諸如foldl之類的函數，但是標準摺疊有明確的選擇。

Array沒有這樣的透明結構，可以在摺疊中一對一匹配。它是一種抽象類型，可以訪問由索引值提供的各個元素，這些元素可以是任何類型的，具有Ix實例。因此，不僅沒有明顯的實現摺疊的選擇，也沒有內在的線性結構。它發生了這樣的情況，Ix可以讓你枚舉一系列索引，但這比其他任何更多的實現細節。

什麼多維Array S'它們並不真正存在，因此。 Ix定義爲實例的，同時也是實例類型的元組，如果你要考慮這樣的元組作爲索引類型爲「多維」 Array，去吧！但他們仍然只是元組。顯然，Ix在這些元組上放置了一些線性順序，但它是什麼？你能在文檔中找到任何告訴你的東西嗎？

所以，我認爲我們可以有把握地說，使用Ix定義的順序摺疊多維Array是不明智的，除非你真的不關心你會得到什麼樣的順序中的元素。

對於Array的Array小號，另一方面，只有一個將它們組合，很像嵌套列表明智的方式：摺疊每個內Array分別按照自己的元素的順序，然後折根據外Array的元素的順序的每個的結果。

---

現在，你很可能會反對說，因爲有一維和多維Array s，而前者之間沒有類型區分，可認爲具有基於Ix實例明智倍訂貨，爲什麼不使用那默認排序？畢竟，已經有一個函數在列表中返回Array的元素。

事實證明，圖書館本身會同意你的看法，因爲這正是Foldable實例的功能。

Answer 2

有摺疊列出一個自然的方式，這是foldr。注意類型列表構造函數：

(:) :: a -> [a] -> [a] 
[] :: [a] 

與b更換的[a]的出現，我們可以得到以下類型：

f :: a -> b -> b 
z :: b 

而現在，當然，的foldr類型是基於這個原理：

foldr :: (a -> b -> b) -> b -> [a] -> b 

因此，考慮建設/列表的觀察語義，foldr是一個的MOS自然。你可以閱讀這個類型爲「告訴我如何處理(:)以及如何處理[]，我將爲你排除一個列表。」

Array沒有此屬性;你從一個關聯列表（Ix i => [(i,a)]）建立一個數組，並且這個類型並沒有真正公開任何遞歸結構：一個數組不是通過遞歸構造器從其他數組構建的，因爲列表或樹會是這樣。