Applicative funktors analysis

Question

Ich habe versucht, über statische Analyse der anwendbaren Funktoren zu lernen. Viele Quellen sagen, dass ein Vorteil ihrer Verwendung gegenüber Monaden die Anfälligkeit für statische Analyse ist.

Aber die einzige example ich finden kann, tatsächlich statische Analyse durchzuführen ist zu kompliziert für mich zu verstehen. Gibt es dafür einfachere Beispiele?

Insbesondere möchte ich wissen, ob ich statische Analyse auf rekursive Anwendungen durchführen kann. Zum Beispiel so etwas wie:

y = f <$> x <*> y <*> z 

Wenn der obige Code analysiert wird, ist es möglich zu erkennen, dass es auf y rekursiv ist? Oder verhindert die referenzielle Transparenz das immer noch?

Answer 1

Applikative Funktoren erlauben statische Analyse zur Laufzeit. Dies wird besser durch ein einfacheres Beispiel erklärt.

Stellen Sie sich vor, Sie möchten einen Wert berechnen, möchten aber verfolgen, welche Abhängigkeiten dieser Wert hat. Zum Beispiel können Sie IO a verwenden Sie den Wert zu berechnen, und eine Liste von Strings für die Abhängigkeiten haben:

data Input a = Input { dependencies :: [String], runInput :: IO a } 

Jetzt können wir einfach diese eine Instanz von Functor und Applicative machen. Die Funktorinstanz ist trivial. Da es keine neuen Abhängigkeiten nicht einführen wird, brauchen Sie nur über den runInput Wert zuzuordnen:

instance Functor (Input) where 
    fmap f (Input deps runInput) = Input deps (fmap f runInput) 

Die Applicative Instanz komplizierter. Die pure Funktion wird nur einen Wert ohne Abhängigkeiten zurückgeben. Die <*> Kombinierer die beide Liste der Abhängigkeiten (Entfernen von Duplikaten) und verbinden die beiden Aktionen verketten:

instance Applicative Input where 
    pure = Input [] . return 

    (Input deps1 getF) <*> (Input deps2 runInput) = Input (nub $ deps1 ++ deps2) (getF <*> runInput) 

Damit können wir auch eine Input a eine Instanz von Num wenn Num a machen:

instance (Num a) => Num (Input a) where 
    (+) = liftA2 (+) 
    (*) = liftA2 (*) 
    abs = liftA abs 
    signum = liftA signum 
    fromInteger = pure . fromInteger 

nExts, lässt ein paar Eingänge machen:

getTime :: Input UTCTime 
getTime = Input { dependencies = ["Time"], runInput = getCurrentTime } 

-- | Ideally this would fetch it from somewhere 
stockPriceOf :: String -> Input Double 
stockPriceOf stock = Input { dependencies = ["Stock (" ++ stock ++ ")"], runInput = action } where 
    action = case stock of 
    "Apple" -> return 500 
    "Toyota" -> return 20 

Schließlich lässt einen Wert machen, dass einige Eingaben verwendet:

portfolioValue :: Input Double 
portfolioValue = stockPriceOf "Apple" * 10 + stockPriceOf "Toyota" * 20 

Das ist ein ziemlich cooler Wert. Zum einen können wir die Abhängigkeiten von portfolioValue als reine Wert finden:

> :t dependencies portfolioValue 
dependencies portfolioValue :: [String] 
> dependencies portfolioValue 
["Stock (Apple)","Stock (Toyota)"] 

, dass die statische Analyse ist, dass Applicative erlaubt - wir kennen die Abhängigkeiten, ohne dass die Aktion ausführen zu müssen.

Wir können immer noch, obwohl der Wert der Aktion erhalten:

> runInput portfolioValue >>= print 
5400.0 

---

Nun, warum nicht tun können wir das gleiche mit Monad? Der Grund ist Monad kann Wahl ausdrücken, in dem eine Aktion bestimmen kann, was die nächste Aktion sein wird.

Imagine gab es eine Monad Schnittstelle für Input, und man hatte den folgenden Code:

mostPopularStock :: Input String 
mostPopularStock = Input { dependencies ["Popular Stock"], getInput = readFromWebMostPopularStock } 

newPortfolio = do 
    stock <- mostPopularStock 
    stockPriceOf "Apple" * 40 + stockPriceOf stock * 10 

Nun, wie können wir die Abhängigkeiten von newPortolio berechnen? Es stellt sich heraus, dass wir es nicht ohne IO machen können! Es hängt vom beliebtesten Bestand ab, und die einzige Möglichkeit, dies zu wissen, ist, die IO-Aktion auszuführen. Daher ist es nicht möglich, Abhängigkeiten statisch zu verfolgen, wenn der Typ Monad verwendet, aber nur mit Applicativ vollständig möglich ist. Dies ist ein gutes Beispiel dafür, warum oft weniger Leistung sinnvoller ist - da Applicative keine Auswahl zulässt, können Abhängigkeiten statisch berechnet werden.

---

Edit: Im Hinblick auf die Prüfung, ob y auf sich selbst rekursiv ist, eine solche Überprüfung ist möglich, mit applicative functors, wenn Sie bereit sind, Ihre Funktionsnamen zu annotieren.

data TrackedComp a = TrackedComp { deps :: [String], recursive :: Bool, run :: a} 

instance (Show a) => Show (TrackedComp a) where 
    show comp = "TrackedComp " ++ show (run comp) 

instance Functor (TrackedComp) where 
    fmap f (TrackedComp deps rec1 run) = TrackedComp deps rec1 (f run) 

instance Applicative TrackedComp where 
    pure = TrackedComp [] False 

    (TrackedComp deps1 rec1 getF) <*> (TrackedComp deps2 rec2 value) = 
    TrackedComp (combine deps1 deps2) (rec1 || rec2) (getF value) 

-- | combine [1,1,1] [2,2,2] = [1,2,1,2,1,2] 
combine :: [a] -> [a] -> [a] 
combine x [] = x 
combine [] y = y 
combine (x:xs) (y:ys) = x : y : combine xs ys 

instance (Num a) => Num (TrackedComp a) where 
    (+) = liftA2 (+) 
    (*) = liftA2 (*) 
    abs = liftA abs 
    signum = liftA signum 
    fromInteger = pure . fromInteger 

newComp :: String -> TrackedComp a -> TrackedComp a 
newComp name tracked = TrackedComp (name : deps tracked) isRecursive (run tracked) where 
    isRecursive = (name `elem` deps tracked) || recursive tracked 


y :: TrackedComp [Int] 
y = newComp "y" $ liftA2 (:) x z 

x :: TrackedComp Int 
x = newComp "x" $ 38 

z :: TrackedComp [Int] 
z = newComp "z" $ liftA2 (:) 3 y 

> recursive x 
False 
> recursive y 
True 
> take 10 $ run y 
[38,3,38,3,38,3,38,3,38,3] 

Answer 2

Ja, anwendbare Funktoren erlauben mehr Analyse als Monaden. Aber nein, Sie können die Rekursion nicht beobachten. Ich habe ein Papier über Parsing geschrieben, die das Problem im Detail erklärt:

https://lirias.kuleuven.be/bitstream/123456789/352570/1/gc-jfp.pdf

Das Papier beschreibt dann eine alternative Codierung von Rekursion, die Analyse erlaubt und hat einige andere Vorteile und einige Nachteile. Damit verbundene Arbeiten ist:

https://lirias.kuleuven.be/bitstream/123456789/376843/1/p97-devriese.pdf

Und mehr damit verbundene Arbeiten können in den entsprechenden Arbeitsabschnitte dieser Papiere zu finden ...