• 0 Posts
  • 14 Comments
Joined 1 year ago
cake
Cake day: June 20th, 2023

help-circle









  • As you already figured out the types are sets with a certain number of elements.

    Two types are isomorphic if you can write a function that converts all elements of the first one into the elements of the second one and a function which does the reverse. You can then use this as the equality.

    The types with the same number of elements are isomorphic, i.e True | False = Left | Right. For example, you can write a function that converts True to Left, False to Right, and a function that does the reverse.

    Therefore you essentially only need types 0, 1, 2, 3, …, where type 0 has 0 elements, type 1 has 1 element, etc. and all others are isomorphic to one of these.

    Let’s use (*) for the product and (+) for the sum, and letters for generic types. Then you can essentially manipulate types as natural numbers (the same laws hold, associativity, commutativity, identity elements, distributivity).

    For example:

    2 = 1 + 1 can be interpreted as Bool = True | False

    2 * 1 = 2 can be interpreted as (Bool, Unit) = Bool

    2 * x = x + x can be interpreted as (Bool, x) = This of x | That of x

    o(x) = x + 1 can be interpreted as Option x = Some of x | None

    l(x) = o(x * l(x)) = x * l(x) + 1 can be interpreted as List x = Option (x, List x)

    l(x) = x * l(x) + 1 = x * (x * l(x) + 1) + 1 = x * x * l(x) + x + 1 = x * x * (l(x) + 1) + x + 1 = x * x * l(x) + x * x + x + 1 so a list is either empty, has 1 element or 2 elements, … (if you keep substituting)

    For the expression problem, read this paper: doi:10.1007/BFb0019443






  • Nope. Monads enable you to redefine how statements work.

    Let’s say you have a program and use an Error[T] data type which can either be Ok {Value: T} or Error:

    var a = new Ok {Value = 1};
    var b = foo();
    return new Ok {Value = (a + b)};
    

    Each statement has the following form:

    var a = expr;
    rest
    

    You first evaluate the “expr” part and bind/store the result in variable a, and evaluate the “rest” of the program.

    You could represent the same thing using an anonymous function you evaluate right away:

    (a => rest)(expr);
    

    In a normal statement you just pass the result of “expr” to the function directly. The monad allows you to redefine that part.

    You instead write:

    bind((a => rest), expr);
    

    Here “bind” redefines how the result of expr is passed to the anonymous function.

    If you implement bind as:

    B bind(Func[A, B] f, A result_expr) {
       return f(result_expr);
    }
    

    Then you get normal statements.

    If you implement bind as:

    Error[B] bind(Func[A, Error[B]] f, Error[A] result_expr) {
       switch (result_expr) {
           case Ok { Value: var a}:
               return f(a);
           case Error:
               return Error;
       }
    }
    

    You get statements with error handling.

    So in an above example if the result of foo() is Error, the result of the statement is Error and the rest of the program is not evaluated. Otherwise, if the result of foo() is Ok {Value = 3}, you pass 3 to the rest of the program and you get a final result Ok {Value = 4}.

    So the whole idea is that you hide the if Error part by redefining how the statements are interpreted.