Manual type-checking in graphs: Avoidable?

I use FGL, which (roughly) defines type Gr a b as a graph on nodes of type a and edges of type b. Suppose you wanted a graph that described which people own which hamsters, knowing only their name. You would have to make node and edge types like this: data GraphNode = Person String | Hamster String data GraphEdge = Has where the strings represent their names. Suppose then you wanted to write a function that, given a person, returns the names of all their hamsters. To make sure the call makes sense, the function would have to first check that the input is in fact a person. Since persons and hamsters are both constructors of the same type, you can't let Haskell's robust, beautiful type-checking system distinguish them for you; you've got to write something like "case n of Person _ -> True; _ -> False". Is there some way around writing such manual checks? -- Jeffrey Benjamin Brown

On Thu, Feb 18, 2016 at 06:50:26PM -0800, Jeffrey Brown wrote:
Suppose then you wanted to write a function that, given a person, returns the names of all their hamsters. To make sure the call makes sense, the function would have to first check that the input is in fact a person. Since persons and hamsters are both constructors of the same type, you can't let Haskell's robust, beautiful type-checking system distinguish them for you; you've got to write something like "case n of Person _ -> True; _ -> False".
Is there some way around writing such manual checks?
Hello Jeffrey, have you considered using Phantom types [1]? [1] https://wiki.haskell.org/Phantom_type#Simple_examples

I had not!
I'm not seeing how such a solution would work. The nodes in a graph all
have to have the same type. If the phantom parameter distinguished two
nodes, they could not be used together.
But maybe you see something there that I don't?
On Thu, Feb 18, 2016 at 8:36 PM, Francesco Ariis
Suppose then you wanted to write a function that, given a person, returns the names of all their hamsters. To make sure the call makes sense, the function would have to first check that the input is in fact a person. Since persons and hamsters are both constructors of the same type, you can't let Haskell's robust, beautiful type-checking system distinguish
On Thu, Feb 18, 2016 at 06:50:26PM -0800, Jeffrey Brown wrote: them
for you; you've got to write something like "case n of Person _ -> True; _ -> False".
Is there some way around writing such manual checks?
Hello Jeffrey, have you considered using Phantom types [1]?
[1] https://wiki.haskell.org/Phantom_type#Simple_examples _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
-- Jeffrey Benjamin Brown

On Thu, Feb 18, 2016 at 09:28:24PM -0800, Jeffrey Brown wrote:
I had not!
I'm not seeing how such a solution would work. The nodes in a graph all have to have the same type. If the phantom parameter distinguished two nodes, they could not be used together.
But maybe you see something there that I don't?
Argh, indeed you are correct. Maybe it can be worked around with existential quantification like this? {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE ExistentialQuantification #-} data Person = Person data Hamster = Hamster data GraphNode a = P String -- hide these | H String -- coll. of vertices data HumHamGraph = forall c . Test c => Gr [(c, c)] findCritters :: HumHamGraph -> GraphNode Person -> GraphNode Hamster findCritters = undefined class Test a where name :: a -> String instance Test (GraphNode Person) where name (P s) = s instance Test (GraphNode Hamster) where name (H s) = s toast = [(P "a,ga", H "beta"), (H "cas", P "cds")] For sure it looks ugly :s

On Thu, Feb 18, 2016 at 06:50:26PM -0800, Jeffrey Brown wrote:
I use FGL, which (roughly) defines type Gr a b as a graph on nodes of type a and edges of type b.
Suppose you wanted a graph that described which people own which hamsters, knowing only their name. You would have to make node and edge types like this: data GraphNode = Person String | Hamster String data GraphEdge = Has where the strings represent their names.
Suppose then you wanted to write a function that, given a person, returns the names of all their hamsters. To make sure the call makes sense, the function would have to first check that the input is in fact a person. Since persons and hamsters are both constructors of the same type,
Actually, I think the problem is that "String" is the same type as "String". Maybe this? data GraphNode = NodePerson Person | NodeHamster Hamster Then you can expose an API that just accepts a Person, and let the find-function take care of constructing the proper start value (i.e. a NodePerson). personHamsters :: MyGraph -> Person -> [Hamster] personHamsters g p = ... where startNode = NodePerson p Still, you'll have to do case evaluation at *some* point, right? If you have two types of nodes, and you're zooming around the graph, you'll have to stop and dereference each node to know what to do next. At least by hiding the details behind the API, your search function will be total.

Jeffrey Brown
I use FGL, which (roughly) defines type Gr a b as a graph on nodes of type a and edges of type b.
Suppose you wanted a graph that described which people own which hamsters, knowing only their name. You would have to make node and edge types like this: data GraphNode = Person String | Hamster String data GraphEdge = Has where the strings represent their names.
Suppose then you wanted to write a function that, given a person, returns the names of all their hamsters. To make sure the call makes sense, the function would have to first check that the input is in fact a person. Since persons and hamsters are both constructors of the same type, you can't let Haskell's robust, beautiful type-checking system distinguish them for you; you've got to write something like "case n of Person _ -> True; _ -> False".
I'll allow myself to rephrase what Tom Ellis already said more strongly. Type systems are tools for making invalid values unrepresentable. If you find yourself in a situation where a certain solution doesn't allow you to do that -- keep looking. -- с уважениeм / respectfully, Косырев Сергей

What you need is a Relation, not a Graph with nodes all of the same type! For me the problem below is most easily solved using Data.Map either use Map Person [Hamster] or Map Hamster [Person] to get the most general relations (many-many) If every Hamster has at most one owner, use Map Hamster Person
Jeffrey Brown
writes: I use FGL, which (roughly) defines type Gr a b as a graph on nodes of type a and edges of type b.
Suppose you wanted a graph that described which people own which hamsters, knowing only their name. You would have to make node and edge types like this: data GraphNode = Person String | Hamster String data GraphEdge = Has where the strings represent their names.
Suppose then you wanted to write a function that, given a person, returns the names of all their hamsters. To make sure the call makes sense, the function would have to first check that the input is in fact a person. Since persons and hamsters are both constructors of the same type, you can't let Haskell's robust, beautiful type-checking system distinguish them for you; you've got to write something like "case n of Person _ -> True; _ -> False".
Andrew Butterfield School of Computer Science & Statistics Trinity College Dublin 2, Ireland
participants (5)
-
Bryan Richter
-
butrfeld
-
Francesco Ariis
-
Jeffrey Brown
-
Kosyrev Serge