Bagaimana Anda menyandikan Jenis Data Aljabar dalam C # - atau bahasa seperti Java?

Ada beberapa masalah yang mudah dipecahkan oleh Tipe Data Aljabar, misalnya tipe Daftar dapat dengan sangat ringkas dinyatakan sebagai:

data ConsList a = Empty | ConsCell a (ConsList a)

consmap f Empty          = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)

l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l

Contoh khusus ini ada di Haskell, tetapi akan serupa dalam bahasa lain dengan dukungan asli untuk Tipe Data Aljabar.

Ternyata ada pemetaan yang jelas untuk subtipe gaya OO: tipe data menjadi kelas dasar abstrak dan setiap konstruktor data menjadi subkelas beton. Berikut ini contoh dalam Scala:

sealed abstract class ConsList[+T] {
  def map[U](f: T => U): ConsList[U]
}

object Empty extends ConsList[Nothing] {
  override def map[U](f: Nothing => U) = this
}

final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
  override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}

val l = (new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)

Satu-satunya hal yang diperlukan di luar subclass naif adalah cara untuk menyegel kelas, yaitu cara untuk membuatnya mustahil untuk menambahkan subclass ke hierarki.

Bagaimana Anda mendekati masalah ini dalam bahasa seperti C # atau Java? Dua batu sandungan yang saya temukan ketika mencoba menggunakan Tipe Data Aljabar di C # adalah:

• Saya tidak tahu apa yang disebut tipe bawah di C # (yaitu saya tidak tahu apa yang harus dimasukkan ke dalam class Empty : ConsList< ??? >)
• Saya tidak bisa menemukan cara untuk menutup ConsList sehingga tidak ada subclass yang dapat ditambahkan ke hierarki

Apa yang akan menjadi cara paling idiomatis untuk mengimplementasikan Tipe Data Aljabar di C # dan / atau Java? Atau, jika itu tidak mungkin, apa yang akan menjadi pengganti idiomatik?

Ada cara yang mudah, tapi sederhana untuk menyegel kelas di Jawa. Anda menempatkan konstruktor pribadi di kelas dasar lalu membuat kelas dalam subkelas itu.

public abstract class List<A> {

   // private constructor is uncallable by any sublclasses except inner classes
   private List() {
   }

   public static final class Nil<A> extends List<A> {
   }

   public static final class Cons<A> extends List<A> {
      public final A head;
      public final List<A> tail;

      public Cons(A head, List<A> tail) {
         this.head = head;
         this.tail = tail;
      }
   }
}

Tack pada pola pengunjung untuk pengiriman.

Proyek saya jADT: Java Algebraic DataTypes menghasilkan semua boilerplate untuk Anda https://github.com/JamesIry/jADT

Anda dapat mencapai ini dengan menggunakan pola pengunjung , yang akan melengkapi pencocokan pola. Sebagai contoh

data List a = Nil | Cons { value :: a, sublist :: List a }

dapat ditulis dalam Java sebagai

interface List<T> {
    public <R> R accept(Visitor<T,R> visitor);

    public static interface Visitor<T,R> {
        public R visitNil();
        public R visitCons(T value, List<T> sublist);
    }
}

final class Nil<T> implements List<T> {
    public Nil() { }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitNil();
    }
}
final class Cons<T> implements List<T> {
    public final T value;
    public final List<T> sublist;

    public Cons(T value, List<T> sublist) {
        this.value = value;
        this.sublist = sublist;
    }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitCons(value, sublist);
    }
}

Sealing dicapai oleh Visitorkelas. Setiap metodenya menyatakan bagaimana mendekonstruksi salah satu subclass. Anda dapat menambahkan lebih banyak subclass, tetapi harus mengimplementasikan acceptdan dengan memanggil salah satu visit...metode, sehingga harus berperilaku suka Consatau suka Nil.

Jika Anda menyalahgunakan parameter bernama C # (diperkenalkan dalam C # 4.0), Anda bisa membuat tipe data aljabar yang mudah dicocokkan dengan:

Either<string, string> e = MonthName(2);

// Match with no return value.
e.Match
(
    Left: err => { Console.WriteLine("Could not convert month: {0}", err); },
    Right: name => { Console.WriteLine("The month is {0}", name); }
);

// Match with a return value.
string monthName =
    e.Match
    (
        Left: err => null,
        Right: name => name
    );
Console.WriteLine("monthName: {0}", monthName);

Berikut ini adalah implementasi dari Eitherkelas:

public abstract class Either<L, R>
{
    // Subclass implementation calls the appropriate continuation.
    public abstract T Match<T>(Func<L, T> Left, Func<R, T> Right);

