标签: corecursion

我已经定义了无限列表的无限列表pathCounts和有限列表的无限列表pathCounts':

import Data.Function (fix)

nextRow xs = fix $ \ys -> zipWith (+) xs (0:ys)

pathCounts = repeat 1 : map nextRow pathCounts
pathCounts' = map (take 100) pathCounts

放入ghci,如果我根本没有评估,我可以:p成功使用:

ghci> :p pathCounts
pathCounts = (_t1::[[Integer]])
ghci> :p pathCounts'
pathCounts' = (_t2::[[Integer]])

但如果我pathCounts'部分评估,那么:p在pathCounts继续成功的同时冻结pathCounts':

ghci> head . head $ pathCounts'
1
ghci> :p pathCounts'
pathCounts' = (1 : (_t4::[Integer])) : (_t5::[[Integer]])
ghci> :p pathCounts
^CInterrupted.

我希望:p …

我filter使用recursion-schemesHackage库中的变形函数实现了一个破坏的函数:

import Data.Functor.Foldable

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana $ project . phi f

phi :: (a -> Bool) -> [a] -> [a]
phi f (h : t) | not (f h) = t
phi f l = l

该功能不是忠实的实现filter:xfilter odd [1..5]工作,但xfilter odd [0,0]没有.我试图通过使用显式递归来实现"重试" phi,然后使用paramorphism重新实现,所以我结束于ana . para:

xfilter :: (a -> Bool) -> [a] -> [a]
xfilter f = ana …

我正在开发一个C++项目,需要经常与树结构交互,这意味着许多递归函数,我正在寻找改进代码的方法.前几天我遇到了corecursion,我有兴趣为我的应用程序探索这个策略.

但是,我还没有找到任何如何用C++完成corecursion的例子.为了使我的问题具体,我如何在C++中使用corecursion进行树遍历？

def bf(tree):
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list

如果这样做只是一个坏主意,请告诉我.也就是说,在互联网上得到一些答案对于那些试图在未来做这件事的人来说会很有用.关于SO匹配没有任何问题,[c++] corecursion互联网的其余部分似乎缺乏有关该主题的有用信息.

我正在玩这种语言来开始学习,我对于递归定义的工作方式感到困惑.

例如,让我们采用三角数的序列(TN n = sum [1..n])

提供的解决方案是:

triangularNumbers = scanl1 (+) [1..]

到现在为止还挺好.

但我提出的解决方案是:

triangularNumbers = zipWith (+) [1..] $ 0 : triangularNumbers

这也是正确的.

现在我的问题是:这如何转化为较低级别的实现？当满足这样的递归定义时,场景背后会发生什么？

我想Foldable.toList使用变形来编写一个非空的玫瑰树,但似乎不可能提取最后一个元素:

import Data.Functor.Foldable

data RoseTree a = RoseNode a [RoseTree a]

ana5 :: RoseTree a -> [a]
ana5 = ana coalg5

coalg5 :: RoseTree a -> ListF a (RoseTree a)
coalg5 (RoseNode a []) = Nil
coalg5 (RoseNode a (RoseNode b1 b2:t)) = Cons a $ RoseNode b1 (b2 ++ t)

它确实是不可能的,它是否适用于所有非空结构？

另外(它是一种可选的奖励问题)是否有一般规则来确定何时Fix f -> Fix g可以使用f-algebras而不是g-coalgebras实现？

Btw apomorphism工作:

coalg6 (RoseNode a []) = Cons a $ Left []
coalg6 (RoseNode a (RoseNode b1 b2:t)) = …

这是一个核心递归算法，因为在每次迭代中，它调用自己的数据大于之前的数据：

iterate f x =  x : iterate f (f x)

它类似于尾递归累加器风格，但它的累加器是隐式的，而不是作为参数传递。如果不是因为懒惰，那将是无限的。那么 codata 只是 WHNF 中值构造函数的结果，有点像(a, thunk)？或者 codata 是范畴论中的一个数学术语，它在编程领域没有有用的表示？

后续问题：值递归只是核心递归的同义词吗？

我正在尝试创建一个Observable,其中每个项目都是通过异步任务生成的.下一项应该通过对前一项结果的异步调用(共同递归)生成.在"生成"这个用语中,这看起来像这样 - 除了Generate不支持异步(它也不支持初始状态的委托).

var ob = Observable.Generate(
   async () => await ProduceFirst(),        // Task<T> ProduceFirst()
   prev => Continue(prev)                   // bool Continue(T);
   async prev => await ProduceNext(prev)    // Task<T> ProduceNext(T)
   item => item
);

作为一个更具体的示例,要通过一次获取100条消息来查看ServiceBus队列中的所有消息,请按如下方式实现ProduceFirst,Continue和ProduceNext:

Task<IEnumerable<BrokeredMessage>> ProduceFirst() 
{
    const int batchSize = 100;
    return _serviceBusReceiver.PeekBatchAsync(batchSize);
}

bool Continue(IEnumerable<BrokeredMessage> prev)
{
    return prev.Any();
}

async Task<IEnumerable<BrokeredMessage>> ProduceNext(IEnumerable<BrokeredMessage> prev) 
{
    const int batchSize = 100;
    return (await _serviceBusReceiver.PeekBatchAsync(prev.Last().SequenceNumber, batchSize + 1)).Skip(1)
}

然后调用.SelectMany(i => i)上IObservable<IEnumerable<BrokeredMessage>>把它变成一个IObservable<BrokeredMessage>

其中_serviceBusReceiver是接口的实例,如下所示: …

换句话说：如果我们分别删除归纳和共归纳数据类型使用的终止检查和防护条件，归纳/共归纳和修复/共归纳之间是否不再有根本区别？

我所说的“根本差异”是指 Coq\xe2\x80\x93 核心演算的差异，而不是语法和证明搜索等方面的差异。

这似乎最终归结为一个关于构造微积分的问题。

注意：我知道一个定理证明者跳过了递归/核心递归的终止检查/防护可以证明False\xe2\x80\x93so，如果有帮助，请将其视为有关非完全编程的问题而不是证明。

我正在尝试编写n的求值递归函数

3(2+1)+4(3+2+1)+...+(n+1)(n+...+2+1)

我知道一般来说我们需要把它写成归纳,基本情况的结果就是说n = 1,然后调用n-1的函数,它将以基本情况结束.

但是在以下函数中元素增加了,我应该如何处理它