Analiza funktorów użytkowych

Question

Próbowałem dowiedzieć się o statycznej analizie funktorów aplikacyjnych. Wiele źródeł twierdzi, że zaletą ich używania w porównaniu z monadami jest podatność na analizę statyczną.

Jednak jedyne example mogę znaleźć w rzeczywistości wykonywania analizy statycznej jest zbyt skomplikowane, aby zrozumieć. Czy są jakieś prostsze przykłady tego?

W szczególności chcę wiedzieć, czy mogę wykonywać analizę statyczną w aplikacjach rekurencyjnych. Na przykład coś takiego:

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

Czy podczas analizy powyższego kodu można wykryć rekursywność na y? Czy też przejrzystość referencyjna nadal uniemożliwia taką możliwość?

Answer 1

Fizyczne funktory umożliwiają analizę statyczną w czasie wykonywania. Jest to lepiej wyjaśnione prostszym przykładem.

Wyobraź sobie, że chcesz obliczyć wartość, ale chcesz śledzić zależności, które ma ta wartość. Na przykład można użyć IO a obliczyć wartość i mieć listę Strings dla zależności:

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

Teraz łatwo możemy dokonać tej instancji Functor i Applicative. Instancja funktora jest banalna. Gdyż nie wprowadzają żadnych nowych zależności, wystarczy map nad wartością runInput:

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

Instancja Applicative jest bardziej skomplikowana. funkcja pure po prostu zwróci wartość bez żadnych zależności. <*> sumator będzie Concat dwie listę zależności (usuwanie duplikatów) i połączyć te dwie czynności:

instance Applicative Input where 
    pure = Input [] . return 

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

z tym, możemy również dokonać Input a instancję Num jeśli Num a:

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

Nexts, pozwala zrobić kilka wejść:

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 

Wreszcie, pozwala tworzyć wartość, która wykorzystuje kilka wejść:

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

Jest to całkiem fajna wartość. Po pierwsze, możemy znaleźć zależnościami portfolioValue jako czysta wartość:

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

czyli analiza statyczna że Applicative pozwala - wiemy zależności bez konieczności wykonywania akcji.

Nadal możemy uzyskać wartość akcji choć:

> runInput portfolioValue >>= print 
5400.0 

---

Teraz, dlaczego nie możemy zrobić to samo z Monad? Powodem jest to, że Monad może wyrazić wybór, ponieważ jedno działanie może określić, jaka będzie następna czynność.

Wyobraź było Monad interfejs Input, i miał następujący kod:

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

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

Teraz, w jaki sposób możemy obliczyć zależnościami newPortolio? Okazuje się, że nie możemy tego zrobić bez użycia IO! Będzie to zależało od najpopularniejszych zasobów, a jedynym sposobem, aby się dowiedzieć, jest uruchomienie akcji IO. Dlatego nie jest możliwe śledzenie zależności statycznych, gdy typ korzysta z Monady, ale całkowicie możliwe za pomocą właśnie Aplikacji. Jest to dobry przykład tego, dlaczego często mniejsza moc oznacza większą użyteczność - ponieważ Wnioskodawca nie pozwala na wybór, zależności można obliczać statycznie.

---

Edit: Jeśli chodzi o sprawdzenie, czy y jest rekurencyjne na siebie, taka kontrola jest możliwa aplikacyjnych funktorów, jeśli są chętni do opisywania nazw funkcji.

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

Tak, funktory aplikacyjne pozwalają na większą analizę niż monady. Ale nie, nie możesz obserwować rekurencji. Pisałem referat o parsowania który wyjaśnia problemu w szczegółach:

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

Papier następnie omawia alternatywne kodowanie rekursji która nie pozwalają na analizę i ma kilka innych zalet i kilka wad. Inne związane z tym prace to:

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

I podobne prace można znaleźć w odpowiednich sekcjach pracy tych papierów ...