Same LHS, different RHS in Haskell

user_9163262 0
Viewed 85

The exercise I need to solve is this:

Write a filter function for Foldable types using foldMap.

filterF 
    :: ( Applicative f
       , Foldable t
       , Monoid (f a)
       ) 
    => (a->Bool) -> t a -> f a
filterF=undefined

The function should return True for all of the following tests:

unit_testFilterF1 = filterF Data.Char.isUpper "aNA aRe mEre" == "NARE"
unit_testFilterF1 = filterF Data.Char.isUpper "aNA aRe mEre" == First (Just 'N')
unit_testFilterF1 = filterF Data.Char.isUpper "aNA aRe mEre" == Min 'A'
unit_testFilterF1 = filterF Data.Char.isUpper "aNA aRe mEre" == Max 'R'
unit_testFilterF1 = filterF Data.Char.isUpper "aNA aRe mEre" == Last (Just 'E')

Using the hints our teacher gave us, I wrote this solution:

filterF 
    :: ( Applicative f
       , Foldable t
       , Monoid (f a)
       ) 
    => (a-> Bool) -> t a -> f a
filterF funct u= foldMap (\x -> if funct x then pure x else mempty) u

Mind you, I obviously don't understand this solution fully, as I can't figure out why those tests return True. What I do understand is this:

  • filterF receives 2 arguments: funct (a function that takes an argument of type a and returns a Bool) and u (a foldable monoid)
  • We let funct decide, for every element in u, if it should stay or not. If it does stay, we "raise" it up to the "rank" of an Applicative with pure
  • we then combine all of the elements into one using the operation defined by the monoidal state of f

Given that in the tests we have the same LHS and different RHS, I would guess that the RHS influences the structure of f. A bit like how we would do in:

unit_testFilterF6=filterF Data.Char.isUpper"aNA aRe mEre" :: First Char

Can someone explain further what's going on here? I am a Haskell beginner.

haskell
1 Answers

Let's write f for (\x -> if funct x then pure x else mempty), when funct is Data.Char.isUpper.

We can evaluate filterF Data.Char.isUpper "aNA aRe mEre" as follows:

filterF Data.Char.isUpper "aNA aRe mEre"
= -- definition of filterF
folMap f "aNA aRe mEre"
= -- definition of foldMap
f 'a' <> f 'N' <> f 'A' <> f ' ' <> f 'a' <> f 'R' <> ....
= -- definition of f
mempty <> pure 'N' <> pure 'A' <> mempty <> mempty <> pure 'R' <> ...
= -- monoidal laws
pure 'N' <> pure 'A' <> pure 'R' <> pure 'E'

From here, using the definition of <> from the several monoids you mentioned, you should be able to conclude.

user_32349590
Related