Wie wird über das Applikativformular abgebildet?

Question

Ich möchte über das Applikative Formular mappen.

Der Typ der map-ähnlichen Funktion wäre wie folgt:

mapX :: (Applicative f) => (f a -> f b) -> f [a] -> f [b]

verwendet als:

result :: (Applicative f) => f [b]
result = mapX f xs
  where f  :: f a -> f b
        f = ...
        xs :: f[a]
        xs = ...

Im Hintergrund dieses Beitrags versuche ich, ein Fluidsimulationsprogramm im Applicative-Stil zu schreiben, unter Bezugnahme auf Paul Haduks "The Haskell School of Expression", und ich möchte die Simulation mit dem Applicative-Stil wie folgt ausdrücken:

x, v, a :: Sim VArray
x = x0 +: integral (v * dt)
v = v0 +: integral (a * dt)
a = (... Berechnung der Beschleunigung mit x v ...)

instance Applicative Sim where
  ...

wo der Typ Sim den Prozess der Simulationsberechnung bedeutet und VArray Array von Vektoren (x, y, z) bedeutet. X, v a sind die Arrays der Position, Geschwindigkeit und Beschleunigung, bzw.

Das Mapping über die Applikative Form erfolgt bei der Definition von a.

---

Ich habe eine Antwort auf meine Frage gefunden.

Im Endeffekt stellt sich meine Frage "Wie kann man Hochordnungsfunktionen (wie map :: (a -> b) -> [a] -> [b]) in die Applikative Welt überführen?" und die Antwort, die ich gefunden habe, ist "Sie mit angehobenen Funktionen erster Ordnung zu bauen."

Zum Beispiel wird "mapX" mit angehobenen Funktionen erster Ordnung (headA, tailA, consA, nullA, condA) wie folgt definiert:

mapX :: (f a -> f b) -> f [a] -> f [b]
mapX f xs0 = condA (nullA xs0) (pure []) (consA (f x) (mapA f xs))
 where
   x = headA xs0
   xs = tailA xs0

headA = liftA head

tailA = liftA tail

consA = liftA2 (:)

nullA = liftA null

condA b t e = liftA3 aux b t e
  where aux b t e = if b then t else e

Answer 1

Zunächst denke ich nicht, dass Ihre vorgeschlagene Typsignatur viel Sinn macht. Angesichts einer applikativen Liste f [a] gibt es keine allgemeine Möglichkeit, das in [f a] umzuwandeln – daher besteht kein Bedarf an einer Funktion vom Typ f a -> f b. Um des Verstandes willen werden wir diese Funktion auf a -> f b reduzieren (um sie in die andere umzuwandeln ist trivial, aber nur wenn f ein Monad ist).

Jetzt wollen wir also:

mapX :: (Applicative f) => (a -> f b) -> f [a] -> f [b]

Was jetzt sofort in den Sinn kommt, ist traverse, was eine Verallgemeinerung von mapM ist. Traverse, spezialisiert auf Listen:

traverse :: (Applicative f) => (a -> f b) -> [a] -> f [b]

Nahe dran, aber kein Zigarre. Nochmals, wir können traverse auf die erforderliche Typsignatur anheben, aber das erfordert eine Monad-Beschränkung: mapX f xs = xs >>= traverse f.

Wenn Ihnen die Monad-Beschränkung nichts ausmacht, ist das in Ordnung (und tatsächlich können Sie das auch einfach mit mapM erledigen). Wenn Sie sich auf Applikative beschränken müssen, dann sollte dies ausreichen, um zu veranschaulichen, warum Ihre vorgeschlagene Signatur nicht wirklich möglich ist.

Bearbeiten: basierend auf weiteren Informationen, so würde ich das grundlegende Problem angehen.

-- Ihre Skizze
a = liftA sum $ mapX aux $ liftA2 neighbors (x!i) nbr 
   where aux :: f Int -> f Vector3
   -- der Typ von "liftA2 neighbors (x!i) nbr" ist "f [Int]

-- meine Interpretation
a = liftA2 aux x v
    where
       aux :: VArray -> VArray -> VArray 
       aux xi vi = ...

Wenn Sie aux nicht so schreiben können – als reine Funktion von den Positionen und Geschwindigkeiten zu einem Zeitpunkt zu den Beschleunigungen, dann haben Sie größere Probleme...

Hier ist eine intuitive Skizze, warum. Der Stream-Applikativ-Functor nimmt einen Wert und hebt ihn in einen Wert über die Zeit – eine Sequenz oder einen Strom von Werten. Wenn Sie Zugriff auf einen Wert über die Zeit haben, können Sie Eigenschaften davon ableiten. Also Geschwindigkeit kann in Bezug auf Beschleunigung definiert werden, Position kann in Bezug auf Geschwindigkeit definiert werden, und so weiter. Toll! Aber jetzt wollen Sie die Beschleunigung in Bezug auf Position und Geschwindigkeit definieren. Auch toll! Aber Sie sollten in diesem Fall nicht die Beschleunigung in Bezug auf Geschwindigkeit über die Zeit definieren müssen. Warum, mag man fragen? Weil Geschwindigkeit über die Zeit alles ist, was Beschleunigung so oder so ist. Also, wenn Sie a in Bezug auf dv definieren, und v in Bezug auf integral(a), dann haben Sie eine geschlossene Schleife, und Ihre Gleichungen sind nicht ordnungsgemäß bestimmt – entweder gibt es selbst bei gegebenen Anfangsbedingungen unendlich viele Lösungen oder es gibt überhaupt keine Lösungen.

