我有类似的问题本.但是,它涉及很多更新,我不确定IxSet是否是解决方案.
基本上我正在编写一个应用程序来优化仓库布局.没有数据库或任何东西; 它只是简单的数据来操作并在最后生成一个文件.仓库由不同尺寸的货架制成; 货架包含不同尺寸的箱子; 并且目标是找到最好的安排(或者至少是一个好的安排),在哪里放置盒子以便它们都适合.
基本模型(实际上并不重要)是:
data Dimension = Dimension {length::Double, width::Double, height::Double}
data Box = Box {boxId :: Int, boxDim:: Dimension }
data Shelf = Shelf {shelfId :: Int, shelfDim :: Dimension, postion :: ... }
现在,第一个问题是有一个货架图.有些架子背靠背.我需要知道它,因为可以调整一个架子的深度(以相反的方式修改后架).我还需要知道对面的架子和下一个架子.
对此进行建模的最有效方法是什么？
我的第一个想法是:
data Shelf = Shelf { ... , backShelf :: Maybe Shelf
, frontShelf :: Maybe Shelf
, nextShelf :: Maybe Shelf
}
现在,数据在Haskell中是不可变的,那么如何更新Shelf？我的意思是,想象一下我有一份清单Shelf; 如果我修改一个,那么我需要更新它的所有副本？
我的第二个想法是使用id代替:
newtype ShelfId = Int
data Shelf = Shelf { ..., backShelfId :: Maybe ShelfId ... }
或者我应该使用外部图表？就像是
back, front, next :: [(shelfId, shelfId)]
第二个问题如何模拟一个盒子属于一个架子的事实.
想到的可能方法是:
data Box = Box { ..., shelf :: Shelf }
要么
data Box = Box { ..., shelfId :: Maybe ShelfId }
要么
data Shelf = Shelf { ..., boxes = [Box] }
要么
data Shelf = Shelf { ..., boxIds = [BoxId] }
外部图表
boxToShelf :: [(BoxId, ShelfId)]
另外,正如我所说,这些操作涉及大量更新; 我可能会逐个向每个架子添加盒子,这对于不可变数据来说效率非常低.
我认为另一种解决方案是使用STRef或等效:
data Box = { ..., shelf :: STRef Shelf }
感觉就像使用指针一样,所以这可能不是一个好主意.
这不是XY问题,也不是玩具问题.这是一个真正的仓库应用程序(100个货架和3000个盒子).它需要能够绘制和加载现有数据(框及其位置).优化只是其中的一小部分,可能是半手动的.
所以我的问题是关于表示可变对象之间的关系而不是基本的组合问题.
因此，让我们采取最简单的情况：需要容纳一些矩形的矩形，并且不允许堆叠。然后当我们在旧的“架子”中放置一个矩形时，我们可以提供一个新的“架子”：
newtype Box = Box Int Int Int deriving (Eq, Ord, Show)
newtype Shelf = Shelf Int Int Int deriving Show
type ShelfID = Int
type BoxID = Int
type ShelfBox = (ShelfID, BoxID)
fitsOn :: (Int, Box) -> (Int, Shelf) -> Maybe (ShelfID, Shelf)
fitsOn (bid, Box bw bh) (sid, Shelf sw sh)
| bw <= sw && bh <= sh = Just (sid, Shelf (sw - bw) sh)
| otherwise = Nothing
从最宽的框开始进行深度优先搜索可能是最有效的：
import Data.IntMap.Strict (IntMap, (!))
import Data.IntMap.Strict as IntMap
import Data.List (sort)
collect (mx : mxs) = case mx of
Just x -> x : collect mxs
Nothing -> collect mxs
-- need to feed something like `IntMap.fromList $ zip [0..] $ sort bs` to `boxes`:
search :: IntMap Box -> IntMap Shelf -> [ShelfBox] -> Maybe [ShelfBox]
search boxes shelves acc
| IntMap.empty boxes = Just acc
| otherwise = case collect $ (map process) options of
[] -> Nothing
(x : xs) -> Just x
where (box, boxes') = IntMap.deleteFindMax boxes
options = collect [box `fitsOn` shelf | shelf <- IntMap.toList shelves]
process (sid, s') = search boxes' (IntMap.insert sid s') ((sid, fst box) : acc)
现在我们怎样才能将两个架子放在一起，总高度为 H，但其他高度却是独立的？我们可以将两者一起写到我们的书架列表中：
vert_shelves other_shelves h w = [Shelf w (h - i) : Shelf w i : other_shelves | i <- [0..h - 1]]
如果您想要盒子上的盒子，您将开始从fitsOn（上方和旁边）生成两个矩形，并尝试将“上方”盒子聚合到来自同一架子且具有相同高度的任何其他盒子中，这将重新设计一下这个东西。您可能还需要无限数量的盒子，如果不重写这些可能的传递方式，这会有点棘手。