在Haskell中創建多態遞歸類型

我想在Haskell中創建一個樹型。我已經使用這個簡單的數據構造函數來存儲樹，其中每個節點可以是空的，可以是包含整數的葉，也可以是包含具有分支到另外兩個葉/節點的整數的節點。這是我得到的：在Haskell中創建多態遞歸類型

module Tree (Tree(Empty, Leaf, Node)) where 

data Tree = Empty 
| Leaf Int 
| Node Tree Int Tree 
deriving(Eq, Ord, Show, Read)

這工作正常，但我需要使樹型多態。我嘗試用'a'代替'Int'，但它似乎不起作用。是否有另一個製作這些類型多態的系統？

來源

2010-02-04 benwad

的確，您可以給Tree一個類型參數，如Alexander Poluektov的示例。夠簡單！但爲什麼要在那裏停下我們可以有更多的樂趣。而不是遞歸結構多態數據，您可以使結構多態在遞歸本身！

首先，抽象掉樹對自身的引用，與抽象出Int的引用相同，用新參數t替換遞歸引用。這給我們留下了這個相當含糊的數據結構：

data TNode t a = Empty 
       | Leaf a 
       | Node (t a) a (t a) 
       deriving (Eq, Ord, Show, Read)

這已被更名爲TNode這裏，因爲它是不是一個真正的樹了;只是一個簡單的數據類型。現在，爲了恢復原始遞歸和創建樹，我們擰TNode周圍，飼料它本身：

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read)

現在我們可以使用這個Tree遞歸，但可悲的是，在一些額外的空話的成本，就像這樣：

Tree (Node (Tree Empty) 5 (Tree (Leaf 2)))

那麼，除了額外的打字，你會問這是什麼給我們的？簡單地說，我們已經將基本樹結構與它所包含的數據以及數據構造和處理的方法分開，從而允許我們編寫更通用的函數來處理某個方面。例如，我們可以用額外的數據修飾樹，或者將額外的東西拼接到樹中，而不影響任何通用樹函數。假設我們想給一個名字在每件樹：

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read)

在另一方面，我們可以編寫通用的樹遍歷邏輯：

toList f t = toList' f (f t) [] 
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs) 
      toList' f (Leaf x) xs = x:xs 
      toList' _ Empty xs = xs

給出一個函數來提取當前TNode從遞歸樹，我們可以在任何這樣的結構使用：

treeToList = toList (\(Tree t) -> t) 
nameTreeToList = toList (\(NameTree (_, t)) -> t)

當然，這可能遠遠超過你在找什麼做的，但它只是多少味道不錯多態性和泛型代碼Haskell允許（不鼓勵）程序員創建。

來源

2010-02-04 15:51:38

data Tree a = Empty 
      | Leaf a 
      | Node (Tree a) a (Tree a)

來源

2010-02-04 13:25:14

與更換int是正確的開始，但你還需要與Tree a更換樹的每一次出現（圓括號它在必要時）。 data Tree部分需要a來聲明該樹有一個類型參數，稱爲a。 Node Tree Int Tree需要表示子樹本身的類型爲Tree a而不是其他一些treetype。

來源

2010-02-04 13:25:22 sepp2k

嘗試讀一下關於類型構造函數類。

如果你有一個多態類型取決於某些類型變量，那麼你的類型構造函數必須有一種反映這種類型的變量。

例如，類型構造MyBool中所定義：

data MyBool = False | True

是樣*。也就是說，我的類型構造函數MyBool不採用參數來定義類型。如果我寫的是這樣的：

data MyMaybe a = Just a | Nothing

，那麼該類型的構造MyMaybe有種*->*，也就是說，它需要一個「類型參數」來定義類型。

您可以比較類型構造函數種類如何與數據構造函數類型的工作方式。

數據構造函數True可以是它自己的類型爲MyBool的數據值，不帶任何參數。但數據構造Just是a -> MyMaybe a類型的值，它會操作超過類型的價值創造MyMaybe a類型的其他價值 - 例如像在這個ghci的會議：

> let x = Just 5 
> :t x 
Maybe Int 
> let y = Just 
> :t y 
a -> Maybe a

這是多還是與類型構造函數MyMaybe和MyBool之間的差異較小。鑑於MyBool有種類*，您可以使用類型爲MyBool的值，不帶任何其他類型參數。但是MyMaybe本身並不是一種類型 - 它是一種類型構造函數，它在類型上「操作」以創建另一種類型，即其種類爲* -> *。所以，你不能有MyMaybe類型的東西，但MyMaybe Int型，MyMaybe Bool，MyMaybe [Int]等東西......

如果一個類型是多態的，它需要的那種* -> *至少，但它可能是*->*->*，像：

data MyPair a b = Pair a b

MyPair需要兩個參數類型定義一個類型，像MyPair Int Bool，MyPair Int Int，等...

帶回家的消息是這樣的：因爲值構造函數具有類型簽名，類型構造函數具有親切簽名，並且在規劃新數據類型時必須考慮到這一點。

http://en.wikipedia.org/wiki/Kind_%28type_theory%29

來源

2010-02-04 15:55:32

在Haskell中創建多態遞歸類型

回答

相關問題