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.
I’m curious, in your update function, you label, but do not use, the first Network structure, especially curious is that when I looked up the name of the method of the short-cut you looked like you were about to use, I noticed that it’s referred to as an “update”:
> update u@(Network v n) (p, nv) = u {valueAt = \pp -> if (pp == p) then nv else v pp}
Yes, it was intended to be used as a short-cut, like you described above. But somewhere between writing the code and posting it, I changed it.
Just as a minor quibble:
(concat $ map go $ tr `neighboursOf` p)
might be better written as simply:
concatMap go (tr `neighboursOf` p)
Naturally, doing this depends on what you want to be understood.
Thanks, now I’ve learned a new function :)
can also be written as
Yes, but that will involve explaining the behind-the-scenes operations of some monad.