    // Convenience wrapper for when the caller doesn't want to return a value
    // from the match expression.
    public void Match(Action<L> Left, Action<R> Right)
    {
        this.Match<int>(
            Left: x => { Left(x); return 0; },
            Right: x => { Right(x); return 0; }
        );
    }
}

public class Left<L, R> : Either<L, R>
{
    L Value {get; set;}

    public Left(L Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Left(Value);
    }
}

public class Right<L, R> : Either<L, R>
{
    R Value { get; set; }

    public Right(R Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Right(Value);
    }
}

Dalam C #, Anda tidak dapat memiliki Emptytipe itu, karena, karena reifikasi, tipe dasar berbeda untuk tipe anggota yang berbeda. Anda hanya dapat memiliki Empty<T>; tidak berguna.

Di Jawa, Anda dapat memiliki Empty : ConsListkarena penghapusan tipe, tetapi saya tidak yakin apakah pemeriksa tipe tidak akan berteriak di suatu tempat.

Namun karena kedua bahasa memiliki null, Anda dapat menganggap semua jenis referensi mereka sebagai "Apa pun | Null". Jadi, Anda hanya akan menggunakan nullsebagai "Kosong" untuk menghindari harus menentukan apa yang berasal.

Satu-satunya hal yang diperlukan di luar subclass naif adalah cara untuk menyegel kelas, yaitu cara untuk membuatnya mustahil untuk menambahkan subclass ke hierarki.

Di Jawa kamu tidak bisa. Tetapi Anda dapat mendeklarasikan kelas dasar sebagai paket privat, yang berarti bahwa semua subclass langsung harus memiliki paket yang sama dengan kelas dasar. Jika Anda kemudian mendeklarasikan subclass sebagai final, mereka tidak dapat subclass lebih jauh.

Saya tidak tahu apakah ini akan mengatasi masalah Anda yang sebenarnya ...

Tipe data ConsList<A>dapat direpresentasikan sebagai antarmuka. Antarmuka memperlihatkan deconstructmetode tunggal yang memungkinkan Anda untuk "mendekonstruksi" nilai dari jenis itu - yaitu, untuk menangani masing-masing konstruktor yang mungkin. Panggilan ke deconstructmetode analog dengan case offormulir di Haskell atau ML.

interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}

The deconstructMetode mengambil "callback" fungsi untuk setiap konstruktor di ADT tersebut. Dalam kasus kami, dibutuhkan fungsi untuk kasus daftar kosong, dan fungsi lain untuk kasus "sel kontra".

Setiap fungsi panggilan balik menerima sebagai argumen nilai yang diterima oleh konstruktor. Jadi kasus "daftar kosong" tidak memerlukan argumen, tetapi kasus "kontra sel" mengambil dua argumen: kepala dan ujung daftar.

Kita dapat menyandikan "beberapa argumen" ini menggunakan Tuplekelas, atau menggunakan currying. Dalam contoh ini, saya memilih untuk menggunakan Pairkelas sederhana .

Antarmuka diimplementasikan sekali untuk setiap konstruktor. Pertama, kami memiliki implementasi untuk "daftar kosong". The deconstructpelaksanaan hanya menyebut emptyCasefungsi callback.

class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}

Kemudian kami menerapkan kasus "sel kontra" dengan cara yang sama. Kali ini kelas memiliki properti: kepala dan ekor daftar yang tidak kosong. Dalam deconstructimplementasi, properti-properti tersebut diteruskan ke consCasefungsi callback.

class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}

Berikut adalah contoh penggunaan penyandian ADT ini: kita dapat menulis sebuah reducefungsi yang merupakan daftar lipat yang biasa.

<T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}

Ini analog dengan implementasi ini di Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2

Satu-satunya hal yang diperlukan di luar subclass naif adalah cara untuk menyegel kelas, yaitu cara untuk membuatnya mustahil untuk menambahkan subclass ke hierarki.

Bagaimana Anda mendekati masalah ini dalam bahasa seperti C # atau Java?

Tidak ada cara yang baik untuk melakukan ini, tetapi jika Anda bersedia untuk hidup dengan hack mengerikan maka Anda dapat menambahkan beberapa jenis eksplisit memeriksa konstruktor kelas dasar abstrak. Di Jawa, ini akan menjadi sesuatu seperti

protected ConsList() {
    Class<?> clazz = getClass();
    if (clazz != Empty.class && clazz != ConsCell.class) throw new Exception();
}

Dalam C # itu lebih rumit karena reified generics - pendekatan yang paling sederhana mungkin untuk mengubah tipe menjadi string dan memotong-motong itu.

Perhatikan bahwa di Jawa bahkan mekanisme ini secara teoritis dapat dilewati oleh seseorang yang benar-benar ingin melalui model serialisasi atau sun.misc.Unsafe.