[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