problème de composition filtre / Carte Haskell

Question

On m'a donné cette question dans un tutoriel, et je ne sais vraiment pas comment s'y prendre.

  

Comment doit g et h définir en termes de p et f afin de faire en sorte que
  filter p . map f = map g . filter h
  détient toujours?

Les pointeurs dans la bonne direction serait grandement apprécié.

Answer 1

Il est clair que f :: a -> b et p :: b -> Bool. Puisque nous ne pouvons pas faire d'autres hypothèses sur f et g, on devra définir

h = p . f
g = f

h :: a -> Bool et g :: a -> b.

Answer 2

Pensez à des types.

f :: a -> b
g :: a -> b
p :: b -> Bool
h :: a -> Bool

Answer 3

Une autre façon de voir ceci:

map g (filter h A) est le {g(a) : with h(a) is true and a is elt from A} de consigne

filter p (map f A) est le {f(a) : with p(f(a) is true and a is elt from A} de consigne

Pour ces ensembles soient égaux, nous devons choisir f = g et h(a) = p(f(a)).