Haskell集合数据类型/数据结构

Question

我想做的是在Haskell中创建一个类型集来表示通用(多态)集，例如{1,'x',"aasdf",Phi}

首先我要澄清在我的程序中我想把(空集)看作属于所有集合

的东西

这是我的代码

data Set a b= Phi | Cons a (Set a b)
deriving (Show,Eq,Ord)

isMember Phi _ = True
isMember _ Phi = False
isMember x (Cons a b) = if x==a
               then True
               else isMember x b

我面临几个问题:

1. 我想让isMember类型为

   isMember :: Eq a => a -> Set a b -> Bool
   

   但是根据我的代码，它是

   isMember :: Eq a => Set a b -> Set (Set a b) c -> Bool
   

2. 如果我有一组不同的时间==操作员不正常工作，所以我需要一些帮助，请:D

Answer 1

关于你的输入错误，问题看起来像我的第一个子句:

isMember Phi _ = True

这是一个奇怪的子句，因为Phi是一个完整的集合，而不是一个集合元素。只需删除它，就会得到一个您所期望的类型的函数。

注意Set类型从不使用它的第二个类型参数，所以它可以写成

data Set a = Phi | Cons a (Set a)

…在这种情况下，你应该只使用[a]，因为它是同构的，并且已经为使用和滥用它们编写了大量的函数。

最后，你要求能够放入不同类型的东西。简单地说，Haskell并不是这样的。这一切都是关于在编译时确切地知道一个东西是什么类型的，这与您所建议的并不真正兼容。实际上有一些方法可以做到这一点;然而，我强烈建议在尝试将键取下之前更熟悉Haskell的特定类型捆绑品牌。

Answer 2

A)这样做几乎总是不是你真正想要的。

从嵌入动态类型(Dynamic)到使用非常复杂的类型(HList)，有多种方法可以做到这一点。

C)这里有一个描述一些方法和问题的页面:http://www.haskell.org/haskellwiki/Heterogenous_collections

D)如果你真的要这样做，我建议HList: http://homepages.cwi.nl/~ralf/HList/

E)但是，如果你开始看文档/HList论文，发现自己绝望地困惑，回到动态解决方案(或者更好的是，重新思考为什么你需要这个)，一旦你对Haskell更加熟悉，再回到HLists。

Answer 3

您尝试做的事情非常困难，因为Haskell默认情况下不存储任何类型信息。两个非常有用的模块是Data.Typeable和Data.Dynamic。它们支持存储单态(!)类型和支持动态单态类型。

我以前没有尝试过这样的代码，但是我有一些想法来完成:

1. 集合中的每个元素是下列元素的三倍(四倍):

   • 存储数据类型
   的TypeRep
   • 值本身，强制为Any。
   • 一个比较函数(你只能使用单态值，你必须以某种方式存储上下文)
   • 类似，一个函数来show的值。

2. 你的集合实际上有两个维度，第一个是TypeRep的树，然后是一个值列表。

3. 每当你插入一个值，你强制它到一个Any和存储所有需要的东西与它在一起，如(1)所解释的，并把它放在正确的位置，如(2)。

4. 当您想要查找一个元素时，您生成它的TypeRep并查找正确类型的子树。然后，您只需将每个子元素与您想要查找的值进行比较。

那只是一些随机的想法。我想实际上使用Dynamic要容易得多。