# [curry] What speed to expect doing logic on graphs represented by maps

From: Jeffrey Brown <jeffbrown.the_at_gmail.com>
Date: Mon, 12 Nov 2018 11:40:10 -0500

I want to write something resembling an editor for a graph database. I'm
wondering if Curry will be fast enough.

The data defining the graph would resemble the following:

data Graph = Graph {
children :: Map Label (Set Address)
parents :: Map Label (Set Address) }

I would define rules such as:

descendent :: Graph -> Index -> Index
descendent g i
-- If j is i's child, then j is i's descendent.
| Set.member j \$ Map.lookup i \$ children g
= j
descendent g i
-- If j is i's descendent and k is j's child, then k is i's descendent.
| descendent g i j
& (Set.member k \$ Map.lookup k \$ children g)
= k

I'll use hash maps unless their space requirements stop me.

I'm hoping the resulting code will quickly (say, in under a second) answer
queries over a few million nodes, along the lines of "the descendents of X
and Y, minus any descendents of Z or W". If an unbounded number of
generations proves computationally difficult, I would not be bothered by
needing to impose depth limits, ala "the first two generations of
descendents of X and Y, minus the first seven generations of descendents of
Z or W".

The graph would be sparse: with an average number of children well under
five, and few cycles.

Is this kind of performance a reasonable thing to expect from Curry? If so,
using which compiler? If not, can you recommend another language?

I know Haskell, and prefer it immensely to any other language. I am
reluctant to write a full application in a pure logic language like
Mercury, but I will if need be.

--
Jeff Brown | Jeffrey Benjamin Brown