Tree-like Structure with unique elements on each level

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Tree-like Structure with unique elements on each level

Martin Drautzburg
Hello all,

I recently modeled a tree like this:

data Predicate a = Any | Pred (S.Set a)
data Product a = Pany | Prod (S.Set(Predicate a, S.Set(Product a)))

What I wanted to achieve was to have each element only once on each level. Hence the Sets. But this structure does not
achieve this. I can easily duplicate elements on a level as long as their subordinates are different, so I might as well
give up working with sets.

Is there a way to construct a tree where each element can occur only once on each level?
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Tree-like Structure with unique elements on each level

Imants Cekusins

> data Predicate a = Any | Pred (S.Set a)
data Product a = Pany | Prod (S.Set(Predicate a, S.Set(Product a)))

Does this fit:

data Predicate a = Any | Pred  a
data Product a = Pred' (Predicate a) |  Prod (Product a)

?


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Tree-like Structure with unique elements on each level

Stephen Tetley-2
In reply to this post by Martin Drautzburg
Hi Martin

The essence of a trie data structure is that all keys at each level
are unique, so so lookup in a trie forms a search path.

There are various implementations of tries on Hackage.

Best wishes

Stephen

On 2 January 2016 at 19:53, martin <[hidden email]> wrote:

> Hello all,
>
> I recently modeled a tree like this:
>
> data Predicate a = Any | Pred (S.Set a)
> data Product a = Pany | Prod (S.Set(Predicate a, S.Set(Product a)))
>
> What I wanted to achieve was to have each element only once on each level. Hence the Sets. But this structure does not
> achieve this. I can easily duplicate elements on a level as long as their subordinates are different, so I might as well
> give up working with sets.
>
> Is there a way to construct a tree where each element can occur only once on each level?
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners