在Haskell中使用Bag

Question

我的任務是創建一個Haskell程序，該程序包含一個多態數據類型Bag的定義和一些簡單的函數，比如將一個列表轉換爲一個包並檢查兩個包是否相同。

我的問題是我是Haskell的新手，所以我不確定如何使用手袋。任何人都可以指點我的一些資源的方向與袋？

Answer 1

• 您可以先了解algebraic數據類型。
• 首先嚐試實現一個簡單的代數數據類型，如樹，然後你可以去實現你自己的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