如何正确应用foldr功能

Question

我试图找到列表的最大元素，其中元素是我自己创建的数据类型，使用折叠而不是递归地进行。但是我最终遇到错误 "couldn't match type"。由于我是 haskell 的新手，我无法理解问题并希望知道如何正确应用 foldr 函数。

我尝试获取最大的元素是这样的：

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

无法编译。

我已经包括了 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 列表后我的预期结果是获得 'largest car' ，这基本上意味着时间最长的汽车。但是由于类型错误，我最终遇到了编译错误。

Answer 1

问题是 comparison 的类型和定义。

首先，类型应该是 Car -> Car -> Car：你取两个 Car 个值和 return 个较大的值。

其次，您对 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

而且，正如 Robin Zigmond 指出的那样，foldr comparison x 基本上是 maximum 的适当值 x。）

Answer 2

考虑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.

获得

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

如何正确应用foldr功能

how to correctly apply the foldr function

syntax

haskell

fold