Запоминание схемы рекурсии
Можно ли запомнить схему рекурсии? Если да, то как бы вы?
Например, в следующем используется анамофизм и катаморфизм.
newtype Fix f = In (f (Fix f))
deriving instance (Eq (f (Fix f))) => Eq (Fix f)
deriving instance (Ord (f (Fix f))) => Ord (Fix f)
deriving instance (Show (f (Fix f))) => Show (Fix f)
out :: Fix f -> f (Fix f)
out (In f) = f
-- Catamorphism
type Algebra f a = f a -> a
cata :: (Functor f) => Algebra f a -> Fix f -> a
cata f = f . fmap (cata f) . out
-- Anamorphism
type Coalgebra f a = a -> f a
ana :: (Functor f) => Coalgebra f a -> a -> Fix f
ana f = In . fmap (ana f) . f
для решения проблемы с решетчатыми путями:
latticePaths m n = cata countPathsAlgNoMemo (ana buildLattice (m, n))
-- recursive solution without dynamic programming
buildLattice :: (Int, Int) -> LeafBTreeF Int (Int, Int)
buildLattice (m, n)
| m == 0 && n == 0 = LeafBTreeLeafF 1
| m < 0 || n < 0 = LeafBTreeLeafF 0
| otherwise = LeafBTreeNodeF (m - 1, n) (m, n - 1)
countPathsAlgNoMemo :: LeafBTreeF Int Int -> Int
countPathsAlgNoMemo (LeafBTreeLeafF n) = n
countPathsAlgNoMemo (LeafBTreeNodeF a b) = a + b
Это неэффективно, потому что подзадачи пересчитываются, а не сохраняются и повторно используются. Я хотел бы знать, есть ли способ сохранить (или заставить компилятор haskell хранить) ранее вычисленные подзадачи.
Я просмотрел некоторые ресурсы, связанные с запоминанием полиморфных функций (http://blog.sigfpe.com/2009/11/memoizing-polymorphic-functions-with.html, http://conal.net/blog/posts ). /memoizing-polymorphic-functions-part-two), но не смог понять, как они могут применяться здесь.
ПРИМЕЧАНИЕ. Меня особенно интересует,apomorphism/paramorphismиanamorphism/catamorphismможно запомнить (или если есть какое-либо другое решение для хранения подзадач с использованием этих схем рекурсии). Я понимаю, что гистоморфизм и динамоморфизм подходят для решения задач динамического программирования, но для своих целей я хочу ограничить свое внимание апо/пара или ана/ката.
Мойparamorphismиapomorphism:
-- Paramorphism
type RAlgebra f a = f (Fix f, a) -> a
para :: (Functor f) => RAlgebra f a -> Fix f -> a
para rAlg = rAlg . fmap fanout . out
where fanout t = (t, para rAlg t)
-- Apomorphism
type RCoalgebra f a = a -> f (Either (Fix f) a)
apo :: Functor f => RCoalgebra f a -> a -> Fix f
apo rCoalg = In . fmap fanin . rCoalg
where fanin = either id (apo rCoalg)
1 ответ
Обновление: см. ниже композиции параморфизма/апоморфизма.
Обратите внимание, что запоминаниеcata fиana gпо отдельности бессмысленно. Проблема в том, что строим свежую решетку с нуля:
ana buildLattice (20,20)
в основном не сложнее, чем чтение этой структуры из предварительно сгенерированной копии в памяти. Это было бы похоже на запоминаниеreplicate 1000000000 'x'. Это не имеет никакого смысла.
То же самое сcata countPathsAlg. Подсчитать количество путей несложно. Трудная часть — обход структуры (будь то для выполнения вычислений или для поиска ключа в памятной таблице). Если вы хотите эффективно запомнить катаморфизм, вам нужно представлять большие структуры с помощью простых ключей. Но у нас уже есть простые ключи для наших структур — это значения, которые мы передаем анаморфизму для создания этих структур!
Другими словами, чтобы сделать это вычисление поддающимся запоминанию, вам нужно исключить промежуточную структуру данных, объединив катаморфизм и анаморфизм.
Это не слишком сложно. Предположим, у нас есть:
h = cata f . ana g
Затем следует, что:
h
= cata f . ana g
= f . fmap (cata f) . out . In . fmap (ana g) . g
= f . fmap (cata f . ana g) . g
= f . fmap h . g
Обратите внимание, что этоrefoldАКАhyloизrecursion-schemesупаковка:
hylo f g = h where h = f . fmap h . g
Для вашего примера у нас есть объединенная рекурсия:
latticePaths :: (Int, Int) -> Int
latticePaths = countPathsAlg . fmap latticePaths . buildLattice
который легко запомнить, скажем,memoizeупаковка:
import Data.Function.Memoize
latticePaths :: (Int, Int) -> Int
latticePaths = h where h = memoize (countPathsAlg . fmap h . buildLattice)
main = print $ latticePaths (100,100)
В более общем случае любой гиломорфизм можно запомнить с помощью:
hylo_memo f g = h where h = memoize (f . fmap h . g)
Полное запоминание комбинации параморфизм/апоморфизм невозможно. Есть две проблемы.
Во-первых, когда апо производит , он может создавать произвольно сложную структуру. Даже если бы вы могли запомнить корень этой структуры (поскольку онаaзначение), нет эффективного способа запомнить идентичные подзадачи в этой структуре. Например, предположим, что apo производит розовое дерево, состоящее из 1000 идентичных ветвей, каждая из которых состоит из миллиона узлов. Единственный способ обнаружить, что все 1000 ветвей идентичны и могут использовать одно и то же решение, — это пройти миллион узлов в каждой ветви, чтобы сравнить их.
Во-вторых, расчет параморфизма может, вообще говоря, зависеть от полной структуры в текущем узле, а не только от некоторой «небольшой» комбинации ранее рассчитанных результатов параморфизма из локальной структуры, определенной алгеброй. Например, рассмотрим параморфизм дерева роз, который суммирует количество раз, когда значение узла появляется в его поддереве, и суммирует эти значения для всех узлов, и предположим, что он реализован следующим образом:
data Rose a t = Rose a [t]
refCount :: (Eq a) => RAlgebra (Rose a) Int
refCount (Rose a bs)
-- reference counts from subnodes
= sum (map snd bs)
-- occurrences of "a" in the branches
+ sum (map (countValues a . fst) bs)
-- count number of "a"s in the tree
countValues :: (Eq a) => a -> Fix (Rose a) -> Int
countValues a = ...
Обратите внимание, что когда у нас есть результат для «подзадачи», все, что у нас есть, — это общее количество ссылок в этом дереве. Если это же дерево появляется под пятью разными родительскими узлами, мы можем повторно использовать этот результат, но нам все равно нужно искать во всем дереве значения пяти разных родительских узлов, чтобы построить их счетчики.
Это не означает, что мемоизация бесполезна. Мы можем запоминать части апоморфизма, и запоминание результатов параморфизма может быть полезно, даже если требуется полный обход структуры (например, дляrefCountвыше, частичная мемоизация уменьшает сложность от кубической до квадратичной, я думаю).
Итак, если вы продолжите расширение:
h
= para f . apo g
= f . fmap ((\t -> (t, para f t)) . either id (apo g)) . g
= f . fmap k . g
where k = \case Left t -> (t, para f t)
Right a -> (apo g, h a)
мы можем добиться частичной мемоизации:
paraApo :: (Ord a, Functor f) => RAlgebra f b -> RCoalgebra f a -> a -> b
paraApo f g = h
where h = memo $
f . fmap k . g
where k = \case Left t -> (t, para f t)
Right a -> (apo g a, h a)
что может быть полезно. Незапомненные части будутpara f tкогда апо выдает а, а потенциально дорогостоящая операция пара над своим первым аргументом производитсяapo g aв филиале.
Комбинация катаморфизма/апоморфизма также частично запоминаема. У нас все еще есть проблема, которую может произвести апоLeftс произвольной, незапоминаемой структурой, ноRightы апо могут быть полностью запомнены.
h
= cata f . apo g
= f . fmap (cata f . either id (apo g)) . g
= f . fmap k . g
where k = \case Left t -> cata f t -- non-memoizable
Right a -> h a -- memoizable