Hi,
I've been looking at the Fudgets research
(http://www.cs.chalmers.se/ComputingScience/Research/Functional/Fudgets/ )
as an example of a purely functional gui.
Afaiu a brief summary is that a Fudget can represent a GUI widget or some
other object, which can have some internal state, and which receives and
passes messages to the other Fudgets it is connected to. Fudgets are
connected to each other by combinators eg:
second >==< first -- sequential (first sends messages to second)
a >*< b -- parallel
There is a continuation passing implementation such that the messages are
passed and internal states of Fudgets are updated (by replacing each fudget
with an updated fudget) as these expressions are evaluated hence the message
passing and maintenance of state doesn't involve any IORefs though
interaction with external devices such as the OS uses IO.
Anyway to get to my point, though all this sounds great, I'm wondering how
to construct an arbitrary graph of Fudgets just from a fixed set of
combinators, such that each Fudget (node in the graph) is only mentioned
once in the expression. To simplify the question, assume we have the
following data structure to describe the desired graph:
data LinkDesc a
= Series a a
| Broadcast a [a]
| Merge [a] a
type GraphDesc a = [LinkDesc a]
and a function to compute a combined object (eg Fudget) corresponding to an
arbitrary graph would be:
mkObj :: Ord label => Map label Obj -> GraphDesc label -> Obj
mkObj = -- ???
The result of mkObj will be some expression, composed from a finite set of
combinators applied to the named objects, but with the all important
property that each named object appears no more than once in the expression
(this is what allows Fudgets to correspond to notional objects which
maintain internal state - during evaluation each fudget gets replaced by an
updated fudget hence can only appear once in the whole expression).
As a very simple example using existing Fudgets combinators,
type Map label value = [(label, value)]
mkObj [("A", objA), ("B", objB), ("C", objC)]
[Series "A" "B", Series "B" "C"]
=== objC >==< objB >==< objA
and
mkObj [("A", objA), ("B", objB), ("C", objC)]
[Broadcast "A" ["B", "C"]]
=== (objB >*< objC) >==< objA
However:
mkObj [("A", objA), ("B", objB), ("C", objC), ("D", objD)]
[Broadcast "A" ["B", "C"], Series "B" "D", Series "A" "D"]
=== ???
The Fudgets library provides many combinators eg for looping, but even so, I
don't think there are sufficient combinators to express the above graph
(though possibly extra nodes and tagging/untagging would solve this
example), or more heavily connected graphs such as:
[Series "A" "B", Series "B" "C", Series "C" "D", Series "D" "B",
Series "C" "A"]
This problem is so general (ie converting a cyclic graph into an expression
tree such that each node appears no more than once) that I'm sure someone
somewhere must already have determined whether or not there can be a
solution, though I don't know where to look or what to search for.
Any ideas?
Thanks, Brian.
--
http://www.metamilk.com
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
