看似合法的Eta减少导致问题

Question

我试图η-减少功能

foldr :: (a -> b -> b) -> b -> BinaryTree a -> b
foldr combiner base tree = foldMap combiner tree base where
  foldMap = ...

同

foldMap :: (a -> b -> b) -> BinaryTree a -> b -> b

按预期工作.

我减少了η

foldr combiner base tree = foldMap combiner tree base

至

foldr combiner = flip $ foldMap combiner where
  ...

这按预期工作.看起来我应该能够完全η-reduce以获得无点功能

foldr = flip $ foldMap where
  ...

但是,这会导致编译错误

Couldn't match type ‘a -> b -> b’ with ‘BinaryTree t0’
Expected type: (a -> b -> b) -> b -> BinaryTree a -> b
  Actual type: BinaryTree t0 -> (t0 -> b -> b) -> b -> b

有可能η-减少更远,如果是这样,怎么样？

Answer 1

引发错误,因为g b = f $ a b不等同于g = f $ a.

在第一种情况下,您将获得以下评估顺序:

• 应用功能a于b(调用a具有b作为参数)
• 将函数f应用于结果

在第二种情况:

• 将功能f应用于a

因此,你刚才flip的foldMap功能,但实际上要flip的foldMap功能后传递combiner给它.这导致我们得出结论,你实际上想要的是组合,即.功能:

foldr = flip . foldMap where
  ...