Eric Dedieu | 13 Oct 23:25 2012
Picon

Interleaving type variables in a tree, has this a name ?

Hi Haskell Helpers,

For a hobby projet to learn haskell, I'm trying to use this kind of interleaved
tree structure (simplified):

> data ANode a b = ANode a [BNode a b] [BNode a b]
> data BNode a b = BNode b [ANode a b] [ANode a b]

The first list of each node is for links "up", the second for "down".
I can navigate with functions like:

> type UpRank   = Int -- index in the list of nodes
> type DownRank = Int
>
> upA   :: UpRank -> ANode a b -> Maybe (BNode a b, DownRank)
> downB :: DownRank -> BNode a b -> Maybe (ANode a b, UpRank)

Such as going first up then down leads me to the same point (actually
this simplified structure is not enough to do this, but is enough to
show my problem simply). Thee are also of course upB and downA.

From this idea I have devised a kind of zipper to navigate the tree,
add nodes, and be able to step back. However, with this pattern of
interleaving a and b values, I could not help but duplicating in a way
every data or function declaration, to apply from an A or a B, and
often code is very similar (like for upA and downB).

Also, I want to go through the tree and modify it keeping the same
structure, applying different functions to A and B nodes, like a "map"
involving a pair of functions that will be applied alternatively. I
(Continue reading)

Chaddaï Fouché | 14 Oct 00:34 2012
Picon

Re: Interleaving type variables in a tree, has this a name ?

On Sat, Oct 13, 2012 at 11:25 PM, Eric Dedieu <papa.eric <at> free.fr> wrote:
> Hi Haskell Helpers,
>
> For a hobby projet to learn haskell, I'm trying to use this kind of interleaved
> tree structure (simplified):
>
>> data ANode a b = ANode a [BNode a b] [BNode a b]
>> data BNode a b = BNode b [ANode a b] [ANode a b]

Wouldn't the following work as well and be simpler to handle :

> data Node a b = Node a [Node b a] [Node b a]

--

-- 
Jedaï

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Eric Dedieu | 14 Oct 22:45 2012
Picon

Re: Interleaving type variables in a tree, has this a name ?

>>> data ANode a b = ANode a [BNode a b] [BNode a b]
>>> data BNode a b = BNode b [ANode a b] [ANode a b]
>
> Wouldn't the following work as well and be simpler to handle :
>
>> data Node a b = Node a [Node b a] [Node b a]

Yes !

In fact my actual structure is not symmetrical (some lists must
preserve order and store additional information for that, some not,
and one is a Maybe), so I "naturally" used two distinct node types.
When I simplified it for the post, it became symmetrical...

Yet I think you're right: if I made it symmetrical (and more general),
I would gain much by using your suggestion (and I could also define
e.g. Foldable (Node a) which would nicely work a all levels).

Thanks.

Gmane