[Haskell-cafe] Re: Wrong Answer Computing Graph Dominators

[ChrisK]

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.