从列表创建包/multiset

Question

这必须是超级简单的，我错过了一些东西。我无论如何也想不到该怎么做。我需要从列表中创建一个包。我试过了：

ins n [] = [(n,1)]
ins n ((x,y):xys)
  |n == x    = (x, y + 1):xys
  |otherwise = (x,y): ins x xys

fromList [] = []
fromList (x:xs) = ins x [] : bag xs

这显然不像预期的那样工作，递归在这里对我不利。insert函数确实可以工作，但是我不知道如何继续添加到相同的列表中，而不是我正在做的事情

编辑:可能应该说得更具体些，抱歉。Bag将是数据类型，其中Bag a = [(element, number of occurrences in list)]可能也称为multiset。因此列表2,2,3,4,2,3将变为(2,3)，(3,2)，(4,1)

我对Haskell和一般的编程都是非常陌生的，所以我再次为我对它的抽象而道歉。

Answer 1

你就快成功了。你可能想要的是：

fromList [] = []
fromList (x:xs) = ins x (fromList xs)

如果你看一下类型，就会更容易看出哪里出了问题。在固定版本中：

ins :: (Eq a, Num b) => a -> [(a,b)] -> [(a,b)]
fromList :: (Eq a, Num b) => [a] -> [(a,b)]

在fromList的原始版本中，您应该会得到一个错误，因为bag是未定义的；但假设您的意思是：

fromList [] = []
fromList (x:xs) = ins x [] : fromList xs

推断的类型为：

fromList :: (Eq a, Num b) => [a] -> [[(a,b)]]

它返回的不是袋子类型[(a,b)]，而是袋子列表[[(a,b)]]。

这个版本实际上所做的是将每个元素包装成一个单独的包；基本上与map (\ x -> ins x [])相同。