haskell - 应用仿函数分析

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值(value):

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

Applicative实例比较复杂。 pure函数只会返回一个没有依赖关系的值。 <*>组合器将连接两个依赖项列表(删除重复项)，并组合两个操作:

instance Applicative Input where
  pure = Input [] . return

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

有了它，我们还可以制作 Input a如果 Num a 是 Num 的一个实例:

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

接下来，让我们做几个输入:

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的静态分析允许 - 我们知道依赖项而无需执行操作。

尽管如此，我们仍然可以获得 Action 的值(value):

> runInput portfolioValue >>= print
5400.0

现在，为什么我们不能对 Monad 做同样的事情？ ?原因是 Monad可以表达选择，因为一个 Action 可以决定下一个 Action 是什么。

想象一下有一个 Monad Input的接口(interface)，并且您有以下代码:

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]