CODEWITHSUNDEEP
haskellsyntaxfold
kalle konsida
kalle konsida

Reputation: 333

how to correctly apply the foldr function

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.

Upvotes: 1

Views: 860

Answers (2)

Greg Bacon
Greg Bacon

Reputation: 139611

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.

Upvotes: 1

chepner
chepner

Reputation: 531808

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.)

Upvotes: 3

Related Questions