Анализ аппликативных функторов

Я пытался узнать о статическом анализе аппликативных функторов. Многие источники говорят, что преимуществом их использования по сравнению с монадами является склонность к статическому анализу.

Однако единственный пример, который я могу найти для выполнения статического анализа, слишком сложен для меня, чтобы понять. Есть ли более простые примеры этого?

В частности, я хочу знать, могу ли я выполнять статический анализ рекурсивных приложений. Например, что-то вроде:

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

Анализируя приведенный выше код, можно ли обнаружить, что он рекурсивен по y? Или ссылочная прозрачность все еще не позволяет сделать это возможным?

Источник

2 ответа

Решение

Аппликативные функторы позволяют проводить статический анализ во время выполнения. Это лучше объяснить на более простом примере.

Представьте, что вы хотите вычислить значение, но хотите отслеживать зависимости этого значения. Например, вы можете использовать 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 Функция просто вернет значение без каких-либо зависимостей. <*> combiner объединит два списка зависимостей (удалив дубликаты) и объединит два действия:

instance Applicative Input where
  pure = Input [] . return

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

С этим мы также можем сделать Input a экземпляр Num, если Num a:

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 позволяет - мы знаем зависимости без необходимости выполнять действие.

Мы все еще можем получить значение действия, хотя:

> 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! Это будет зависеть от самой популярной акции, и единственный способ узнать это - запустить действие ввода-вывода. Поэтому невозможно статически отслеживать зависимости, когда тип использует 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]
Источник

Да, аппликативные функторы позволяют проводить больший анализ, чем монады. Но нет, вы не можете наблюдать рекурсию. Я написал статью о разборе, которая подробно объясняет проблему:

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

Затем в документе обсуждается альтернативное кодирование рекурсии, которое позволяет проводить анализ и имеет некоторые другие преимущества и некоторые недостатки. Другая связанная работа:

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

И больше связанной работы можно найти в соответствующих разделах работы этих документов...

Источник
Другие вопросы по тегам