Мне очень нравится идея работать с катаморфизмами/анаморфизмами в общем виде, но мне кажется, что это имеет существенный недостаток производительности:
Предположим, что мы хотим категорически работать с древовидной структурой - описать различные варианты сгибания с помощью общей функции катаморфизма:
newtype Fix f = Fix { unfix :: f (Fix f) }
data TreeT r = Leaf | Tree r r
instance Functor TreeT where
fmap f Leaf = Leaf
fmap f (Tree l r) = Tree (f l) (f r)
type Tree = Fix TreeT
catam :: (Functor f) => (f a -> a) -> (Fix f -> a)
catam f = f . fmap (catam f) . unfix
Теперь мы можем написать такие функции, как:
depth1 :: Tree -> Int
depth1 = catam g
where
g Leaf = 0
g (Tree l r) = max l r
К сожалению, этот подход имеет существенный недостаток: во время вычисления новые экземпляры TreeT Int
создаются на каждом уровне в fmap
только для немедленного потребления g
. По сравнению с классическим определением
depth2 :: Tree -> Int
depth2 (Fix Leaf) = 0
depth2 (Fix (Tree l r)) = max (depth1 l) (depth1 r)
наш depth1
будет всегда медленнее делать ненужную нагрузку на GC. Одним из решений было бы использовать hylomorphisms и объединить создание и складывание деревьев вместе. Но часто мы не хотим этого делать, мы можем хотеть, чтобы дерево было создано на одном месте, а затем передавалось куда-то еще, чтобы свернуть позже. Или, чтобы быть папкой несколько раз с различными катаморфизмами.
Можно ли оптимизировать GHC depth1
? Что-то вроде вставки catam g
, а затем слияние/обезлесение g . fmap ...
внутри?