News for hackers. Stuff that matters.
Re:The Algebra of Algebraic data types by sjolsen on Thursday June 25, 2015 @04:43AM (#9776635)
It's worth noting that if you take the expansion for List:

    L a = 𝟏 + a Γ— (L a)
        = 𝟏 + a + aΒ² + aΒ³ + β‹―
and substitute 𝟏 for a:

    L 𝟏 = 𝟏 + 𝟏 + 𝟏² + 𝟏³ + β‹―
        = 𝟏 + 𝟏 + 𝟏  + 𝟏  + β‹―
        = 𝟏 + (L 𝟏)
you get β„•:

    β„• = 𝟏 + β„•
The zero-power rule (x⁰ = 1) from classic algebra also holds; there is exactly one function from 𝟎 to any type (or in set-theoretic terms, from the empty set to any set).

There was an interesting paper on "closed semirings"[0] posted here a few days ago. Clearly, the product and coproduct on types form a semiring, and interestingly, List is the closure!

[0] http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf

Re:The Algebra of Algebraic data types by hiker on Thursday June 25, 2015 @04:47AM (#9776656)
The "Analytic Combinatorics"[1] book by Flajolet and Sedgewick is also relevant here.

[1] http://algo.inria.fr/flajolet/Publications/book.pdf

Re:The Algebra of Algebraic data types by tel on Thursday June 25, 2015 @01:23PM (#9779442)
Not to detract from your point, but you don't need the expansion for that. Directly substituting 𝟏 in the definitional equation works just fine:

    L a = 𝟏 + a Γ— (L a)
    L 𝟏 = 𝟏 + 𝟏 Γ— (L 𝟏)
    L 𝟏 = 𝟏 +     (L 𝟏)
    L 𝟏 = 𝟏 + 𝟏 + 𝟏 + 𝟏 + 𝟏 + 𝟏 + ...
    β„•   = 𝟏 + 𝟏 + 𝟏 + 𝟏 + 𝟏 + 𝟏 + ...
The final expansion is worth writing, however, since it notes how there are unboundedly many naturals, each a different component in this infinite disjoint sum.
Re:The Algebra of Algebraic data types by sjolsen on Thursday June 25, 2015 @10:26PM (#9782170)
>Not to detract from your point, but you don't need the expansion for that

I just used the expansion given in the parent. It also makes it apparent that List is the closure.

Re:The Algebra of Algebraic data types by tel on Thursday June 25, 2015 @11:11PM (#9782288)
That's true!
Re:The Algebra of Algebraic data types by bweitzman on Thursday June 25, 2015 @12:39PM (#9779152)
Actually I just realized that the law does not hold, the type `Void -> Maybe Void` has two inhabitants, not one:

f1 x = Nothing

f2 x = Just x

Re:The Algebra of Algebraic data types by wz1000 on Thursday June 25, 2015 @01:34PM (#9779510)
Both of them are regarded as the same function(ignoring bottom) because there is no way to differentiate between them as you can never supply them with a value of type Void in order to see their result.
Re:The Algebra of Algebraic data types by bweitzman on Thursday June 25, 2015 @04:50PM (#9780823)
They are similar in that they cannot be applied to any non-bottom value, but they are definitely not the same function.
Re:The Algebra of Algebraic data types by sjolsen on Thursday June 25, 2015 @10:53PM (#9782228)
>they are definitely not the same function

This depends on what equivalence you're using, and the only one in which it's true (definitional equality) isn't very interesting. Extensionally, the functions are identical.

Re:The Algebra of Algebraic data types by bweitzman on Friday June 26, 2015 @11:02AM (#9784911)
Ignoring, bottom, the functions arguably have no extensionality, and therefore are only vacuously equivalent in that sense.
Re:The Algebra of Algebraic data types by yummyfajitas on Thursday June 25, 2015 @01:22PM (#9779432)
`Just x` cannot be constructed since there is no `x` which is has type `Void`.
Re:The Algebra of Algebraic data types by tel on Thursday June 25, 2015 @02:09PM (#9779801)
Well, there's the one in context that does! Except this function can never be called in an empty context so you ultimately are stuck.
Re:The Algebra of Algebraic data types by bweitzman on Thursday June 25, 2015 @04:45PM (#9780803)
`Just x` can be constructed given an `x`. The fact that no `x` can be given is somewhat irrelevant to the definition of the function.
Re:The Algebra of Algebraic data types by bweitzman on Thursday June 25, 2015 @12:27PM (#9779058)
I love that 0^0 = 1 since you can define voidToVoid :: Void -> Void = id
Re:The Algebra of Algebraic data types by sjolsen on Thursday June 25, 2015 @11:12PM (#9782292)
You have to be careful when using Haskell for this sort of thing, because you can, for example, have a term of type Void:

    inhabitantOfZero :: Void
    inhabitantOfZero = fix id
(Side note: the empty type can also be interpreted as the type of non-terminating computations, and in fact typing 'fix id' into ghci will cause it to hang)

It turns out that 𝟎⁰ = 𝟏 is true, though, and if I'm not mistaken, this is true of semirings in general (where the exponent has a natural interpretation; of course you can define exponentiation this way for any semiring you like). This sole inhabitant is the empty function, which is easiest to explain in set-theoretic terms: if you define a function from A to B to be a subset of A Γ— B such that each a ∈ A appears exactly once (for example, the negation function on Bool would be the set {(true, false), (false, true)}), it's clear that there's exactly one function from the empty set to the empty set, because there is only one subset of βˆ… Γ— βˆ… (i.e., βˆ…) and for this set the above property is vacuously true.

For completeness, here's what the empty function looks like in Agda, which treats types much more carefully than Haskell (to understand why, look up intuitionistic logic/type theory and the Curry-Howard isomorphism):

    module EmptyFunction where
    
      data βŠ₯ : Set where
        -- No constructors, since βŠ₯ is empty
    
      inhabitant-of-𝟎⁰ : βŠ₯ β†’ βŠ₯
      inhabitant-of-𝟎⁰ ()
Re:The Algebra of Algebraic data types by bweitzman on Friday June 26, 2015 @10:58AM (#9784857)
Yeah, things start to break down when you include bottom (and fix id = _|_ since it diverges).

I'm not sure exactly how to work with polymorphism in the function as subset model you described, but I'm guessing it would be something like this:

Let id_A βŠ† A x A s.t for all a ∈ A, (a, a) ∈ id_A.

If A = βˆ…, then id_A = βˆ…, which is exactly the result we'd expect, so I don't see any issue.

> the empty type can also be interpreted as the type of non-terminating computations

This is true, in a sense, but also a little bit misleading I think, since technically every type in Haskell is the set of terminating value with that type plus _|_

Re:The Algebra of Algebraic data types by sjolsen on Friday June 26, 2015 @11:05PM (#9788939)
>If A = βˆ…, then id_A = βˆ…, which is exactly the result we'd expect, so I don't see any issue.

The issue isn't with the example you gave, but with the idea in general that being able to produce a term of a given type in Haskell means that that type is necessarily inhabited.

>This is true, in a sense, but also a little bit misleading I think, since technically every type in Haskell is the set of terminating value with that type plus _|_

Well, βŠ₯ is empty, so naturally every type is itself plus βŠ₯. In fact, that leads to an important observation, which is that any computation in Haskell could potentially be non-terminating, not just those with type Voidβ€”and so it's really not the inclusion of the bottom type that causes things to break down, but the ability to produce non-terminating computations (more specifically, non-coterminating, i.e. non-productive "lazy" computations).

Unfortunately, the alternativeβ€”making it impossible to produce non-terminating computationsβ€”is more than anything a matter of rejecting everything the compiler can't prove terminates, which is kind of limiting, termination being undecidable in the general case. On the other hand, the sorts of computations humans design are generally much more well-structured than an arbitrary Turing machine, and so probably much easier to prove (co)termination for.