Question Est-ce toujours vrai: fmap (foldr f z). sequenceA = foldr (liftA2 f) (z pur)


import Prelude hiding (foldr)

import Control.Applicative
import Data.Foldable
import Data.Traversable

left, right :: (Applicative f, Traversable t) => (a -> b -> b) -> b -> t (f a) -> f b
left f z = fmap (foldr f z) . sequenceA
right f z = foldr (liftA2 f) (pure z)

Je soupçonne fortement que les expressions gauche et droite sont égales, mais comment le prouver?


14
2018-05-19 10:12


origine


Réponses:


Voici un début au moins:

\f z -> fmap (foldr f z) . sequenceA
== (definition of Foldable foldr)
\f z -> fmap (foldr f z . toList) . sequenceA
== (distributivity of fmap)
\f z -> fmap (foldr f z) . fmap toList . sequenceA
== (need to prove this step, but it seems intuitive to me)
\f z -> fmap (foldr f z) . sequenceA . toList

\f z -> foldr (liftA2 f) (pure z)
== (definition of Foldable foldr)
\f z -> foldr (liftA2 f) (pure z) . toList

Si vous pouvez prouver que fmap toList . sequenceA = sequenceA . toList, et que votre demande initiale est valable pour t = [] vous devriez être bon pour aller.


9
2018-05-19 12:22