Perl 6 can do ADTs, using classes. Kind of.

tree-adt-using-classes.pl

# data Tree a = Branch (Tree a) (Tree a) | Leaf a

class Tree { ... }

class Tree::Branch {
    has Tree $.left;
    has Tree $.right;
}

class Tree::Leaf {
    has $.cargo;
}

class Tree {
    has Tree::Branch $.branch handles <left right>;
    has Tree::Leaf   $.leaf   handles <cargo>;

    method new { die "Cannot construct Tree this way" };
    method new-branch(Tree :$left!, Tree :$right!) {
        self.bless(*, :branch( Tree::Branch.new(:$left, :$right) ));
    }
    method new-leaf($cargo) {
        self.bless(*, :leaf( Tree::Leaf.new(:$cargo) ));
    }
}

# We can still define convenient subtypes Branch and Leaf which
# specialize Tree.

subset Branch of Tree where { defined .branch };
subset Leaf of Tree where { defined .leaf };

my $tree = Tree.new-branch(
    left => Tree.new-leaf(1),
    right => Tree.new-branch(
        left => Tree.new-leaf(2),
        right => Tree.new-leaf(3),
    ),
);
say $tree ~~ Tree;              # True

# Now it's suddenly silly to talk about those other types
# not smartmatching. They're simply not instances of the
# Tree class. So let's skip that.

# 'when' statements are basically sugar for smartmatching,
# and so they work, too. This allows us to 

sub sum_leaves(Tree $_) {
    when Branch { sum_leaves(.left) + sum_leaves(.right) }
    when Leaf   { .cargo }
}

say sum_leaves($tree);          # 6