Answer 2

Wenn ich das richtig durchdenke, können Sie dies nicht nur mit einem applikativen Funktor tun; Sie werden einen Monaden brauchen. Wenn Sie eine Applicative haben - nennen wir sie f -, stehen Ihnen die folgenden drei Funktionen zur Verfügung:

fmap  :: (a -> b) -> f a -> f b
pure  :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

Also, was können Sie mit einem f :: f a -> f b tun? Nun, wenn Sie einige xs :: [a] haben, können Sie diese übertragen: map (f . pure) xs :: [f b]. Und wenn Sie stattdessen fxs :: f [a] haben, könnten Sie stattdessen fmap (map (f . pure)) fxs :: f [f b].1 Aber hier stecken Sie fest. Sie wollen eine Funktion vom Typ [f b] -> f [b]f (f b) -> f bBearbeitung: tatsächlich können Sie die erstere definieren; siehe die Bearbeitung). Warum? Nun, wenn Sie sich fmap, pure und <*> ansehen, werden Sie feststellen, dass Sie keine Möglichkeit haben, den f Typkonstruktor loszuwerden (oder umzustellen), sodass Sie einmal [f a] haben, in dieser Form stecken bleiben.

Zum Glück sind dafür Monaden vorgesehen: Berechnungen, die den "Formenwechsel" ermöglichen, sozusagen. Wenn Sie eine Monade m haben, erhalten Sie neben dem oben Genannten zwei zusätzliche Methoden (und return als Synonym für pure):

(>>=) :: m a -> (a -> m b) -> m b
join  :: m (m a) -> m a

Obwohl join nur in Control.Monad definiert ist, ist es genauso grundlegend wie >>= und manchmal klarer zu verstehen. Jetzt haben wir also die Möglichkeit, Ihre Funktionen [m b] -> m [b]m (m b) -> m bjoin; und die erste ist sequence, aus der Präludium. Mit der Monade m können Sie also Ihr mapX definieren als

mapX :: Monad m => (m a -> m b) -> m [a] -> m [b]
mapX f mxs = mxs >>= sequence . map (f . return)

Das wäre jedoch eine seltsame Art, es zu definieren. Es gibt noch ein paar andere nützliche Funktionen auf Monaden im Präludium: mapM :: Monad m => (a -> m b) -> [a] -> m [b], was äquivalent zu mapM f = sequence . map f ist; und (=<<) :: (a -> m b) -> m a -> m b, was äquivalent zu flip (>>=) ist. Unter Verwendung dieser würde ich mapX wahrscheinlich wie folgt definieren

mapX :: Monad m => (m a -> m b) -> m [a] -> m [b]
mapX f mxs = mapM (f . return) =<< mxs

---

Bearbeitung: Tatsächlich, mein Fehler: wie John L freundlich in einem Kommentar darauf hingewiesen hat, stellt Data.Traversable (was ein Basismodul ist) die Funktion sequenceA :: (Applicative f, Traversable t) => t (f a) => f (t a) bereit; und da [] eine Instanz von Traversable ist, können Sie einen applikativen Funktor sequenzieren. Dennoch erfordert Ihre Typensignatur weiterhin join oder =<<, also stecken Sie weiterhin fest. Ich würde wahrscheinlich vorschlagen, Ihr Design neu zu überdenken; Ich denke, sclv hat wahrscheinlich die richtige Idee.

---

1: Oder map (f . pure) <$> fxs, unter Verwendung des Synonyms <$> für fmap aus Control.Applicative.

Answer 3

Hier ist eine Sitzung in ghci, in der ich mapX so definiere, wie du es wolltest.

Prelude>
Prelude> import Control.Applicative
Prelude Control.Applicative> :t pure
pure :: Applicative f => a -> f a
Prelude Control.Applicative> :t (<*>)
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Prelude Control.Applicative> let mapX fun ma = pure fun <*> ma
Prelude Control.Applicative> :t mapX
mapX :: Applicative f => (a -> b) -> f a -> f b

Ich muss jedoch hinzufügen, dass es besser ist, fmap zu verwenden, da Functor weniger ausdrucksstark ist als Applicative (das bedeutet, dass fmap häufiger funktioniert).

Prelude> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

Bearbeitung: Oh, du hast eine andere Signatur für mapX, wie auch immer, vielleicht meintest du die, die ich vorgeschlagen habe (fmap)?