标签: catamorphism

写完这篇文章之后,我决定将我的钱放在我的嘴边,并开始转换我以前使用的项目recursion-schemes.

有问题的数据结构是一个懒惰的kdtree.请查看具有显式和隐式递归的实现.

这主要是一种简单的转换:

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

至

data KDTreeF v a f = NodeF a f f | Leaf v a

现在对整个shebang进行基准测试后,我发现该KDTreeF版本比普通版本慢了两倍(在这里找到整个版本).

这只是额外的Fix包装,让我放慢了速度吗？有什么我可以做的吗？

注意事项:

• 目前这是专门为(V3双).
• 这是在变形应用之后的cata-.Hylomorphism不适合kdtrees.
• 我用cata (fmap foo algebra)了好几次.这是好习惯吗？
• 我使用Edwards recursion-schemes包.

编辑1:

这有关系吗？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers 是newtype Fix f = Fix …

我正在尝试了解catamorphisms,我已经阅读了维基百科文章以及F#博客上F#主题系列中的第一篇文章.

我理解这是折叠的概括(即,将许多值的结构映射到一个值,包括值列表到另一个列表).我认为折叠列表和折叠树是一个典型的例子.

可以使用LINQ的Aggregate运算符或其他一些更高阶的方法在C#中显示它吗？

我非常喜欢以通用的方式使用catamorphisms/anamorphisms的想法,但在我看来它有一个显着的性能缺点:

假设我们希望以分类方式使用树结构 - 使用通用的catamorphism函数描述不同的折叠:

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 …

许多catamorphisms似乎很简单,大多数用自定义函数替换每个数据构造函数,例如

data Bool = False | True
foldBool :: r              -- False constructor
         -> r              -- True constructor
         -> Bool -> r

data Maybe a = Nothing | Just a
foldMaybe :: b             -- Nothing constructor
          -> (a -> b)      -- Just constructor
          -> Maybe a -> b

data List a = Empty | Cons a (List a)
foldList :: b              -- Empty constructor
         -> (a -> b -> b)  -- Cons constructor
         -> List a -> b

但是,对我来说不清楚的是,如果使用相同类型的构造函数,但使用不同的类型参数会发生什么.例如,而不是传递List …

来自http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf的第3页:

一般情况下,catamorphisms在组成下是封闭的

在什么条件下,catamorphisms构成了一个catamorphism？更具体地说(假设我正确地理解了陈述):

假设我有两个基础仿函数F和G每个折叠:foldF :: (F a -> a) -> (?F -> a)和foldG :: (G a -> a) -> (?G -> a).

现在假设我有两个代数a :: F ?G -> ?G和b :: G X -> X.

该构图何时成为(foldG b) . (foldF a) :: ?F -> X一个变形？

编辑:我有一个猜测,基于dblhelix的扩展答案:这outG . a :: F ?G -> G ?G必须是?G一些自然转换的组成部分? :: F a -> G a.我不知道这是否正确.( …

我很不耐烦,期待理解与这个SO问题有关的 catamorphism :)

我只练习了Real World Haskell教程的开头.所以,也许我现在要问的方式太多了,如果是这样的话,那就告诉我应该学习的概念.

下面,我引用了维基百科代码样本的catamorphism.

我想知道你对下面的foldTree的看法,这是一种遍历树的方法,与其他SO问题和答案相比,还涉及遍历Tree n-ary树遍历.(独立于二进制或不二进制,我认为下面的catamorphism可以编写,以便管理n-ary树)

我评论了我的理解,如果你能纠正我,并且澄清一些事情,我会很高兴.

{-this is a binary tree definition-}
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

{-I dont understand the structure between{} 
however it defines two morphisms, leaf and branch 
leaf take an a and returns an r, branch takes two r and returns an r-} 
data TreeAlgebra a r = TreeAlgebra { leaf   :: a      -> r
                                   , branch :: r -> r …

我正在阅读关于catamorphisms的维基百科文章,目前我能够在F#中重现Haskell示例,除了这部分:

type Algebra f a = f a -> a -- the generic f-algebras

newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions

这可能在F#中做到吗？

对自然数使用以下 catamorphism 我可以实现各种算术算法而不必处理递归：

cataNat :: b -> (b -> b) -> Natural -> b
cataNat zero succ = go
  where
    go n = if (n <= 0) then zero else succ (go (n - 1))

fib :: Natural -> Natural
fib = fst . cataNat (0, 1) (\(a, b) -> (b, a + b))

cataNat对我来说看起来类似于原始递归。无论提供zero和 的哪种组合，至少它的每个应用程序似乎都可以终止succ。在每次迭代中，整个问题都被最小/最简单的问题实例分解。因此，即使它在技术上不是原始递归，它似乎也具有同样的表现力。如果这是真的，则意味着 catamorphism 不足以表达一般递归。为此，我们可能需要一个hylomorphism。我的推理是否正确，也就是说，等价性是否适用于任何类型的 catamorphism，而不仅仅是自然数？

我最近学到了一些关于F-algebras的知识:https: //www.fpcomplete.com/user/bartosz/understanding-algebras.我想将此功能提升到更高级的类型(索引和更高级别).此外,我检查了"给Haskell一个促销"(http://research.microsoft.com/en-us/people/dimitris/fc-kind-poly.pdf),这非常有用,因为它给我自己的模糊命名"发明".

但是,我似乎无法创建适用于所有形状的统一方法.

代数需要一些"载体类型",但我们遍历的结构需要一定的形状(本身,递归应用),所以我想出了一个"Dummy"容器,可以携带任何类型,但形状符合预期.然后我使用一个类型系列来耦合它们.

这种方法似乎有效,导致我的'cata'功能的相当通用的签名.

但是,我使用的其他东西(Mu,Algebra)仍然需要为每个形状分别设置版本,只是为了传递一堆类型变量.我希望像PolyKinds这样的东西可以提供帮助(我成功地使用它来塑造虚拟类型),但它似乎只是意味着相反的方式.

由于IFunctor1和IFunctor2没有额外的变量,我试图通过附加(通过类型族)索引保留函数类型来统一它们,但由于存在量化,这似乎是不允许的,所以我留下了多个版本太.

有没有办法统一这两个案例？我是否忽略了一些技巧,或者这只是现在的限制？还有其他可以简化的事情吗？

{-# LANGUAGE DataKinds                 #-}
{-# LANGUAGE ExistentialQuantification #-}
{-# LANGUAGE GADTs                     #-}
{-# LANGUAGE PolyKinds                 #-}
{-# LANGUAGE Rank2Types                #-}
{-# LANGUAGE StandaloneDeriving        #-}
{-# LANGUAGE TypeFamilies              #-}
{-# LANGUAGE TypeOperators             #-}
{-# LANGUAGE UndecidableInstances      #-}
module Cata where

-- 'Fix' for indexed types (1 index)
newtype Mu1 f a = Roll1 { unRoll1 :: f (Mu1 f) a }
deriving instance Show (f (Mu1 f) a) …

我最近发现了如何 以某种迂回的方式在 Java 中模拟高阶类型，如下所示

interface H<F, T> { }

这里H编码一个高阶类型，它采用类型参数，F该类型参数本身采用参数T。

现在这让我想知道，我们可以用它来实现一些更高级的构造吗？例如，Haskell 中的 Fix 等函子的不动点及其相应的变形？