[Haskell-cafe] Manual type-checking in graphs: Avoidable?

[Jeffrey Brown]

Francesco, using existentials looks promising! I'll work on it.

Perhaps people owning hamsters is more easily represented with maps, at
least in an economy in which every hamster has exactly one owner. Here is a
nearly identical example that surely requires a graph:

    data GraphNode = Person String | Hamster String
    data GraphEdge = Owns -- people own hamsters
      | Friend -- any two GraphNodes can be friends

If you used maps for this kind of information, you would have a lot of
copies of the same thing. If you changed someone's name, you would have to
search through each map to find every instance of it. In a graph, by
contrast, you would just change it in the one place that it is represented.
Moreover, with maps there's the risk of indicating someone owns a hamster
that does not exist. You have to keep some kind of master record of which
hamsters are available, and check each map against it. In a graph, a
hamster that does not exist is not represented, and so cannot be linked to.

Bryan Richter wrote;

> Maybe this?
>
>    data GraphNode = NodePerson Person | NodeHamster Hamster

That's what I was already doing! I feel validated.

On Fri, Feb 19, 2016 at 6:18 AM, Tom Ellis <
tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk> wrote:

> On Fri, Feb 19, 2016 at 05:06:57PM +0300, Kosyrev Serge wrote:
> > Tom Ellis <tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk> writes:
> > > On Fri, Feb 19, 2016 at 03:07:59PM +0300, Kosyrev Serge wrote:
> > >> Tom Ellis <tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk> writes:
> > >> > I agree.  FGL seems inappropriate to model people owning hamsters
> because
> > >> > you genuinely want to reflect the difference between people and
> hamsters by
> > >> > having two different node types.
> > >>
> > >> What would you propose instead?
> > >
> > > If I were utterly insane I would propose that FGL be extended with
> > > higher-typed indexes, so instead of
> > >
> > >     Gr :: * -> * -> *
> > >
> > > we would have
> > >
> > >     Gr :: (k -> *) -> (k -> k -> *) -> *
> > >
> > > Then Hamster and Person would be the only inhabitants of some kind k,
> and
> > > you can could choose two different types to represent them, and four
> > > different types to represent the (directed) edges between them.
> >
> > Richard, is something like this possible with what is in GHC 8?
> >
> > Or would DataKinds already be sufficient for this?
>
> GADTs and DataKinds already suffice for this.  Programming like this is
> possible but not especially syntactically convenient, and FGL would have to
> be changed throughout, of course.
>
> (Thanks to Andras Kovacs for introducing me to this lovely world of
> higher-kinded indexed types)
>
> Tom
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>



-- 
Jeffrey Benjamin Brown
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160219/a1de4b24/attachment.html>