Haskell中的复杂数据结构

Question

阅读http://learnyouahaskell.com/后我仍然不明白,Haskell中是如何构建复杂的数据结构的.

一个例子:

我有很多地方,每个地点都能够容纳一个项目.每个项目都可以定位在一个位置.位置和项目都有一个名称和一些额外的信息(我把它们留在这里).每个位置和每个项目的名称都是唯一的.

此问题出现在优化问题的上下文中,应该构建一个短传输列表.这意味着,对象只需读取一次,然后就不会被操纵.存在更多类型,它们都通过面向对象设计中的实例字段链接在一起.

我的第一个想法(根据我对面向对象设计的了解)将是:

data Location = Location String Item
data Item = Item String Location

由于没有引用,只有Haskell中的值,我希望这是一个无休止的递归.

data Location = Location String Item
data Item = Item String

通过这种方法,当我只有物品时,我无法获得位置.

我的第二个想法是:

data Location = Location String
data Item = Item String
type LocItems = [(Location, Item)]

好吧,这种方式我必须给出方法,它需要一个位置的项目,两个参数:位置和地图.当它变得越来越复杂时,我最终会得到许多地图.反对这种方法的第二个原因:类型系统不限制仅链接到另一个的位置和项目.地图(或更好的关联列表)可以将一个位置映射到多个项目.

我不明白如何在Haskell中构建这样复杂的结构.

那么如何在Haskell中构建这样的数据结构呢？

Answer 1

由于没有引用,只有Haskell中的值,我希望这是一个无休止的递归.

不过,它有可能:

data Location = Location String Item
data Item     = Item     String Location

locationName (Location s _) = s
getItem      (Location _ i) = i
itemName     (Item s _) = s
getLocation  (Item _ l) = l

getItemNameAtLocation :: Location -> String
getItemNameAtLocation = itemName . getItem

getLocationNameOfItem :: Item -> String
getLocationNameOfItem = locationName . getLocation

mkItemLocation :: ItemName -> LocationName -> (Item, Location)
mkItemLocation i l = let it = Item i $ Location l $ it in (it, getLocation it)

main = do
        let it   = Item "Toothbrush" $ Location "Bathroom" $ it
            loc1 = getLocation it
            loc2 = Location "Quantum bathroom" $ it
        print $ getLocationNameOfItem it
        print $ getItemNameAtLocation loc1
        print $ getItemNameAtLocation loc2
        print $ locationName loc2

但是,这并没有强制执行您的规则,因为现在有两个声称拥有牙刷的位置.如果不导出构造函数,仍可以强制执行此操作:

module ItemLocation (mkItemLocation, Item, Location,
                     getLocation, locationName,
                     getItem, itemName) where

-- see above for Item, Location and others

type ItemName     = String
type LocationName = String

mkItemLocation :: ItemName -> LocationName -> (Item, Location)
mkItemLocation i l = let it = Item i $ Location l $ it in (it, getLocation it)

main = do
    let (it, loc) = mkItemLocation "Toothbrush" "Bathroom"
        print $ getLocationNameOfItem it
        print $ getItemNameAtLocation loc

但是,没有什么能阻止你使用mkItemLocation "Toothbrush" "Another quantum room".但在这一点上,你还没有说过如何识别单个物品或位置(可能是通过名称).

请注意,您可能想要使用data Location = Location String (Maybe Item).话虽如此,但您不清楚自己想要如何操纵某个位置或项目,以及这些操作应该如何反映您所在位置的其他位置.根据您实际想要做的事情,您最终可能会State与两个人一起使用Map.

好的,上面只是告诉你如何处理递归数据类型.一个人如何真正解决你的问题？让我们尝试构建一个接口:

data Magic

-- | initial empty magic
empty :: Magic

-- | turns the magic type into a list of (Location, Item)
--   every Location and Item is unique
assoc  :: Magic -> [(Location, Item)]


-- | adds the given Location and Item and puts them into relation
--   If either Location or Item already exist, they're going to be
--  removed (together with their counterpart) beforehand
insert :: Location -> Item -> Magic -> Magic

现在,这可以概括.而不是Location和Item,我们可以支持a和b.我们获得:

module DualMap (DualMap, empty, assocLeft, 
                assocRight, flipMap, insert, 
                removeLeft, removeRight) where

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

data DualMap a b = DualMap (Map a b) (Map b a) deriving (Eq, Show)

empty :: DualMap a b
empty = DualMap (M.empty) (M.empty)

flipMap :: DualMap a b -> DualMap b a
flipMap (DualMap ls rs) = DualMap rs ls

assocLeft :: DualMap a b -> [(a, b)]
assocLeft (DualMap ls _) = M.toList ls

assocRight :: DualMap a b -> [(b, a)]
assocRight = assocLeft . flipMap

insert :: (Ord a, Ord b) => a -> b -> DualMap a b -> DualMap a b
insert loc item m = DualMap (M.insert loc item ls) (M.insert item loc is)
  where (DualMap ls is) = removeLeft loc m

removeLeft :: (Ord a, Ord b) => a -> DualMap a b -> DualMap a b
removeLeft l m@(DualMap ls rs) = 
  case M.lookup l ls of
    Just r  -> DualMap (M.delete l ls) (M.delete r rs)
    Nothing -> m

removeRight :: (Ord a, Ord b) => b -> DualMap a b -> DualMap a b
removeRight r m@(DualMap ls rs) = 
  case M.lookup r rs of
    Just l  -> DualMap (M.delete l ls) (M.delete r rs)
    Nothing -> m

请注意,您不应导出DataMap构造函数.removeRight并removeLeft确保如果您取出左值,也会删除正确的值.请注意,在我们的情况下,使用其中一个就足够了,因为insert两个值都是对称存储的.

这需要你有有效Ord的两个实例Location和Item,应基于其独特的属性(在这种情况下他们的名字).如果您已经碰巧拥有一个不使用该名称的实例Ord或Eq实例,请使用newtype包含适当实例的包装器.