go almost has algebraic datatypes?

[Ealdwulf Wuffinga]

Hi,
I realise everyone has been asking about their favourite language features, so
I'll say first that I think go as it stands is a great improvement over
existing systems languages.

Anyway, I was trying to figure out whether go has anything equivalent to
algebraic data types, as in languages like ML or Haskell. For those not
familiar with those languages, algebraic datatypes are a type-safe alternative
to the 'union' of C/C++.

It looks to me that go has most of the functionality of algebraic
types in these languages, due to the 'Type switch' construct: this provides a
type safe way of accessing a variable as any of the types it can dynamically
take. However, as far as I can tell the compiler has no way of checking that all
of the possible dynamic types of a variable have a case in the
switch. Is this correct?

It appears to me that a way of specifying a finite list of types would
slot quite neatly into go. As an example, I'll define a 'Tree' algebraic
datatype. Defining the types of the alternatives:

type TreeLeaf int;
type TreeNode struct { left, right *Tree }

Currently, an actual tree would have to be declared of type 'interface {}'.
Instead, one could have a definition like:

type Tree alternatives {TreeLeaf,TreeNode}

Variables of type 'Tree' would then work like variables of type 'interface {}'
except that you can only assign TreeLeaf or TreeNode values to them.

For something as simple as a tree this doesn't gain you much. It comes
into its own when you have a list of types that gets added to. Then the compiler
can tell you all the places in the code where you need to add code to deal with
the new variant.

Has anything like this been considered?

Ealdwulf

[Santidhammo]

This is not such a bad idea. It gives you the opportunity to have what
most system languages lack, a dynamic type, and it gives the safety
most dynamic languages lack.

What I could imagine is a way to ensure call safety in the following
manner:

func (tree *Tree) HandleTree {
goalt handleTreeImpl(tree) // goalt sounds nice :-)
}

func (leaf *TreeLeaf) handleTreeImpl { ... }

func (node *TreeNode) handleTreeImpl { ... }

Is this what you are trying to convey?

[Evan Shaw]

Couldn't you get basically the same result if you just made Tree an interface? You could do something like:

type Tree interface {
HandleTree()
}

type TreeLeaf int;
func (leaf *TreeLeaf) HandleTree() { ... }

type TreeNode struct { left, right *Tree }

func (node *TreeNode) HandleTree() { ... }

The main difference is that instead of explicitly listing the types that Tree can be, we're just defining what it takes to be considered a Tree. To me, this seems like a better approach in general.

[Rick R]

What he's basically describing are GADTs ala Haskell and other enlightened languages.  The GADTs are basically typesafe unions. Types that can be one of any types in a constrained set.  The thing is that these types are just data. They don't have, and shouldn't have, any methods like an interface value might.

Go can achieve the same result as Haskell's GADTs albeit with more typing.

An example might be found in an interpreter for a Toy language. (apologies to http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours)

There is a number of potential primitives in our language, an Atoms, Lists (of something), Numbers, Strings, and Boolean values. When the parser function runs, it will return whichever primitive it finds next. But how do represent what is a valid value to be returned by the parser? The answer is GADTs.
In Haskell:

data ToyVal = Atom String
            | List [ToyVal]

            | Number Integer
            | String String

            | Bool Bool

So we're saying that ToyVal can actually represent a String, a list of ToyVals, an Integer, or a Boolean.
So we can return a ToyVal from our parse function, then pattern match on it's type, and act accordingly.

Go can achieve similar results with more effort using:

type ToyVal interface {
 toyvaldummy()
}

type Atom string;
type List []ToyVal;
type Number int;
type String string
type Bool bool

func (a *Atom) toyvaldummy() {};
func (a *List) toyvaldummy() {};
func (a *Number) toyvaldummy() {};
func (a *String) toyvaldummy() {};
func (a *Bool) toyvaldummy() {};

This would allow you to specify that ToyVal can only be represented by these 5 types.  This seems like a large amount of typing when compared to Haskell. In addition, we can do nothing to stop someone else from adding to that list. But, to me, it's a reasonable facsimile.

In either case, this allows us to call:

func handlePrimitive(text string)
{
  val result ToyVal;
  result = parseSomething(text);
  switch t := result.(type) {
    case Atom:
       // do something with Atoms
    case List:
       // do something with lists
    ...
  }
}

[Sjoerd van Leent]

I was thinking of this solution later, and I think the only thing that should be added is a termination to the interface type, basically telling the compiler to make the interface final. This means that types can not be added anymore to the interface and voila, we have what we want.

As to use the ToyVal example:

type ToyVal interface {
 toyvaldummy()
}

type Atom string;
type List []ToyVal;
type Number int;
type String string;
type Bool bool;

func (a *Atom) toyvaldummy() {};
func (a *List) toyvaldummy() {};
func (a *Number) toyvaldummy() {};
func (a *String) toyvaldummy() {};

func (a *Bool) toyvaldummy() {};

finalize ToyVal;

2009/11/23 Rick R <rick.ri...@gmail.com>

--
Sjoerd van Leent

Consultant

Realworld Systems
Tel:  +31 345 614 406
Mobile: +31 6 26256153
http://www.realworld-systems.com
sjoerd.v...@realworld-systems.com

[ealdwulf]

On Nov 23, 8:49 pm, Evan Shaw <chicken...@gmail.com> wrote:
> Couldn't you get basically the same result if you just made Tree an
> interface?

That works if you are only trying to use one value, but you might want
to deal with more that one.
Eg, Suppose you want to define an ordering relation on Tree values:

func lowerThan(Tree a,Tree b) bool
[or (Tree a) lowerThan(Tree b) bool]

Ealdwulf

[roger peppe]

2009/11/23 Rick R <rick.ri...@gmail.com>:

> What he's basically describing are GADTs ala Haskell

sorry to be pedantic, but i think you're actually describing
haskell's plain ADTs (algrebraic data types).
GADTs are a relatively new addition to haskell
that provide more advanced features.