关于 Haskell 中执行的函数组合顺序

Question

我很难理解这个例子：

data Row = R [Int]
deriving Show
data Matrix = M [Row]
deriving Show
check :: Matrix -> Int -> Bool
check (M matrix) n = foldr ((&&) . ((R row) -> length row == n)) True matrix

test1 = check (M[R[1,2,3], R[4,5], R[2,3,6,8], R[8,5,3]]) 3 == False

我有一个名为Row的数据类型，其中包含整数列表，Matrix数据类型包含行列表。我必须检查我的函数是否所有行的长度都等于第二个参数n.我真的不明白为什么这种foldr有效。让我们看看test1.它从做((&&) . (lambda)) R[8, 5, 3] True开始 现在不是，某种 (f.g) x y 是 f (g x y) 吗？如果是这样，结果将是&&(lambda R[8, 5, 3] True)<->&& (True True)，并且 paran中的表达式不是首先评估(True True)，它应该给我一个错误吗？请让我了解执行顺序是什么，我错在哪里。

Answer 1

首先，让我们记住foldr的作用： 它接受函数f、列表xn = [x1, x2, ..., xn]和起始值s并生成表达式

f x1 (f x2 (... (f xn s) ...))

或等效

f x1 $ f x2 $ ... $ f xn $ s

函数组合(.)首先应用右侧函数，然后应用左侧函数，因此首先是您的 lambda 表达式，我们现在checkRow调用该表达式，然后(&&)。这导致

(&&) (checkRow x1) $ (&&) (checkRow x2) $ ... $ (&&) (checkRow xn) $ True

插入True作为起始值时。

这可以用中缀表示法重写为

(checkRow x1) && (checkRow x2) && ... (checkRow xn) && True

编辑：关于函数组合在这种情况下如何工作，请查看类型：

(.) :: (b -> c) -> (a -> b) -> a -> c

请记住，(&&)可以被视为返回另一个(在本例中为一元)函数的一元函数，并遵循以下类型：

(Bool -> (Bool -> Bool)) -> (Row -> Bool) -> Row -> Bool -> Bool
(&&) . checkRow :: Row -> Bool -> Bool

所以(&&)和checkRow的组合是一个函数，它接受一个Row和一个Bool并返回一个Bool。因此，右侧函数应用于第一个输入参数，结果作为第二个函数的第一个输入参数转发。但是，第二个函数可以接受多个参数。

这与foldr类型非常吻合：

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

或在您的情况下

(Row -> Bool -> Bool) -> Bool -> [Row] -> Bool

Answer 2

您的问题似乎与理解折叠中使用的函数实际作用有关：

(&&) . ((R row) -> length row == n)

确实，这有点神秘。让我们尝试以等效的形式重写它。根据组合的定义，a.b意味着x -> a (b x)，因此我们得到

x -> (&&) ( ((R row) -> length row == n) x )

这看起来仍然很奇怪，因为我们希望&&应用于两个参数。我们可以 eta-expand：f相当于y -> f y。我们得到

x -> y -> (&&) ( ((R row) -> length row == n) x ) y

这意味着

x y ->  ( ((R row) -> length row == n) x ) && y

注意类型：此处x :: Row，而y :: Bool。我们可以等价地将上述内容重写为

(R row) y ->  length row == n && y

这意味着折叠

foldr ((&&) . ((R row) -> length row == n)) True [Row r1, Row r2, ...]

简化为

length r1 == n && (length r2 == n && ... (... && True))

这相当于检查所有行的长度是否相同n.