[Haskell-cafe] and [] = True; or [] = False

[Bjorn Buckwalter]

Ok Guys, you've convinced me thrice within ten minutes of posing my
question. The quality of the mailing list is just ridiculous! ;)

And Miguel, thanks for the follow-up regarding "for all" and "exists"
– it's an excellent analogy and easy to remember!


On Mon, Apr 26, 2010 at 20:23, Jochem Berndsen <jochem at functor.nl> wrote:
> Bjorn Buckwalter wrote:
>> Dear all,
>>
>> Does it make good sense that 'and []' returns 'True' and 'or []'
>> returns 'False'? The Haskell Road to Logic, Maths and Programming says
>> so:
>>
>> "The function or takes a list of truth values and returns True if at
>> least one member of the list equals True, while and takes a list of
>> truth values and returns True if all members of the list equal True."
>>
>> "Should the conjunction of all elements of [] count as true or false?
>> As true, for it is indeed (trivially) the case that all elements of []
>> are true. So the identity element for conjunction is True. Should the
>> disjunction of all elements of [] count as true or false? As false,
>> for it is false that [] contains an element which is true. Therefore,
>> the identity element for disjunction is False."
>>
>> While the above reasoning is fine, and allows straight-forward
>> implementations, it isn't extremely convincing. In particular, it
>> isn't clear that, while simple, the definitions of the first paragraph
>> are the most sensible. Perhaps one of the more mathematically versed
>> readers on the Cafe could enlighten me?
>
> The empty sum is regarded to be zero. The empty product is equal to one.
> The empty conjunction is True. The empty disjunction is False.
>
> The reason for this is that these are the neutral elements, i.e.
>  0 + x = x
>  1 * x = x
>  True AND x = x
>  False OR x = x
>
> This allows some laws to hold also in degenerate cases, and it is quite
> useful in general to accept these conventions. An example of such a law is
> (∀ x : x ∈ A : P(x)) ∧ (∀ x : x ∈ B : P(x))
>  ==
> (∀ x : x ∈ A ∪ B : P(x)).
>
> This also works if A or B is empty, provided that we say that the empty
> conjunction is true.
>
> In Haskell, we now have that
>
> (and xs) && (and ys)
>  ==
> and (xs ++ ys),
>
> even if xs or ys is the empty list.
>
> Cheers, Jochem
> --
> Jochem Berndsen | jochem at functor.nl
>