[sci.math] "Semiabstract" datatypes

JWC@IDA.LiU.SE (Jonas Wallgren) (09/06/88)

Assume the following declaration (in ML) of an abstract tree type:

	abstype tree=leaf of int|branch of tree*tree
	with val tend=leaf
	     fun fork l1 l2=branch(l1,l2)
	end;

Everytime a tree is created one is forced to write e.g.

	tfork(tend 1,tend 2);

I.e. every integer must be prefixed with 'tend'.
This implementation not only hides the representation of the tree structure
(tree*tree) but also hides the representation of the leaves.

My idea is that the declaration could look like

	semiabstype tree=int|branch of tree*tree
	with fun tfork l1 l2=branch(l1,l2)
	end;

Then the example above becomes

	tfork 1 2;

in the original abstract type the top is visible and the rest below is hidden.
In the second example there is something visible at the top and something
visible in the bottom, and the middle part is hidden - that's why I call the
type 'semiabstract'.


My questions are:

	Are there any programming languages supporting such a construction?

	Is there any algebraic concept or other mathematical structure
	suitable for describing such a fenomenon?

-------------------------------------------------------------------------------
Jonas Wallgren                                   |               JWC@IDA.LiU.SE
Department of Computer and Information Science   |
Linkoping University                             |-----------------------------
SE-581 83  Linkoping                             |
Sweden                                           |   The Argument Eater: YKx=YK
-------------------------------------------------------------------------------

db@lfcs.ed.ac.uk (Dave Berry) (09/13/88)

In article <896@tragicomix.liu.se> JWC@IDA.LiU.SE (Jonas Wallgren) writes:
>Assume the following declaration (in ML) of an abstract tree type:
>
>	abstype tree=leaf of int|branch of tree*tree
>	with val tend=leaf
>	     fun tfork l1 l2=branch(l1,l2)
>	end;
>
>Everytime a tree is created one is forced to write e.g.
>
>	tfork(tend 1)(tend 2);
>
>My idea is [...]
>Then the example above becomes
>
>	tfork 1 2;

I'm not sure what you're asking.  You can write this in ML as follows:

       abstype tree=leaf of int|branch of tree*tree
       with val tend=leaf
            fun tfork l1 l2=branch(tend l1,tend l2)
       end;

but then you can't write "tfork(tend 1)(tend 2);" anymore.

Do you want to be able to write either
       tfork(tend 1)(tend 2); 	or	tfork 1 2;
with the same definition of tfork?  I agree this would be useful.  I've
sometimes wanted it to abbreviate large ML patterns.

>	Are there any programming languages supporting such a construction?

The nearest I know of is C++, which has the feature that if a function
expects an argmuent of type A and receives one of type B, it will convert
the argument to type A if it knows how to do so.  It can do this iff there
is a constructor (C++ usage of the word) for type A that takes an argument
of type B.

Any other offers?

>	Is there any algebraic concept or other mathematical structure
>	suitable for describing such a phenomenon?
-----------------------------------------------------------------------------
 Dave Berry.		 db@lfcs.ed.ac.uk