在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