[Haskell-cafe] Producing MinimumValue

Dan Weston westondan at imageworks.com
Thu Jul 19 15:41:44 EDT 2007


The standard (and simplest) definition for universally quantified 
predicates (all) starts with True and looks for a False occurrance:

Prelude> all even []
True

Conversely, existentially-quantified predicates (any) start with False 
and looks for a True occurrance:

Prelude> any even []
False

I would define:

allEqual []         = True
allEqual [_]        = True
allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs

As a purely stylistic note, (per a previous mail thread) you don't need 
to worry about the order that mutually-exclusive patterns are listed, so 
I find it clearer to put the base case of an induction first, so I don't 
forget it.

Dan

Alexteslin wrote:
> I have defined the first line it seems right to me but second line not sure. 
> I have True or False and whatever value i give it produces that value.
> 
> allEqual :: [Int] -> Bool
> allEqual (x1:x2:xs) = (x1 == x2) && allEqual xs
> allEqual _          = ???
> 
> 
> 
> Steve Schafer wrote:
>> On Thu, 19 Jul 2007 10:55:19 -0700 (PDT), you wrote:
>>
>>> The question suggests to use some functions defined in the section, and
> one
>>> of them is iSort.
>> Aha. Well, that one certainly lends itself better to this particular
>> proplen than either map or filter.
>>
>>> minimumValue :: [Int] -> Int
>>> minimumValue ns = head (iSort ns)
>> If I were going to use a sort, then yes, that's the way I would do it.
>> Of course, sorting isn't the best way to solve the problem, as sorting
>> will always be at least O(n * log n), whereas a more straightforward
>> algorithm would be O(n).
>>
>>> The other question is to test whether the values of allEqual on inputs 0
> to
>>> n are all equal.  Again, I defined the method but not sure if its concise?
>>>
>>> allEqual :: [Int] -> Bool
>>> allEqual xs = length xs == length (filter isEqual xs)
>>> 	where
>>> 	isEqual n = (head xs) == n
>> Simple recursion is probably the most conceptually straightforward
>> approach here. One little difficulty with this problem (and with
>> minimumValue, too) is that the problem isn't completely specified,
>> because we don't know what answer we're supposed to give when the list
>> is empty. Let's assume that allEqual is supposed to return True on an
>> empty list. In that case, we can write it like this:
>>
>>  allEqual :: [Int] -> Bool
>>  allEqual (x1:x2:xs) = ???
>>  allEqual _          = ???
>>
>> where the two ???s are left as an exercise for the reader.
>>
>> -Steve
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>>
> 




More information about the Haskell-Cafe mailing list