在Haskell中创建多态递归类型

Question

我正在尝试在Haskell中创建一个Tree类型.我已经使用这个简单的数据构造函数来存储一个树,其中每个节点可以是空的,是包含整数的叶子,或者是包含一个整数的节点,该整数具有到另外两个叶子/节点的分支.这是我得到的:

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

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

这工作正常,但我需要使树类型多态.我试过用'a'代替'Int',但它似乎不起作用.是否有另一个系统使这些类型多态？

Answer 1

实际上,你可以给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允许程序员创建多少多态和通用代码(nay,鼓励).

Answer 2

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