Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Implementation question about directed acyclic graph
(Doug McIlroy)
----------------------------------------------------------------------
Message: 1
Date: Sat, 09 May 2015 10:59:22 -0400
From: Doug McIlroy <[email protected]>
To: [email protected]
Cc: [email protected]
Subject: Re: [Haskell-beginners] Implementation question about
directed acyclic graph
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Your suggested this representation
> type Connections = M.Map Int a [Int]
>
> data Graph a = Empty
> | Gragh { nodes :: M.Map Int (Node a), nextID :: Int,
> connections :: Connections }
Making connections by name (in this case an Int) entails table
lookup at every step of any graph traversal. That is avoided by
this simple representation:
data Graph a = Graph a [Graph a]
perhaps elaborated to allow the empty case
data Graph a = Graph a [Graph a] | Empty
If you need node identifiers, e.g. to recognize repeat visits to
a node, they can be incorporated in data type a, or abstracted
into another field
data Eq id => Graph id a = Graph id a [Graph id a]
Doug McIlroy
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 83, Issue 12
*****************************************
