應用仿函數分析

Question

我一直在嘗試瞭解應用仿函數的靜態分析。許多消息來源表示，將它們用於monad的優勢在於對靜態分析的敏感性。

但是，我能找到的實際執行靜態分析的唯一example對我來說太複雜了。有沒有更簡單的例子？

具體來說，我想知道我是否可以對遞歸應用程序執行靜態分析。例如，如下所示：

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

當分析上述代碼時，是否有可能檢測到它是遞歸的y？還是參照透明度仍然可以防止這種情況發生？

Answer 1

應用仿函數允許在運行時進行靜態分析。這可以通過一個更簡單的例子來解釋。

想象一下，您想要計算一個值，但想要跟蹤該值具有哪些相關性。例如，你可以使用IO a計算值，並有Strings列表的依賴關係：

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

現在，我們可以很容易地使Functor和Applicative這一個實例。函子實例是微不足道的。因爲它不引入任何新的依賴，你只需要映射在runInput值：

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

的Applicative情況更爲複雜。 pure函數將只返回一個沒有依賴關係的值。該<*>組合將Concat的依賴（刪除重複）的兩個列表，並結合這兩個動作：

instance Applicative Input where 
    pure = Input [] . return 

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

就這樣，我們也可以做一個Input a如果Num a的民實例：

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

的nextS，讓我們做一些投入的：

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 

最後，讓我們做的是使用一些輸入一個值：

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

這是一個非常酷的價值。首先，我們可以發現portfolioValue依賴作爲一個純粹的價值：

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

這是靜態分析認爲Applicative讓 - 我們知道的依賴，而無需執行的操作。

我們仍然可以得到行動的價值，但：

> runInput portfolioValue >>= print 
5400.0 

---

現在，我們爲什麼不能做Monad一樣嗎？原因是Monad可以表示選擇，因爲一個動作可以確定下一個動作是什麼。

想象有一個Monad接口Input，和你有下面的代碼：

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

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

現在，我們怎麼能計算newPortolio的依賴？事實證明，如果不使用IO，我們無法做到！這將取決於最流行的股票，唯一的方法就是運行IO操作。因此，當類型使用Monad時，不可能靜態地跟蹤依賴關係，但完全可以使用Applicative。這是一個很好的例子，爲什麼經常較少的權力意味着更有用 - 因爲Applicative不允許選擇，依賴性可以靜態計算。

---

編輯：至於是否y是自身遞歸的檢查，這種檢查是可能的應用性函子，如果你願意來註釋功能名稱。

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

是的，應用仿函數允許比單子更多的分析。但是，不，你不能觀察遞歸。我寫了一個關於解析文件，其中詳細解釋了這個問題：

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

本文然後討論遞歸的另一種編碼，這確實允許分析，並有一些其他的優勢和一些缺點。其他相關工作：

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

而更多的相關工作可在這些論文的相關工作章節中找到...