How to efficiently model relationships in Haskell with mutable data

Question

I have a problem like this . However, it includes many updates, and I'm not sure if the IxSet solution is a solution.

I mainly write an application to optimize the layout of the repository. No database or anything else; it is just data to manipulate and create the file at the end. The warehouse is made of shelves of different sizes; shelves contain boxes of different sizes; and the goal is to find a better location (or at least a good one) where to put the boxes so that they all fit.

Base model (doesn't really matter):

data Dimension = Dimension {length::Double, width::Double, height::Double} data Box = Box {boxId :: Int, boxDim:: Dimension } data Shelf = Shelf {shelfId :: Int, shelfDim :: Dimension, postion :: ... } 

Now the first problem is that there is a shelf schedule. Some shelves go back to back. I need to know this because you can adjust the depth of one shelf (which change the back of the rear shelf). I also need to know the opposite shelf and the next.

What is the most efficient way to simulate this?

My first thought:

 data Shelf = Shelf { ... , backShelf :: Maybe Shelf , frontShelf :: Maybe Shelf , nextShelf :: Maybe Shelf } 

Now the data is immutable in Haskell, so how can I update Shelf ? I mean, imagine that I have a Shelf list; if I modify it, do I need to update all copies of it?

My second thought is to use identifiers instead:

 newtype ShelfId = Int data Shelf = Shelf { ..., backShelfId :: Maybe ShelfId ... } 

Or use external graphics? Sort of

  back, front, next :: [(shelfId, shelfId)] 

The second problem is how to simulate the fact that the field belongs to the shelf.

Possible approaches that come to mind:

  data Box = Box { ..., shelf :: Shelf } 

or

  data Box = Box { ..., shelfId :: Maybe ShelfId } 

or

  data Shelf = Shelf { ..., boxes = [Box] } 

or

  data Shelf = Shelf { ..., boxIds = [BoxId] } 

External graph

  boxToShelf :: [(BoxId, ShelfId)] 

In addition, as I said, operations include many updates; I can add boxes one at a time to each shelf, which can be really inefficient with immutable data.

Another solution I thought would use STRef or the equivalent:

 data Box = { ..., shelf :: STRef Shelf } 

It seems like using a pointer, so there is probably no good idea.

Update

This is not an XY problem, nor a problem with the toy. This is a real world application for a real warehouse (about 100 shelves and 3,000 boxes). It should be able to draw and load existing data (boxes and their location). Optimization is only a small part of it and is likely to be semi-automatic.

So my question is about representing the relationship between mutable objects, not the main combinatorial problems.

Answer 1

Knowing how the optimization algorithm works will help.

At the heart of the problem is a data structure that tracks which boxes are on the shelves (and vice versa). Let me call it "configuration."

The combinatorial search algorithm creates new configurations from the old ones as it explores the space of all possible configurations. There are several configurations at any given time - one for each stack frame of a recursive search.

On the other hand, an algorithm such as local search has only one (global) data structure, which it mutates using heuristics or randomness, until it finds a good enough solution.

What is your algorithm?

Update: note that there cannot be a single view that works for all of your use cases. To store data you only need a card from the shelf to the boxes. For display, it may also be convenient for you to have a reverse map (fields → shelves.) And for optimization, you may need to model the problem with mutable arrays for an effective update.

Update 2: I would try an approach with a preliminary data structure and see how well it works.

 type BoxId = Int type ShelfId = Int data Shelf = Shelf { ... just the dimensions of the shelf ... } data Box = Box { ... just the dimensions of the box ... } data Configuration = { shelves :: IntMap Shelf, -- map from shelf id to shelf characterstics boxes :: IntMap Box, -- map from box id to box characteristics boxesForShelf :: IntMap [BoxId], -- map from shelf id to box ids shelfForBox :: IntMap ShelfId -- map from box id to shelf id (or 0) } 

Then write down this function:

 assignBox :: BoxId -> ShelfId -> Configuration -> Configuration 

For efficiency, you can also write something like:

 assignBoxes :: [BoxId] -> ShelfId -> Configuration -> Configuration 

and feel free to write other optimized features for other bulk configuration updates that occur in your use cases.

It may be convenient for you to have BoxId in the Box structure (and the same for the ShelfId / Shelf structure) ... but you don't need to. But the relationship between boxes and shelves is better handled by separate cards.

I defined boxesForShelf as IntMap [BoxId] simply because it seems that there will be only a small number of boxes on each shelf. Perhaps this is not true.

Hope this helps.

Answer 2

Why not use persistent ? I compiled a sample application in the form of a cabal package for use here https://github.com/gxtaillon/Shelves .

Constantly follows the guidelines for type safety and brevity, declarative syntax. Some other nice features:

• Database agnostic. There is first-class support for PostgreSQL, SQLite, MySQL, and MongoDB with experimental support for Redis.
• Convenient data modeling. Persistent lets you model relationships and use them in a safe way. The standard secure default API does not support federation, which allows for wider storage. Connections and other SQL functionality can be achieved using the original SQL level (with very little security type). An additional library, Esqueleto, is built on top of the Permanent Data Model, adding secure connection types and SQL functionality.
• Auto Database Migration

Once you know what data needs to be saved, you will have a working database and you can start working on this optimization algorithm without worrying about wheel performance, scalability or rethinking.

models - File containing the schema definition of your database

 Shelf hrId Text length Double width Double height Double UniqueShelf hrId deriving Show Box hrId Text length Double width Double height Double UniqueBox hrId deriving Show Storage shelfId ShelfId boxId BoxId UniqueStorage shelfId boxId deriving Show 

Model.hs - where you import models and generate the corresponding types

 {-# LANGUAGE EmptyDataDecls #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE GADTs #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE QuasiQuotes #-} {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE TypeFamilies #-} module Model where import Database.Persist.Quasi import Database.Persist.TH import ClassyPrelude share [mkPersist sqlSettings, mkMigrate "migrateAll"] $(persistFileWith upperCaseSettings "models") 

Main.hs - sample application

 {-# LANGUAGE OverloadedStrings #-} module Main where import Model import Control.Monad.IO.Class (liftIO) import Database.Persist.Sqlite hiding (master, Connection) main :: IO () main = runSqlite ":memory:" $ do runMigration migrateAll myShelfId <- insert $ Shelf "ABCD.123" 10.0 1.5 2.0 thatBoxId <- insert $ Box "ZXY.098" 1.0 1.0 1.0 thisBoxId <- insert $ Box "ZXY.099" 2.0 1.0 1.0 _ <- insert $ Storage myShelfId thatBoxId _ <- insert $ Storage myShelfId thisBoxId myStorage <- selectList [StorageShelfId ==. myShelfId] [] liftIO $ print (myStorage :: [Entity Storage]) update myShelfId [ShelfWidth +=. 0.5] thatBox <- get thatBoxId liftIO $ print (thatBox :: Maybe Box) myShelf <- get myShelfId liftIO $ print (myShelf :: Maybe Shelf) 

To print something along these lines:

 Migrating: [...] [Entity {entityKey = StorageKey {unStorageKey = SqlBackendKey {unSqlBackendKey = 1}}, entityVal = Storage {storageShelfId = ShelfKey {unShelfKey = SqlBackendKey {unSqlBackendKey = 1}}, storageBoxId = BoxKey {unBoxKey = SqlBackendKey {unSqlBackendKey = 1}}}},Entity {entityKey = StorageKey {unStorageKey = SqlBackendKey {unSqlBackendKey = 2}}, entityVal = Storage {storageShelfId = ShelfKey {unShelfKey = SqlBackendKey {unSqlBackendKey = 1}}, storageBoxId = BoxKey {unBoxKey = SqlBackendKey {unSqlBackendKey = 2}}}}] Just (Box {boxHrId = "ZXY.098", boxLength = 1.0, boxWidth = 1.0, boxHeight = 1.0}) Just (Shelf {shelfHrId = "ABCD.123", shelfLength = 10.0, shelfWidth = 2.0, shelfHeight = 2.0}) 

Answer 3

So, let's take the simplest case: the rectangles that need to hold some rectangles, without the possibility of stacking. Then we can provide a new “shelf” when we put the rectangle in the old “shelf”:

 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 

Perhaps the most effective is to search for depth at the beginning, starting with the widest fields:

 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) 

Now, how can we put, say, two shelves one above the other with a total height H, but independent heights otherwise? We can write them together in our list of shelves:

 vert_shelves other_shelves hw = [Shelf w (h - i) : Shelf wi : other_shelves | i <- [0..h - 1]] 

If you need boxes-on-boxes, you will start giving two rectangles from fitsOn (above and next to it) and try to combine the “above” window into any other fields that come from the same shelf, and the same elevation, which will take a little redo this thing. You may also need an unlimited number of boxes, which would be a bit complicated without overwriting how these bytes will be transmitted.

Answer 4

It looks like you need a relational database management system (RDBMS). If you don’t want to implement one in Haskell (which you probably don’t know and don’t want), I suggest you use the excellent, free Postgres and communicate with it from Haskell in the form and style using Opaleye . [Disclaimer: I wrote Opaleye.]