WillNess

I'm late to the party but here goes:

>   divStep (start, n) = head $ [(x,q) | x <- [start .. isqrt n],
>                                let (q,r)=quotRem n x, r == 0] ++ [(n,1)]
    
>   isqrt n = floor . sqrt . fromIntegral $ n

>   pe3 n | n > 1 = fst . until ((== 1) . snd) divStep $ (2,n)
    
>   factorizing n = takeWhile ((> 1) . fst) . drop 1 . iterate divStep $ (2,n)

WillNess

(define (make-letter destination message)
  (define (dispatch x)
    (cond ((eq? x 'get-destination) destination)
          ((eq? x 'get-message) message)
          (else "Invalid option.")))
      dispatch)

(define (make-mailbox address)
  (let ((T '()))
    (define (add-post letter)

WillNess

Prelude Data.List> length [(x, y*y) | y <-[1..31], a<-[1..499],
     b<-[a..div 500 a-1], let x=a*b,  5<x, x<500, mod y x == 0]
85
(0.41 secs, 16891796 bytes)

Prelude Data.List> length [(x, y*y) | y <-[1..31], a<-[1..499],
     b<-[a..div 500 a-1], let x=a*b,  5<x, mod y x == 0]
85
(0.37 secs, 15572324 bytes)

WillNess

this is not a specific question. it is too broad; hard to say what is been asked here. I can answer 
with a general reply, but I don't know how helpful it will be. This is not how questions are supposed 
to be asked on SO, I think. Questions should be clear and specific, so that they, and the answers, can 
be helpful to others as well. On SO, please ask one specific question.
___

Each DCG rule `rule(...)` corresponds to a Prolog predicate `rule(... , L, Z)`, where `L, Z` form a 
difference-list. Your program is thus equivalent to:

<!-- language: lang-prolog -->

WillNess

primes4 :: [Integer]
primes4 = iterate
        (\p -> ([x |
                x <- [p + 1 ..],
                all (\p -> x `mod` p /= 0) $
                    takeWhile (\p-> p*p <= x) primes4 ] !! 0)
            )
        2

primes5 :: [Integer]

WillNess

it's kind of a [paramorphism][2]. Encoded via `foldr + tails`,

    import Data.List (tails)

    foo :: (a -> b -> b) -> (a -> b) -> [a] -> b
    foo g k = foldr (\xs r -> case xs of [x] -> k x; (x:_) -> g x r) undefined
                . init . tails

Richard Bird in his 2010 book "Pearls of Functional Algorithm Design" gives it a 
special name, [`foldrn`][1], with a direct implementation which follows the usual

WillNess

 fix$(<$>)<$>(:)<*>((<$>((:[{- thor's mother -}])<$>))(=<<)<$>(*)<$>(*2))$1

fix $ (<$>) <$> (:) <*>
   (  (<$> ((:[]) <$>) ) (=<<)
--    |----\~~~~~~~~~/-|
      <$>(*)<$>(*2)  
   )
$ 1

fix $ (fmap . (:)) <*>

WillNess

(define (prl k m)
  (define (print-line n)
    (cond ((> n 0) (display n)
                   (print-line (- n 1)))
          (else (newline))))
  (print-line k)
  (cond ((> m 1) (prl (+ k 1) (- m 1)))))

(defun prl (k m)                   ; (define (prl k m)
  (prog (n)

WillNess

Actually, with just some minor and cosmetic edits, your code becomes the *very* nice:

>    -- map (*i) [i ..] == map (*i) [i, i+1 ..] == [i*i, i*i+i ..]
>    -- sieve 2 [] where sieve i [] = (i:) $ sieve (i + 1) [i*i, i*i+i ..] 
>    --                 == 2 : sieve 3 [4, 6 ..]
>    primesA :: [Integer]
>    primesA = 2 : sieve 3 [4, 6 ..]
>    --
>    sieve p cs@(c : t)
>       | p == c    =     sieve (p + 1) t

WillNess

Hmm, very interesting. Your code is actual honest to goodness ***genuine sieve of Eratosthenes*** IMHO, counting its way along the ascending natural numbers by decrementing each counter that it sets up for each prime encountered, by 1 on each step. 

And it is very inefficient. [Tested on Ideone](http://ideone.com/EC3t4g) it runs at the same empirical order of growth `~ n^2.2` (at the tested range of few thousand primes produced) as the famously inefficient [Turner's trial division sieve](http://ideone.com/cWYH4g) (in Haskell).

Why? Several reasons. ***First***, no early bailout in your test: when you detect it's a composite, you continue processing the array of counters, `sieve`. You have to, because of the ***second reason***: you count the difference by decrementing each counter by 1 on each step, with 0 representing your current position. This is the most faithful expression of the original sieve IMHO, and it is very inefficient: today our CPUs know how to add numbers in O(1) time (if those numbers belon