[Haskell-cafe] Re: Wrong Answer Computing Graph Dominators
ChrisK
haskell at list.mightyreason.com
Fri Apr 18 07:52:07 EDT 2008
More algebraically, including 'or' for symmtry:
and xs = foldr (&&) True xs
or xs = foldr (||) False xs
The True and False are the (monoid) identities with respect to && and || :
True && x == x
x && True == x
False || x == x
x || False == x
And so an empty list, if defined at all, should be the identity:
and [] = True
or [] = False
In english:
"and returns false" when "is any element of the list false?" is yes
"or returns true" when "is any element of the list true?" is yes
Matthew Brecknell wrote:
> Dan Weston wrote:
>> Here, "any path" means all paths, a logical conjunction:
>>
>> and [True, True] = True
>> and [True ] = True
>> and [ ] = True
>
> Kim-Ee Yeoh wrote:
>> Hate to nitpick, but what appears to be some kind of a
>> limit in the opposite direction is a curious way of arguing
>> that: and [] = True.
>>
>> Surely one can also write
>>
>> and [False, False] = False
>> and [False ] = False
>> and [ ] = False ???
>
> No. I think what Dan meant was that for all non-null
> xs :: [Bool], it is clearly true that:
>
> and (True:xs) == and xs -- (1)
>
> It therefore makes sense to define (1) to hold also
> for empty lists, and since it is also true that:
>
> and (True:[]) == True
>
> We obtain:
>
> and [] == True
>
> Since we can't make any similar claim about the
> conjuctions of lists beginning with False, there
> is no reasonable argument to the contrary.
More information about the Haskell-Cafe
mailing list