How to do this functionally?
Dr Pibb
although that detail is not so important.
What *is* important is that I wish to compare equality on directed
cyclic graphs. In order to understand the cycles, I want to have
every node contain a unique integer id. But, I can't figure out how
to allocate this id functionally. What is the best way?
I wish for every term/node to have its id associated with it at
construction time, which is the difficult part for me. If I didn't
want this id to be somewhat permanent, I suppose I would try having
the nodes *not* contain an id, and then when an algorithm tries to
look at the graph, first "rebuild" the graph with leaf types
(Int,Node) rather than just Node...
But, again, that is not quite my intent. Perhaps I need to rework my
thinking?
I come from an imperative programming background, so some things
"feel" uncomfortable to me... In an imperative program, I would just
of a globally accessibly variable of the "current id", and increment
it with every node allocated.
An obvious way to implement it in this way is to have a collection of
state which is passed along all the time to every function. But this
seems rather tedious. I could also use the ST "lazy state thread"
module, which would perhaps elminate some of the tedium... but this
still doesn't feel right.
After doing functional programming for a little while now, I am
suspicious of my inclinations to use imperative-style algorithms...
But, perhaps that is the correct way in this case?
John Heron
Well you could start with something like:
insertNode (zip [1..] [nodes])
Or is your problem getting the cycles built? Here are a couple of other
thoughts to save for a rainy day:
The Haskell library page:
http://www.haskell.org/libraries/#datastructures
A functional graph library from Martin Erwig:
http://www.cs.orst.edu/~erwig/fgl/
and the Haskell wiki
http://www.haskell.org/wiki/wiki
has a lot of good things on how to better learn to do the functional
thing.
Cheers,
John Heron
ol...@pobox.com
> An obvious way to implement it in this way is to have a collection of
> state which is passed along all the time to every function. But this
> seems rather tedious. I could also use the ST "lazy state thread"
> module, which would perhaps elminate some of the tedium...
You can build your own monad -- that will effectively hide the counter
(which you use to tag every node)
Here's an example
--First, some framework
type Numbered a = (Int,a)
newtype NumberedM a = NumberedM (Int -> Numbered a)
instance Monad NumberedM where
NumberedM m >>= f = NumberedM $ \n -> let (n1,v) = (m n)
NumberedM m' = f v
(n1',v') = (m' n1)
in (n1',v')
return x = NumberedM $ \n -> (n,x)
-- additional monad morphisms
-- get the current id and increment it
incr:: NumberedM Int
incr = NumberedM $ \n -> (n+1,n)
run_numberedM:: NumberedM a -> Int -> Numbered a
run_numberedM (NumberedM m) init_count = m init_count
-- Now, on to applications: trees
-- The basic tree datatype
data Tree a = Nd a (Forest a) deriving Show
type Forest a = [Tree a]
make_node val kids = do {
n <- incr;
return (Nd (n,val) kids)
}
-- Finally, let's try to build a binary tree
make_btree:: Int -> NumberedM (Tree (Numbered Int))
make_btree 0 = make_node 0 []
make_btree depth = do {
left <- make_btree (depth -1);
right <- make_btree (depth -1);
make_node depth [left, right]
}
-- Let's see what we've got
Main> run_numberedM (make_btree 1) 100
(103,Nd (102,1)
[Nd (100,0) [],
Nd (101,0) []])
The result is a pair (the_resulting_count,tree)
We tag each node with a unique counter, an integer that starts at 100
and counts forward.
Main> run_numberedM (make_btree 3) 100
(115,Nd (114,3)
[Nd (106,2)
[Nd (102,1)
[Nd (100,0) [],
Nd (101,0) []],
Nd (105,1)
[Nd (103,0) [],
Nd (104,0) []]],
Nd (113,2)
[Nd (109,1)
[Nd (107,0) [],
Nd (108,0) []],
Nd (112,1)
[Nd (110,0) [],
Nd (111,0) []]]])
It does seem to work, don't you think?
Marcin 'Qrczak' Kowalczyk
> You can build your own monad -- that will effectively hide the counter
> (which you use to tag every node)
Or use a ready-made monad. GHC provides some common monads:
> type Numbered a = (Int,a)
>
> newtype NumberedM a = NumberedM (Int -> Numbered a)
import MonadState
type NumberedM = State Int
> instance Monad NumberedM where
This instance is of course provided when NumberedM = State Int.
> -- get the current id and increment it
> incr:: NumberedM Int
> incr = NumberedM $ \n -> (n+1,n)
incr :: NumberedM Int
incr = modify (+1) >> get
-- Slightly different than the above: returns the incremented value.
> run_numberedM:: NumberedM a -> Int -> Numbered a
> run_numberedM (NumberedM m) init_count = m init_count
run_numberedM :: NumberedM a -> Int -> Numbered a
run_numberedM = runState
-- Or perhaps:
run_numberedM :: NumberedM a -> Int -> a
run_numberedM = evalState
--
__("< Marcin Kowalczyk * qrc...@knm.org.pl http://qrczak.ids.net.pl/
\__/
^^ SYGNATURA ZASTĘPCZA
QRCZAK
Dominic Steinitz
programming to graphs?
--
Dominic Steinitz
"Dr Pibb" <dr_...@hotmail.com> wrote in message
news:a1eba1e1.0110...@posting.google.com...
Peter G. Hancock
>> An obvious way to implement it in this way is to have a
>> collection of state which is passed along all the time to every
>> function. But this seems rather tedious.
"Obvious" is good, not bad. If "tedious" means that there is too much
plumbing cluttering up the code, then it's not tedious because you can
(and should) hide the plumbing by using a monad with a
post-incrementing read-out, IYSWIM. It will look pretty much like the
natural imperative program if you use "do/return" notation. If
"tedious" means that the code turns out to be slow with a monad you
program yourself, you can re-program just the monad to use one of
these "dirty" stateful built-ins that people like so much.
--
Peter Hancock