小编Foo*_*Bee的帖子

我是Haskell的新手,我正试图以流处理方式实现Euler的Sieve.

当我查看关于素数的Haskell Wiki页面时,我发现了一些神秘的流优化技术.在3.8维基的线性合并中:

primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes']) 
  where
    primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])

joinL ((x:xs):t) = x : union xs (joinL t)

它说

" 根据Melissa O'Neill的代码,这里引入了双素数反馈,以防止不必要的记忆,从而防止内存泄漏."

怎么会这样？我无法弄清楚它是如何工作的.

我在Scheme中写过Collat​​z猜想:

(define C
  (lambda (n)
    (cond
     ((eq? n 1) 1)
     ((even? n) (C (/ n 2)))
     (else (C (+ (* n 3) 1))))))

这是一个尾递归调用,但是当我调用时(C 121)我得到堆栈溢出:

guile> (trace C)
(C)
guile> (C 121)
[C 121]
[C 364]
[C 182]
[C 91]
[C 274]
[C 137]
[C 412]
[C 206]
[C 103]
[C 310]
[C 155]
[C 466]
[C 233]
[C 700]
[C 350]
[C 175]
[C 526]
[C 263]
[C 790]
[C 395]
[C 1186]
ERROR: Stack overflow
ABORT: (stack-overflow)

为什么正确的尾递归会导致溢出？如您所见,我使用Guile作为Scheme解释器(版本1.8.7).

Sieve of euler比Sieve of Eratosthenes具有更好的渐近复杂度，并且可以简单地用命令式语言实现。

我想知道是否有任何方法可以用流优雅地实现它。我已经检查了关于素数的haskell wiki，但是这两个实现比该wiki中的其他筛子（甚至试验分区！）慢数百倍。

所以我尝试自己写：

{-sieve of Euler-}
primesEU = 2:sieve [3,5 ..] where
    sieve (p:i:xt) = p:(sieve (i:xt) `minus` (lps i)) where
        lps i = map (i*) (takeWhile' (\p->(p<i)&&(mod i p /= 0)) primesEU)

takeWhile'::(t->Bool)->[t]->[t]
takeWhile' p [] = []
takeWhile' p (x:xs) = case (p x) of
    True  -> x:takeWhile' p xs
    False -> [x]

minus::(Ord t) => [t]->[t]->[t]
minus [] _ = []
minus xs [] = …

当我尝试向朋友解释一些简单的代码时,会发生一些奇怪的事情:

#include <stdio.h>
int main() 
{
    int x;
    printf("%x\n",x);
}

我已经尝试了数百万次,x的最后12位总是变成0xff0.我已经解除了代码,但仍然无法弄清楚这里发生了什么

我的操作系统是ubuntu10.10,编译器是gcc4.7.2