--- title: "Lazy I/O and graphs: Winterfell to King's Landing" description: Finding the shortest path in a lazily loaded infinite graph tags: haskell --- Introduction ============ This post is about Haskell, and lazy I/O in particular. It is a bit longer than usual, so I will start with a high-level overview of what you can expect: - We talk about how we can represent graphs in a _"shallow embedding"_. This means we will not use a dedicated `Graph` type and rather represent edges by directly referencing other Haskell values. - This is a fairly good match when we want to encode infinite [^infinite] graphs. When dealing with infinite graphs, there is no need to "reify" the graph and enumerate all the nodes and egdes -- this would be futile anyway. - We discuss a Haskell implementation of shortest path search in a weighted graph that works on these infinite graphs and that has good performance characteristics. - We show how we can implement lazy I/O to model infinite graphs as pure values in Haskell, in a way that only the "necessary" parts of the graph are loaded from a database. This is done using the `unsafeInterleaveIO` primitive. - Finally, we discuss the disadvantages of this approach as well, and we review some of common problems associated with lazy I/O. [^infinite]: In this blogpost, I frequently talk about _"infinite graphs"_. Of course most of these examples are not truly infinite, but we can consider examples that do not fit in memory completely, and in that way we can regard them as _"infinite for practical purposes"_. Let's get to it! As usual, this is a [literate Haskell] file, which means that you can just load this blogpost into GHCi and play with it. You can find the raw `.lhs` file [here](https://raw.githubusercontent.com/jaspervdj/jaspervdj/master/posts/2017-01-17-lazy-io-graphs.lhs). [literate Haskell]: https://wiki.haskell.org/Literate_programming > {-# LANGUAGE OverloadedStrings #-} > {-# LANGUAGE ScopedTypeVariables #-} > import Control.Concurrent.MVar (MVar, modifyMVar, newMVar) > import Control.Monad (forM_, unless) > import Control.Monad.State (State, gets, modify, runState) > import Data.Hashable (Hashable) > import qualified Data.HashMap.Strict as HMS > import qualified Data.HashPSQ as HashPSQ > import Data.Monoid ((<>)) > import qualified Data.Text as T > import qualified Data.Text.IO as T > import qualified Database.SQLite.Simple as SQLite > import qualified System.IO.Unsafe as IO The problem at hand =================== ![](/images/2017-01-17-throne.jpg) As an example problem, we will look at finding the shortest path between cities in [Westeros], the fictional location where the [A Song of Ice and Fire] novels (and HBO's [Game of Thrones]) take place. [Westeros]: https://en.wikipedia.org/wiki/World_of_A_Song_of_Ice_and_Fire [A Song of Ice and Fire]: https://en.wikipedia.org/wiki/A_Song_of_Ice_and_Fire [Game of Thrones]: https://en.wikipedia.org/wiki/A_Game_of_Thrones We model the different cities in a straightforward way. In addition to a unique ID used to identify them, they also have a name, a position (_X,Y_ coordinates) and a list of reachable cities, with an associated time (in days) it takes to travel there. This travel time, also referred to as the _cost_, is not necessarily deducable from the sets of _X,Y_ coordinates: some roads are faster than others. > type CityId = T.Text > data City = City > { cityId :: CityId > , cityName :: T.Text > , cityPos :: (Double, Double) > , cityNeighbours :: [(Double, City)] > } Having direct access to the neighbouring cities, instead of having to go through `CityId`s both has advantages and disadvantages. On one hand, updating these values becomes cumbersome at best, and impossible at worst. If we wanted to change a city's name, we would have to traverse all other cities to update possible references to the changed city. On the other hand, it makes access more convenient (and faster!). Since we want a read-only view on the data, it works well in this case. Getting the data ================ We will be using data extracted from [got.show], conveniently licensed under a Creative Commons license. You can find the complete SQL dump [here](/files/2017-01-17-got.sql.txt). The schema of the database should not be too surprising: ~~~~~{.sql} CREATE TABLE cities ( id text PRIMARY KEY NOT NULL, name text NOT NULL, x float NOT NULL, y float NOT NULL ); CREATE TABLE roads ( origin text NOT NULL, destination text NOT NULL, cost float NOT NULL, PRIMARY KEY (origin, destination) ); CREATE INDEX roads_origin ON roads (origin); ~~~~~ [got.show]: https://got.show/ The road costs have been generated by multiplying the actual distances with a random number uniformly chosen between `0.6` and `1.4`. Cities have been (bidirectionally) connected to at least four closest neighbours. This ensures that every city is reachable. We will use [sqlite] in our example because there is almost no setup involved. You can load this database by issueing: [sqlite]: http://sqlite.org/ ~~~~~{.sh} curl -L jaspervdj.be/files/2017-01-17-got.sql.txt | sqlite3 got.db ~~~~~ But instead of considering the whole database (which we'll get to later), let's construct a simple example in Haskell so we can demonstrate the interface a bit. We can use a `let` to create bindings that refer to one another easily. > test01 :: IO () > test01 = do > let winterfell = City "wtf" "Winterfell" (-105, 78) > [(13, moatCailin), (12, whiteHarbor)] > whiteHarbor = City "wih" "White Harbor" (-96, 74) > [(15, braavos), (12, winterfell)] > moatCailin = City "mtc" "Moat Cailin" (-104, 72) > [(20, crossroads), (13, winterfell)] > braavos = City "brv" "Braavos" (-43, 67) > [(17, kingsLanding), (15, whiteHarbor)] > crossroads = City "crs" "Crossroads Inn" (-94, 58) > [(7, kingsLanding), (20, crossroads)] > kingsLanding = City "kgl" "King's Landing" (-84, 45) > [(7, crossroads), (17, kingsLanding)] > > printSolution $ > shortestPath cityId cityNeighbours winterfell kingsLanding ![Illustration of test01](/images/2017-01-17-test-01-map.png) `printSolution` is defined as: > printSolution :: Maybe (Double, [City]) -> IO () > printSolution Nothing = T.putStrLn "No solution found" > printSolution (Just (cost, path)) = T.putStrLn $ > "cost: " <> T.pack (show cost) <> > ", path: " <> T.intercalate " -> " (map cityName path) We get exactly what we expect in `GHCi`: *Main> test01 cost: 40.0, path: Winterfell -> Moat Cailin -> Crossroads Inn -> King's Landing So far so good! Now let's dig in to how `shortestPath` works. The Shortest Path algorithm =========================== The following algorithm is known as _Uniform Cost Search_. It is a variant of [Dijkstra's graph search algorithm] that is able to work with infinite graphs (or graphs that do not fit in memory anyway). It returns the shortest path between a known start and goal in a weighted directed graph. [Dijkstra's graph search algorithm]: https://en.wikipedia.org/wiki/Dijkstra's_algorithm Because this algorithm attempts to solve the problem the right way, including keeping back references, it is not simple. Therefore, if you are only interested in the part about lazy I/O, feel free to skip to [this section] and return to the algorithm later. [this section]: #interlude-a-very-simple-cache ![](/images/2017-01-17-bran.jpg) We have two auxiliary datatypes. `BackRef` is a wrapper around a node and the previous node on the shortest path to the former node. Keeping these references around is necessary to iterate a list describing the entire path at the end. > data BackRef node = BackRef {brNode :: node, brPrev :: node} We will be using a `State` monad to implement the shortest path algorithm. This is our state: > data SearchState node key cost = SearchState > { ssQueue :: HashPSQ.HashPSQ key cost (BackRef node) > , ssBackRefs :: HMS.HashMap key node > } In our state, we have: - A priority queue of nodes we will visit next in `ssQueue`, including back references. Using a priority queue will let us grab the next node with the lowest associated cost in a trivial way. - Secondly, we have the `ssBackRefs` map. That one serves two purposes: to keep track of which nodes we have already explored (the keys in the map), and to keep the back references of those locations (the values in the map). These two datatypes are only used internally in the `shortestPath` function. Ideally, we would be able to put them in the `where` clause, but that is not possible in Haskell. Instead of declaring a `Node` typeclass (possibly with [associated types] for the key and cost types), I decided to go with simple higher-order functions. We only need two of those function arguments after all: a function to give you a node's key (`nodeKey`) and a function to get the node's neighbours and associated costs (`nodeNeighbours`). [associated types]: https://wiki.haskell.org/GHC/Type_families#An_associated_type_synonym_example > shortestPath > :: forall node key cost. > (Ord key, Hashable key, Ord cost, Num cost) > => (node -> key) > -> (node -> [(cost, node)]) > -> node > -> node > -> Maybe (cost, [node]) > shortestPath nodeKey nodeNeighbours start goal = We start by creating an initial `SearchState` for our algorithm. Our initial queue holds one item (implying that we need explore the `start`) and our initial back references map is empty (we haven't explored anything yet). > let startbr = BackRef start start > queue0 = HashPSQ.singleton (nodeKey start) 0 startbr > backRefs0 = HMS.empty > searchState0 = SearchState queue0 backRefs0 `walk` is the main body of the shortest path search. We call that and if we found a shortest path, we return its cost together with the path which we can reconstruct from the back references (`followBackRefs`). > (mbCost, searchState1) = runState walk searchState0 in > case mbCost of > Nothing -> Nothing > Just cost -> Just > (cost, followBackRefs (ssBackRefs searchState1)) > where Now, we have a bunch of functions that are used within the algorithm. The first one, `walk`, is the main body. We start by exploring the next node in the queue. By construction, this is _always_ a node we haven't explored before. If this node is the goal, we're done. Otherwise, we check the node's neighbours and update the queue with those neighbours. Then, we recursively call `walk`. > walk :: State (SearchState node key cost) (Maybe cost) > walk = do > mbNode <- exploreNextNode > case mbNode of > Nothing -> return Nothing > Just (cost, curr) > | nodeKey curr == nodeKey goal -> > return (Just cost) > | otherwise -> do > forM_ (nodeNeighbours curr) $ \(c, next) -> > updateQueue (cost + c) (BackRef next curr) > walk Exploring the next node is fairly easy to implement using a priority queue: we simply need to pop the element with the minimal priority (cost) using `minView`. We also need indicate that we reached this node and save the back reference by inserting that info into `ssBackRefs`. > exploreNextNode > :: State (SearchState node key cost) (Maybe (cost, node)) > exploreNextNode = do > queue0 <- gets ssQueue > case HashPSQ.minView queue0 of > Nothing -> return Nothing > Just (_, cost, BackRef curr prev, queue1) -> do > modify $ \ss -> ss > { ssQueue = queue1 > , ssBackRefs = > HMS.insert (nodeKey curr) prev (ssBackRefs ss) > } > return $ Just (cost, curr) `updateQueue` is called as new neighbours are discovered. We are careful about adding new nodes to the queue: 1. If we have already explored this neighbour, we don't need to add it. This is done by checking if the neighbour key is in `ssBackRefs`. 2. If the neighbour is already present in the queue with a lower priority (cost), we don't need to add it, since we want the _shortest_ path. This is taken care of by the utility `insertIfLowerPrio`, which is defined below. > updateQueue > :: cost -> BackRef node -> State (SearchState node key cost) () > updateQueue cost backRef = do > let node = brNode backRef > explored <- gets ssBackRefs > unless (nodeKey node `HMS.member` explored) $ modify $ \ss -> ss > { ssQueue = insertIfLowerPrio > (nodeKey node) cost backRef (ssQueue ss) > } If the algorithm finishes, we have found the lowest cost from the start to the goal, but we don't have the path ready. We need to reconstruct this by following the back references we saved earlier. `followBackRefs` does that for us. It recursively looks up nodes in the map, constructing the path in the accumulator `acc` on the way, until we reach the start. > followBackRefs :: HMS.HashMap key node -> [node] > followBackRefs paths = go [goal] goal > where > go acc node0 = case HMS.lookup (nodeKey node0) paths of > Nothing -> acc > Just node1 -> > if nodeKey node1 == nodeKey start > then start : acc > else go (node1 : acc) node1 That's it! The only utility left is the `insertIfLowerPrio` function. Fortunately, we can easily define this using the `alter` function from the [psqueues] package. That function allows us to change a key's associated value and priority. It also allows to return an additional result, but we don't need that, so we just use `()` there. [psqueues]: https://hackage.haskell.org/package/psqueues > insertIfLowerPrio > :: (Hashable k, Ord p, Ord k) > => k -> p -> v -> HashPSQ.HashPSQ k p v -> HashPSQ.HashPSQ k p v > insertIfLowerPrio key prio val = snd . HashPSQ.alter > (\mbOldVal -> case mbOldVal of > Just (oldPrio, _) > | prio < oldPrio -> ((), Just (prio, val)) > | otherwise -> ((), mbOldVal) > Nothing -> ((), Just (prio, val))) > key Interlude: A (very) simple cache ================================ ![](/images/2017-01-17-ghost.jpg) Lazy I/O will guarantee that we only load the nodes in the graph when necessary. However, since we know that the nodes in the graph do not change over time, we can build an additional cache around it. That way, we can also guarantee that we only load every node once. Implementing such a cache is very simple in Haskell. We can simply use an `MVar`, that will even take care of blocking [^stripe] when we have concurrent access to the cache (assuming that is what we want). [^stripe]: While blocking is good in this case, it might hurt performance when running in a concurrent environment. A good solution to that would be to stripe the `MVar`s based on the keys, but that is beyond the scope of this blogpost. If you are interested in the subject, I talk about it a bit [here](/posts/2015-02-24-lru-cache.html#a-striped-cache). > type Cache k v = MVar (HMS.HashMap k v) > newCache :: IO (Cache k v) > newCache = newMVar HMS.empty > cached :: (Hashable k, Ord k) => Cache k v -> k -> IO v -> IO v > cached mvar k iov = modifyMVar mvar $ \cache -> do > case HMS.lookup k cache of > Just v -> return (cache, v) > Nothing -> do > v <- iov > return (HMS.insert k v cache, v) Note that we don't really delete things from the cache. In order to keep things simple, we can assume that we will use a new cache for every shortest path we want to find, and that we throw away that cache afterwards. Loading the graph using Lazy I/O ================================ Now, we get to the main focus of the blogpost: how to use lazy I/O primitives to ensure resources are only loaded when they are needed. Since we are only concerned about one datatype (`City`) our loading code is fairly easy. The most important loading function takes the SQLite connection, the cache we wrote up previously, and a city ID. We immediately use the `cached` combinator in the implementation, to make sure we load every `CityId` only once. > getCityById > :: SQLite.Connection -> Cache CityId City -> CityId > -> IO City > getCityById conn cache id' = cached cache id' $ do Now, we get some information from the database. We play it a bit loose here and assume a singleton list will be returned from the query. > [(name, x, y)] <- SQLite.query conn > "SELECT name, x, y FROM cities WHERE id = ?" [id'] The neighbours are stored in a different table because we have a properly normalised database. We can write a simple query to obtain all roads starting from the current city: > roads <- SQLite.query conn > "SELECT cost, destination FROM roads WHERE origin = ?" > [id'] :: IO [(Double, CityId)] This leads us to the crux of the matter. The `roads` variable contains something of the type `[(Double, CityId)]`, and what we really want is `[(Double, City)]`. We need to recursively call `getCityById` to load what we want. However, doing this "the normal way" would cause problems: 1. Since the `IO` monad is strict, we would end up in an infinite loop if there is a cycle in the graph (which is almost always the case for roads and cities). 2. Even if there was no cycle, we would run into trouble with our usage of `MVar` in the `Cache`. We block access to the `Cache` while we are in the `cached` combinator, so calling `getCityById` again would cause a deadlock. This is where Lazy I/O shines. We can implement lazy I/O by using the [unsafeInterleaveIO](http://hackage.haskell.org/package/base/docs/System-IO-Unsafe.html#v:unsafeInterleaveIO) primitive. Its type is very simple and doesn't look as threatening as `unsafePerformIO`. unsafeInterleaveIO :: IO a -> IO a It takes an `IO` action and _defers_ it. This means that the `IO` action is not executed right now, but only when the value is demanded. That is exactly what we want! We can simply wrap the recursive calls to `getCityById` using `unsafeInterleaveIO`: > neighbours <- IO.unsafeInterleaveIO $ > mapM (traverse (getCityById conn cache)) roads And then return the `City` we constructed: > return $ City id' name (x, y) neighbours Lastly, we will add a quick-and-dirty wrapper around `getCityById` so that we are also able to load cities by name. Its implementation is trivial: > getCityByName > :: SQLite.Connection -> Cache CityId City -> T.Text > -> IO City > getCityByName conn cache name = do > [[id']] <- SQLite.query conn > "SELECT id FROM cities WHERE name = ?" [name] > getCityById conn cache id' Now we can neatly wrap things up in our `main` function: > main :: IO () > main = do > cache <- newCache > conn <- SQLite.open "got.db" > winterfell <- getCityByName conn cache "Winterfell" > kings <- getCityByName conn cache "King's Landing" > printSolution $ > shortestPath cityId cityNeighbours winterfell kings This works as expected: *Main> :main cost: 40.23610549037591, path: Winterfell -> Moat Cailin -> Greywater Watch -> Inn of the Kneeling Man -> Fairmarket -> Brotherhood Without Banners Hideout -> Crossroads Inn -> Darry -> Saltpans -> QuietIsle -> Antlers -> Sow's Horn -> Brindlewood -> Hayford -> King's Landing Disadvantages of Lazy I/O ========================= Lazy I/O also has many disadvantages, which have been widely discussed. Among those are: 1. Code becomes harder to reason about. In a setting without lazy I/O, you can casually reason about an `Int` as either an integer that's already computed, or as something that will do some (pure) computation and then yield an `Int`. When lazy I/O enters the picture, things become more complicated. That `Int` you wanted to print? Yeah, it fired a bunch of missiles and returned the bodycount. This is why I would not seriously consider using lazy I/O when working with a team or on a large project -- it can be easy to forget what is lazily loaded and what is not, and there's no easy way to tell. 2. Scarce resources can easily become a problem if you are not careful. If we keep a reference to a `City` in our heap, that means we also keep a reference to the cache and the SQLite connection. We must ensure that we fully evaluate the solution to something that doesn't refer to these resources (to e.g. a printed string) so that the references can be garbage collected and the connections can be closed. Closing the connections is a problem in itself -- if we cannot guarantee that e.g. streams will be fully read, we need to rely on finalizers, which are pretty unreliable... 3. If we go a step further and add concurrency to our application, it becomes even tricker. Deadlocks are not easy to reason about -- so how about reasoning about deadlocks when you're not sure when the `IO` is going to be executed at all? Despite all these shortcomings, I believe lazy I/O is a powerful and elegant tool that belongs in every Haskeller's toolbox. Like pretty much anything, you need to be aware of what you are doing and understand the advantages as well as the disadvantages. For example, the above downsides do not really apply if lazy I/O is only used _within_ a module. For this blogpost, that means we could safely export the following interface: > shortestPathBetweenCities > :: FilePath -- ^ Database name > -> CityId -- ^ Start city ID > -> CityId -- ^ Goal city ID > -> IO (Maybe (Double, [CityId])) -- ^ Cost and path > shortestPathBetweenCities dbFilePath startId goalId = do > cache <- newCache > conn <- SQLite.open dbFilePath > start <- getCityById conn cache startId > goal <- getCityById conn cache goalId > case shortestPath cityId cityNeighbours start goal of > Nothing -> return Nothing > Just (cost, path) -> > let ids = map cityId path in > cost `seq` foldr seq () ids `seq` > return (Just (cost, ids)) Thanks for reading -- and I hope I was able to offer you a nuanced view on lazy I/O. Special thanks to [Jared Tobin] for proofreading. [Jared Tobin]: https://jtobin.io/