Algebraic Data Types for C99

Post by nyssos » Thu, May 09, 2024, 4:50 PM UTC

dtech wrote: post #48

fanf2 wrote: post #41

Earlier quoted context omitted.

Union types are not the same as sum types.

TS narrows union types cases based on conditionals like "if" (called discriminated unions in the docs in the past), and supports exhaustiveness checks. How do they differ in functionality from sum types?

     L = { tag: "a", payload: string } | { tag: "b", payload: number }
     R = { tag: "b", payload: number } | { tag: "c", payload: boolean }
     T = L | R  

Post by LegionMammal978 » Thu, May 09, 2024, 4:50 PM UTC

CraigJPerry wrote: post #52

different_base wrote: post #3

One of the crimes of modern imperative programming languages is not having ADTs (except maybe Rust) built-in. It is such a basic mental model of how humans think and solve problems. But instead we got inheritance and enums which are practically very primitive.

>> not having ADTs (except maybe Rust) built-in Most of the common languages today have product types. Java[1], Rust, Haskell, etc. have sum types. I think it gets a bit more escoteric beyond that though - i don't doubt that there's probably some haskell extension for quotient types[2] or some other category theory high-jinx. Most languages have ADTs built in. [1] https://blogs.oracle.com/javamagazine/post/inside-the…

Post by gpderetta » Thu, May 09, 2024, 4:54 PM UTC

chongli wrote: post #61

Hirrolot wrote: post #57

Earlier quoted context omitted.

This is more of syntax sugar than power and generality, since nested pattern matching can be mechanically translated into "top-level" matching (e.g., see [1] and [2]). [1] L. Augustsson. Compiling Pattern Matching. In Functional Programming Languages and Computer Architecture, pages 368– 381, 1985. [2] P. Wadler. Efficient Compilation of Pattern Matching. In S.L. Peyton Jones, editor, The Implementation of Functional…

This argument is the most common fallacy I see in programming language discussions. I might as well give it a name right here: "Turing equivalence fallacy" or perhaps "syntax sugar fallacy." All Turing Complete programming languages are Turing equivalent to one another. Programs written in one language can be mechanically transformed into those written in another. This is irrelevant to the discussion of programming l…

Post by naasking » Thu, May 09, 2024, 4:56 PM UTC

taeric wrote: post #82

naasking wrote: post #60

Earlier quoted context omitted.

Verdex's explanation is detailed but too long IMO. The short version is that ADTs/sum types formally correspond to the OR-logical connective, and records/product types formally correspond to AND-logical connective. I think you'd be hard-pressed to argue that people don't think in terms of "X AND Y OR Z". These are core primitives of any kind of reasoning.

I can easily argue that people don't think in terms of boolean logic. For one, the evidence seems as strong that people generally think backwards from the answer far more than they do forwards from the ingredients. This is often why new things are so long to be discovered. It isn't that people couldn't have gotten there, but they didn't know to go for it. For two, addition is a wildly disparate thing everywhere we us…

Post by brabel » Thu, May 09, 2024, 5:02 PM UTC

nextaccountic wrote: post #70

CraigJPerry wrote: post #52

Earlier quoted context omitted.

>> not having ADTs (except maybe Rust) built-in Most of the common languages today have product types. Java[1], Rust, Haskell, etc. have sum types. I think it gets a bit more escoteric beyond that though - i don't doubt that there's probably some haskell extension for quotient types[2] or some other category theory high-jinx. Most languages have ADTs built in. [1] https://blogs.oracle.com/javamagazine/post/inside-the…

Does Java sealed classes enable something like an exhaustive pattern matching? (A form of pattern matching that will fail at compile time if you add a new class that extends the sealed class)

    sealed interface BinaryTree {
      record Leaf(int value) implements BinaryTree {}
      record Node(BinaryTree lhs,
                BinaryTree rhs,
                int value) implements BinaryTree {}
    }

    public class Hello {
      static int sum(BinaryTree tree) {
        return switch (tree) {
        case BinaryTree.Leaf(var value) -> value;
        case BinaryTree.Node(var lhs, var rhs, var value) -> sum(lhs) + value + sum(rhs);
        };
      }
    
      public static void main(String... args) {
        var tree = new BinaryTree.Node(
                                       new BinaryTree.Leaf(1),
                                       new BinaryTree.Node(
                                                           new BinaryTree.Leaf(2),
                                                           new BinaryTree.Leaf(3),
                                                           4),
                                       5);
        System.out.println(tree);
        System.out.println("Sum: " + sum(tree));
      }
    }