как правильно применить функцию Foldr - PullRequest
Новая
       17

как правильно применить функцию Foldr

0 голосов
/ 05 февраля 2019

Я пытаюсь найти максимальный элемент списка, где элементы представляют собой тип данных, созданный мной, используя сгиб вместо рекурсивного.Однако я в конечном итоге с ошибкой «не может соответствовать типу».Поскольку я довольно новичок в haskell, у меня возникли проблемы с видением проблемы и я хочу знать, как правильно применять функцию foldr.

Моя попытка получить самые большие элементы выглядит следующим образом:

- (сравнение сгибов (список заголовков) (список хвостов))

, который не будет компилироваться.

Я включил тип данных и его экземпляры для Eq и Ord, а также включил функцию сравнения. 

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

Мой ожидаемый результат после сворачивания списка Car заключается в получении«самый большой автомобиль», что в основном означает автомобиль с наибольшим временем.Но я получаю ошибку компиляции из-за неправильного типа.

Ответы [ 2 ]

0 голосов
/ 07 февраля 2019

Рассмотрим упрощенный тип foldr. 

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

Это гораздо более общий вопрос, чем требуется, поскольку вы имеете дело со всеми автомобилями.Это означает, что для поиска наибольшего Car с foldr типом становится 

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

Первый аргумент - это функция, которая выбирает между двумя машинами.В вашем случае вы хотите max, потому что его тип 

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

становится 

max :: Car -> Car -> Car

и точно соответствует.

Второй аргумент foldr называетсяz для нуля.Это семя для процесса складывания.Для этого вы также можете использовать первый элемент вашего списка, полученный с помощью head.

Аргумент list типа [Car] - это, очевидно, список, максимум которого вы хотите вычислить.Вы можете передать весь список, но заголовок уже считается аргументом z.Лучше было бы tail list.

Учитывая следующий список (после изменения Car для удаления tupleForm и получения Show экземпляра) 

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

, находя максимум с помощью foldr - это 

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

Обратите внимание, что это приложение foldr эквивалентно maximum, но вы не обязаны верить мне на слово.Добавление 

import Test.QuickCheck

в начало исходного файла, а затем 

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)

дает больше уверенности в утверждении. 

λ> quickCheck prop_max
+++ OK, passed 100 tests.
0 голосов
/ 05 февраля 2019

Проблема в типе и определении comparison.

Во-первых, тип должен быть Car -> Car -> Car: вы берете два Car значений и возвращаете большее.

Во-вторых, ваше определение comparison пытаетсядля сопоставления одного аргумента в виде кортежа, а не двух отдельных аргументов.Скиньте скобки и запятую. 

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

(Конечно, comparison это просто max, ограничено Car, а не Ord a => a. 

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

И,как указывает Робин Зигмонд, foldr comparison x в основном maximum для соответствующего значения x.)

...