Использование сумки в Haskell

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

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


list functional-programming bag haskell
person Matt Gibson    schedule 18.10.2012    source источник
comment
У вас действительно нет конкретного вопроса, на который кто-то может ответить. Вы знаете, что такое сумка? У вас есть идея, как бы вы реализовали это на другом языке? Начиная оттуда, попробуйте написать простую версию Haskell; затем, если у вас есть конкретные проблемы, измените свой вопрос. Более конкретные вопросы обычно делают SO более полезным.   -  person Tikhon Jelvis    schedule 19.10.2012
comment
Есть библиотеки для сумок. Поиск в Google Haskell Data.Bag — один из способов найти нужный материал.   -  person pigworker    schedule 19.10.2012
comment
Сумка IIRC - это просто мультисет. Разве вы не можете использовать для этого Data.Map?   -  person Satvik    schedule 19.10.2012
comment
Data.MultiSet?   -  person NovaDenizen    schedule 20.10.2012

Ответы (1)


arrow_upward
6
arrow_downward

  • Вы можете начать с чтения об алгебраических типах данных.
  • Сначала попробуйте реализовать простой алгебраический тип данных, такой как дерево, а затем вы можете реализовать свой собственный тип данных Bag. Если у вас возникнут проблемы, вы всегда можете задать их здесь.
  • Если это не домашнее задание, вы можете использовать уже реализованные Bags или использовать 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
person Satvik    schedule 19.10.2012