3 ms·

ADTs is a concept I've had a tough time understanding; the approximate definition that made the most impact with is considering them as a specific type of enume

ADTs is a concept I've had a tough time understanding; the approximate definition that made the most impact with is considering them as a specific type of enumerations: Ones where each variant holds a value. Is this correct?

ChrisMarshallNY 4y ago
That’s the way Swift enums work. Here’s an interesting little exploration: https://littlegreenviper.com/miscellany/swiftwater/writing-a-robust-little-parser-in-swift-epilogue/#peek https://littlegreenviper.com/miscellany/swiftwater/writing-a...
thesz 4y ago
It is the other way around: enumerations are special cases of algebraic data types with no values attached. In algebraic data types we have a sum (union) of a labeled cartesian products, and each product may have arbitrary number of values: data MaybeInt = NoInt | AnInt Int data MaybeItsPair = NoIntsPair | AnIntPair Int Int The first constructor in both data types is a labeled (No...) product with empty number of value to apply cartesian product to. The second constructor in both data types is a cartesian product: in first case an Int and in case a pair of Ints. Of course you can have more involved data type: data Expr = Void | Const Int | Var String | Bin BinOp Expr Expr | Un UnOp Expr A label, two single value constructors and much more involved operations as well.
- ghostpepper 4y ago
  Can you explain the term 'cartesian product' in this context? I'm familiar with the cross product from undergrad linear algebra but I haven't applied algebra to types before, and I don't understand what two sets would produce a single Int as their product. I haven't studied much theoretical computer science so I'd love to hear some good beginner resources on this stuff.
  - thesz 4y ago
    Cartesian product: https://en.wikipedia.org/wiki/Cartesian_product https://en.wikipedia.org/wiki/Cartesian_product The number of variants of the AnIntPair construction is the number of distinct elements in the Int type, squared. I used definition of algebraic data type in Haskell: http://wiki.haskell.org/Algebraic_data_type http://wiki.haskell.org/Algebraic_data_type
  - justinpombrio 4y ago
    "Cartesian product" is a fancy word for "pair". Or more generally "tuple".

ChrisMarshallNY 4y ago

That’s the way Swift enums work. Here’s an interesting little exploration: https://littlegreenviper.com/miscellany/swiftwater/writing-a-robust-little-parser-in-swift-epilogue/#peek https://littlegreenviper.com/miscellany/swiftwater/writing-a...

thesz 4y ago

It is the other way around: enumerations are special cases of algebraic data types with no values attached. In algebraic data types we have a sum (union) of a labeled cartesian products, and each product may have arbitrary number of values: data MaybeInt = NoInt | AnInt Int data MaybeItsPair = NoIntsPair | AnIntPair Int Int The first constructor in both data types is a labeled (No...) product with empty number of value to apply cartesian product to. The second constructor in both data types is a cartesian product: in first case an Int and in case a pair of Ints. Of course you can have more involved data type: data Expr = Void | Const Int | Var String | Bin BinOp Expr Expr | Un UnOp Expr A label, two single value constructors and much more involved operations as well.

ghostpepper 4y ago
Can you explain the term 'cartesian product' in this context? I'm familiar with the cross product from undergrad linear algebra but I haven't applied algebra to types before, and I don't understand what two sets would produce a single Int as their product. I haven't studied much theoretical computer science so I'd love to hear some good beginner resources on this stuff.
- thesz 4y ago
  Cartesian product: https://en.wikipedia.org/wiki/Cartesian_product https://en.wikipedia.org/wiki/Cartesian_product The number of variants of the AnIntPair construction is the number of distinct elements in the Int type, squared. I used definition of algebraic data type in Haskell: http://wiki.haskell.org/Algebraic_data_type http://wiki.haskell.org/Algebraic_data_type
- justinpombrio 4y ago
  "Cartesian product" is a fancy word for "pair". Or more generally "tuple".