1

Im attempting to find the max element of a list, where the elements are a data type created by myself, using a fold instead of doing it recursively. However i end up with an error "couldn't match type". As im fairly new to haskell im having trouble seeing the problem and wish to know how to correctly apply the foldr function.

My attempt at obtaining the largest elements looks like this:

-- (foldr comparison (head list) (tail list))

which won't compile.

i have included the datatype and its instances for Eq and Ord, and i've also included the comparison function.

 -- Car data type

 data Car = Car {registration :: String,
                    hour :: Integer, 
                  minute :: Integer, 
               tupleForm :: PTime
           }

-- Equality comparison between Car data types
-- reqiures equality by registration number, hours and minutes

instance Eq Car where 
     (Car r1 h1 m1 _) == (Car r2 h2 m2 _) = (r1 == r2) && (((h1*60)+m1) == 
((h2*60)+m2))

-- Order comparison between Car data types
-- Compares time of two Cars , hours and minutes 

instance Ord Car where 
     compare (Car _ h1 m1 _) (Car _ h2 m2 _) = compare ((h1*60)+m1) 
     ((h2*60)+m2)  


-- Returns the larger Car
comparison :: (Car,Car) -> Car
comparison(car1,car2) = if(car1 > car2) then car1 else car2

My expected result after folding the list of Car is to obtain the 'largest car' ,which basically means the car with the largest time. But I end up with a compilation error due to faulty type.

Improve this question
2
  • 2
    Once you've made a type an instance of Ord, as you have here, you get a maximum function "for free". So you don't need to implement your own. (If you want to for practice, you should probably use foldr1 rather than just foldr, because it doesn't make a lot of sense to find the maximum of an empty list). Commented Feb 5, 2019 at 14:38
  • did not think about the maximum function, how nice! I'll use it instead of folding, but i'll leave the question up for future references on how to fold something like this correctly seeing how im unable to figure out what whent wrong. @RobinZigmond much appreciated! Commented Feb 5, 2019 at 14:44

2 Answers 2

Reset to default
3

The problem is the type and definition of comparison.

First, the type should be Car -> Car -> Car: you take two Car values and return the bigger one.

Second, your definition of comparison tries to match a single argument as a tuple, rather than two separate arguments. Drop the parentheses and the comma.

comparison :: Car -> Car -> Car
comparison car1 car2 = if car1 > car2 then car1 else car2

(Of course, comparison is just max restricted to Car rather than Ord a => a.

comparison :: Car -> Car -> Car
comparison = max

And, as Robin Zigmond points out, foldr comparison x is basically maximum for an appropriate value x.)

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

i mustve uploaded the wrong version of comparison because i originally passed a pair of Car as argument. But seeing your answer i understand that it wasn't a tuple pair it wanted. thx!
You could define comparison' :: (Car, Car) -> Car, comparison' (car1, car2) = <same definition as before>, but that's not idiomatic. (However, the two are isomorphic, as comparison == curry comparison' and comparison' == uncurry comparison.)
just to clarify - I was referring to maximum in reference to what it seemed the OP was trying to implement with the foldr, to get the maximum of a list according to the defined ordering. Of course you're right to point out that the comparison shown here is just uncurry max
Ah, OK. I assumed you made the same mistake I usually make, which is to confuse which of maximum and max takes a list (er, Foldable) and which takes two explicit values. :)
@RobinZigmond I've edited my answer to try to put more accurate words in your mouth :)
|
1

Consider the simplified type of foldr.

foldr :: (a -> b -> b) -> b -> [a] -> b

This is a lot more general than you require because you’re dealing with all Cars. That means to find the biggest Car with foldr, the type becomes

foldr :: (Car -> Car -> Car) -> Car -> [Car] -> Car

The first argument is a function that selects between two Cars. In your case, you want max because its type

max :: Ord a => a -> a -> a

becomes

max :: Car -> Car -> Car

and matches exactly.

The second argument to foldr is named z for zero. It is the seed for the folding process. For this, you may as well use the first element of your list, obtained with head.

The list argument of type [Car] is obviously the list whose maximum you want to compute. You could pass the entire list, but the head is already accounted for as the z argument. Better would be tail list.

Given the following list (after modifying Car to remove tupleForm and derive a Show instance)

cars = [ Car "A" 1 2, Car "B" 3 4, Car "C" 10 10 ]

finding the maximum with foldr is

λ> foldr max (head cars) (tail cars)
Car {registration = "C", hour = 10, minute = 10}

Note that this application of foldr is equivalent to maximum, but you don’t have to take my word for it. Adding

import Test.QuickCheck

to the top of your source file and then

prop_max :: [Car] -> Property
prop_max l =
  not (null l) ==>
    maximum l == foldr max (head l) (tail l)

instance Arbitrary Car where
  arbitrary = do
    r <- oneof $ map return ["Apple","Orange","Banana"]
    h <- choose (0,23)
    m <- choose (0,59)
    return (Car r h m)

gives more confidence in the assertion.

λ> quickCheck prop_max
+++ OK, passed 100 tests.
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.