A General Network Module

by Mithrandir

Let’s say we need to solve a problem involving a graph-like structure, possibly containing cycles. We want to do this in a functional way (Haskell) but we are stuck when we deal with the cycles.

Of course, we can use a «Tying the Knot» technique, but, unfortunately, this doesn’t really help: if we change only one single value in our graph we will have to build the entire structure if we only use what’s presented there. Moreover, we are forced to know some things about our structure when we are writting our code. Wouldn’t it be more useful to have a general network of nodes which can be updated very fast?

> module Network where

It seems that we can do this, if we will consider each node in the network to have an index and a value which can be obtained by applying a function to that index. Also, the neighbourhood of a specific node can be obtained by applying another function to that index. We would like to keep that index generic and the values not restricted to some type.

> data Network p a = Network {
>   valueAt :: p -> a
>   , neighboursOf :: p -> [p]
>   }

Thus, the update value function can be easily written:

> update :: (Eq p) => (Network p a) -> (p, a) -> (Network p a)
> update u@(Network v n) (p, nv) = Network (\pp -> if (pp == p) then nv else v pp) n

We could have used functions instead of values in the if..then..else part but I wasn’t sure if using id there would be a no-op with no performance penalty or not.

Now, we can test this short module (which will be completed when I will need to change the underlying structure) with the following short test case:

import Network
 
> test0 size = Network (\p->p) neigh
>   where
>     neigh x
>       | x == 0 = [size-1, 1]
>       | x == size-1 = [size-2, 0]
>       | otherwise = [x-1, x+1]
>
> toList dl = go 0
>   where
>     go x = (dl `valueAt` x) : go (last $ dl `neighboursOf` x)
>
> test1 = (test0 10) `update` (4, 42)
>
> test2 = Network v n
>   where
>     v (0, 0) = 0
>     v (0, 1) = 2
>     v (0, 2) = 4
>     v (1, 0) = 5
>     v (1, 1) = 8
>     v (1, 2) = 0
>     v _ = 0
>     n (0, 0) = [(0, 1), (1, 0)]
>     n (0, 1) = [(1, 2)]
>     n (0, 2) = []
>     n (1, 0) = [(1, 1)]
>     n (1, 1) = [(0, 2)]
>     n _ = []
>
> toList' tr = go (0, 0)
>   where
>     go p = (tr `valueAt` p) : (concat $ map go $ tr `neighboursOf` p)
>
> test3 = test2 `update` ((0, 2), 42) `update` ((0, 0), 42)

If a few days I’ll come with the puzzle and the solution which required this structure. Maybe, I’ll find something better until then (self search or through reader’s comments).

PS: if you want to run the code you can save the article as Network.lhs and load it with ghci. If you want to have two modules, just like I have, then you should split the article right before the import Network line and add a > in front of it.

About these ads