Jeśli dobrze rozumiem twoje przykłady, typy są ai -> b -> ai
, a nie ai -> b -> a
, tak jak napisałeś po raz pierwszy. Przeredagujmy typy na a -> ri -> ri
, tylko dlatego, że pomaga mi myśleć.
Pierwszą rzeczą obserwować jest to korespondencja:
(a -> r1 -> r1, ..., a -> rn -> rn) ~ a -> (r1 -> r1, ..., rn -> rn)
To pozwala na pisanie tych dwóch funkcji, które są odwrotne:
pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (r1 -> r1, r2 -> r2)
pullArg (f, g) = \a -> (f a, g a)
pushArg :: (a -> (r1 -> r1, r2 -> r2)) -> (a -> r1 -> r1, a -> r2 -> r2)
pushArg f = (\a -> fst (f a), \a -> snd (f a))
Drugie spostrzeżenie: typy postaci ri -> ri
są czasami nazywane endomorfizmów, a każdy z tych typów ma monoid z kompozycją jako operacją asocjacyjną i funkcją tożsamości jako tożsamością. Pakiet Data.Monoid
ma to opakowanie na to:
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = id
mappend = (.)
To pozwala Ci przepisać wcześniejszy pullArg
do tego:
pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> (Endo r1, Endo r2)
pullArg (f, g) = \a -> (Endo $ f a, Endo $ g a)
Trzecie spostrzeżenie: iloczyn dwóch monoids również monoid, jak na to przykład również z Data.Monoid
:
instance (Monoid a, Monoid b) => Monoid (a, b) where
mempty = (mempty, mempty)
(a, b) `mappend` (c, d) = (a `mappend` c, b `mappend d)
Podobnie na krotki dowolną liczbę argumentów.
Czwarte spostrzeżenie: What are folds made of? Odpowiedź: folds are made of monoids!
import Data.Monoid
fold :: Monoid m => (a -> m) -> [a] -> m
fold f = mconcat . map f
Ten fold
jest tylko specjalizacja foldMap
z Data.Foldable
, więc w rzeczywistości nie musimy go zdefiniować, możemy po prostu importować jej bardziej ogólną wersję:
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
Jeśli fold
z Endo
, że jest taka sama jak składane z prawej strony.Spasować z lewej chcesz spasować z Dual (Endo r)
monoid:
myfoldl :: (a -> Dual (Endo r)) -> r -> -> [a] -> r
myfoldl f z xs = appEndo (getDual (fold f xs)) z
-- From `Data.Monoid`. This just flips the order of `mappend`.
newtype Dual m = Dual { getDual :: m }
instance Monoid m => Monoid (Dual m) where
mempty = Dual mempty
Dual a `mappend` Dual b = Dual $ b `mappend` a
Pamiętaj naszą pullArg
funkcję? Załóżmy zmienić go nieco więcej, ponieważ jesteś składane od lewej:
pullArg :: (a -> r1 -> r1, a -> r2 -> r2) -> a -> Dual (Endo r1, Endo r2)
pullArg (f, g) = \a -> Dual (Endo $ f a, Endo $ g a)
i to, że twierdzą, jest to wersja 2-krotnym swoimi f
lub przynajmniej izomorficzna do niego. Można byłaby swoje funkcje krotnie w postaci a -> Endo ri
, a następnie wykonaj:
let (f'1, ..., f'n) = foldMap (pullArgn f1 ... fn) xs
in (f'1 z1, ..., f'n zn)
Warto także patrząc na: Composable Streaming Folds, który jest ponadto opracowanie tych pomysłów.
Myślę, że istnieje rozwiązanie przy użyciu Arrow's *** i &&&, używając typów takich jak (f, (g, (h, i)) zamiast (f, g, h, i) pod maską, ale ja ' kilkaset mil od mojego laptopa, więc nie mogę dziś zagrać. – AndrewC