CODEWITHSUNDEEP
haskellpointfree
LVFToENlCx
LVFToENlCx

Reputation: 875

Seemingly legal Eta reduction causing issues

I am attempting to η-reduce the function

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

with 

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

working as intended.

I have η-reduced 

foldr combiner base tree = foldMap combiner tree base

to 

foldr combiner = flip $ foldMap combiner where
  ...

This works as intended. It seems like I should be able to η-reduce completely to get the pointfree function

foldr = flip $ foldMap where
  ...

However, this causes a compilation error

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

Is it possible to η-reduce farther, and if so, how?

Upvotes: 6

Views: 124

Answers (1)

Igor Drozdov
Igor Drozdov

Reputation: 15045

The error is raised, because g b = f $ a b is not equivalent to g = f $ a.

In the first case you get the following sequence of evaluation:

  • apply the function a to b (call a with b as an argument)
  • apply the function f to the result

In the second case:

  • apply the function f to a

Thus, you just flip the foldMap function, but actually want to flip the foldMap function after passing combiner to it. This leads us to the conclusion, that you actually want the composition, i. e. . function:

foldr = flip . foldMap where
  ...

Upvotes: 10

Related Questions