Использование Bag в Haskell

Question

Мне было поручено создать программу на Haskell, которая содержит определение полиморфного типа данных Bag и несколько простых функций, таких как преобразование списка в пакет и проверка, совпадают ли два пакета.

Моя проблема в том, что я новичок в Haskell, поэтому не знаю, как использовать сумки. Может ли кто-нибудь указать мне на некоторые ресурсы, чтобы сделать с мешками?

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