list - 在 Haskell 中使用 Bag

Question

我的任务是创建一个 Haskell 程序，该程序包含多态数据类型 Bag 的定义和一些简单的函数，例如将列表转换为包并检查两个包是否相同。

我的问题是我是 Haskell 的新手，所以我不确定如何使用 Bags。谁能指出我与包有关的一些资源的方向？

Answer 1

• 您可以从阅读代数数据类型开始。
• 首先尝试实现一个简单的代数数据类型，比如树，然后你可以去实现你自己的 Bag 数据类型。如果您有任何问题，您可以随时在这里提问。
• 如果这不是家庭作业，那么您可以使用已经实现的包或使用Data.Map来实现相同的包。

我已经给出了Data.Map用于比较您的实现的定义，我想您将使用自己的代数数据类型编写它。

import qualified Data.Map as M
import Data.Map (Map)

newtype Bag a = Bag (Map a Int)
    deriving (Show,Eq)

empty :: Bag a
empty = Bag $ M.empty

singleton :: a -> Bag a
singleton a = Bag $ M.singleton a 1

fromList :: (Ord a) => [a] -> Bag a
fromList = foldl f empty
    where
        f (Bag map) x = Bag $ M.insertWith (+) x 1 map

toList :: Bag a -> [a]
toList (Bag m) = concatMap f $ M.toList m
    where f (a,b) = replicate b a

我已经定义了一些非常基本的功能，但是你可以做你要求的事情以及更多，比如

*Main> let x = fromList [1,2,3,2,2,1]
*Main> x
Bag (fromList [(1,2),(2,3),(3,1)])
*Main> let y = fromList [1,1,2,2,2,3]
*Main> y
Bag (fromList [(1,2),(2,3),(3,1)])
*Main> x==y
True