标签: theory

我正在阅读Lambda-Cube,我对System F-omega特别感兴趣,它允许"类型操作符",即类型取决于类型.这听起来很像GHC的类型系列.例如

type family Foo a
type instance Foo Int = Int
type instance Foo Float = ...
...

其中实际类型取决于类型参数a.我是否认为类型族是ala系统F-omega类型的一个例子？还是我在左外野？

读完这个问题后,我开始怀疑:是否有可能有一个不改变或复制原始列表的改组算法？

说清楚:

想象一下,您将获得一个对象列表.列表大小可以是任意的,但假设它非常大(例如,10,000,000个项目).您需要以随机顺序打印列表中的项目,并且需要尽快完成.但是,你不应该:

• 复制原始列表,因为它非常大并且复制会浪费大量内存(可能达到可用RAM的限制);
• 修改原始列表,因为它以某种方式排序,之后的其他部分依赖于它的排序.
• 创建一个索引列表,因为再次,列表非常大,复制需要花费太多时间和内存.(澄清:这意味着任何其他列表,其具有与原始列表相同数量的元素).

这可能吗？

补充:更多澄清.

1. 我希望列表以真正的随机方式进行混洗,所有排列都同样可能(当然,假设我们有一个合适的Rand()函数开始).
2. 建议我制作一个指针列表,或一个索引列表,或任何其他列表与原始列表具有相同数量的元素,由原始问题明确地认为是低效的.如果需要,您可以创建其他列表,但它们应该比原始列表小很多.
3. 原始列表就像一个数组,您可以通过其在O(1)中的索引从中检索任何项目.(所以没有双重链接列表的东西,你必须遍历列表才能找到你想要的项目.)

添加2:好的,让我们这样说吧:你有一个装有数据项的1TB硬盘,每个512字节大(一个扇区).您希望将所有这些数据复制到另一个1TB HDD,同时洗牌所有项目.您希望尽快完成此操作(单次传递数据等).您有512MB的RAM可用,并且不依赖于交换.(这是一个理论场景,我在实践中没有这样的东西.我只是想找到完美的algorithm.item.)

我一直在考虑使用Haskell的Parsec解析库来解析Java的一个子集作为递归下降解析器,作为更传统的解析器生成器解决方案(如Happy)的替代.Parsec似乎很容易使用,解析速度绝对不是我的一个因素.不过,我想知道是否可以用Parsec实现"备份",这是一种通过依次尝试每个产品来找到正确生产的技术.举一个简单的例子,考虑JLS Java语法的开头:

Literal:
    IntegerLiteral  
    FloatingPointLiteral

我想要一种方法来不必弄清楚我应该如何命令这两个规则来使解析成功.就目前而言,这样一个天真的实现:

literal = do {
    x <- try (do { v <- integer; return (IntLiteral v)}) <|>
         (do { v <- float; return (FPLiteral v)});
    return(Literal x)
}

无法工作......像"15.2"之类的输入将导致整数解析器首先成功,然后整个事情将会扼杀"." 符号.当然,在这种情况下,您可以通过重新订购两个产品来解决问题.然而,在一般情况下,发现这样的事情将成为一场噩梦,我很可能会错过一些案例.理想情况下,我想要一种方法让Parsec为我找出这样的东西.这可能,或者我只是想对图书馆做太多事情？Parsec文档声称它可以"解析上下文敏感的,无限的前瞻语法",所以看起来像我应该能够在这里做点什么.

我正在寻找一种算法,可以计算给定输入字符串的Kolmogorov复杂度的近似值.因此,如果K是字符串S的Kolmogorov复杂度,并且t表示时间,那么函数将表现得像这样...... limit(t-> inf)[K_approx(t,S)] = K.

我们知道在Objective-C中有两个主要的根类: NSObject和NSProxy.还有其他根(主要用于私人和遗留目的),如Object和NSLeafProxy.

定义一个新根是相当简单的:

@interface DDRoot <NSObject>

@end

@implementation DDRoot

//implement the methods required by <NSObject>

@end

我的问题是:你为什么要定义一个新的根类？是否有必要使用某些用例？

比方说,我有三个阵列a,b和c等长的N.每个数组的元素都来自一个完全有序的集合,但没有排序.我还有两个索引变量,i和j.对于所有人i != j,我想计算索引对的数量a[i] < a[j],b[i] > b[j]以及c[i] < c[j].有没有办法可以在低于O(N ^ 2)的时间复杂度下完成,例如通过创造性地使用排序算法？

注意:这个问题的灵感来源于,如果你只有两个数组,a并且b你可以找到索引对的数量,a[i] < a[j]并且b[i] > b[j] 在O(N log N)中使用合并排序.我基本上正在寻找三个数组的推广.

为简单起见,您可以假设任何数组中没有两个元素相等(无关系).

示例JavaScript代码如何使用Monad？我问,因为如果我能看到代码示例(而JavaScript是一种简单的函数式语言,它可能是用来学习它的最佳语言),那么理解Monad会更加清晰.

我试图证明以下内容:

如果G是乔姆斯基范式中的无上下文语法,那么对于任何字符串w属于长度n≥1的L(G),它需要恰好2n-1步才能得出w的任何推导.

我该如何证明这一点？

我已经看过几个地方简单地说已知P是NP和co-NP的交集的子集.证明P是NP子集的证据并不难找到.因此,为了表明它是交集的一个子集,剩下要做的就是表明P是co-NP的子集.什么可以证明这一点？非常感谢!

我一直想知道这件事.没有书明确说明这一点.

回溯正在探索所有可能性,直到我们发现一种可能性无法引导我们找到可能的解决方案,在这种情况下我们放弃它.

据我所知,动态编程的特点是重叠的子问题.那么,动态编程是否可以表示为缓存回溯(对于以前探索过的路径)？

谢谢