Is this even a function in Haskell ? If so, how should we read it?

Question

In the book of The Haskell Road to Logic, Math and Programming by Doets et.al., at page 103, it is given that

prime :: Integer -> Bool
prime n | n < 1     = error "not a positive integer"
        | n == 1    = False
        | otherwise = ldp n == n where 
  ldp    = ldpf primes
  ldpf (p:ps) m | rem m p == 0 = p
                | p^2 > m = m
                | otherwise = ldpf ps m 
  primes = 2 : filter prime [3..]

However, isn't the logic of this function circular ? I mean I think I'm quite comfortable with recursive functions, but I do not think that this is a recursive function. Even if it is, I'm not able to comprehend the logic of it, so my question is that how to read the logic of such a function.

Edit:

The reason why I'm confused is prime function uses the list primes, but to generate that list, we also use the function prime, so it seems that there is a circular logic, or I just do not understand recursive functions with lazy evaluation.

Please post code as text rather than screenshots. It makes reading, local testing, and searching far easier. — Carl, Aug 02 '18 at 15:30
Haskell is lazy; trace a call to `prime 2`, and notice how you never actually use `ps` in the call to `ldpf`. That means the recursive call to `prime` never actually gets made until you actually need it. — chepner, Aug 02 '18 at 15:41
Haskell is magic like that. This is too complex a function to contemplate, try grokking this Fibonacci sequence implementation first: `fibs = 0 : 1 : zipWith (+) fibs (tail fibs)`. Note that it produces an *infinite* list. — n. m. could be an AI, Aug 02 '18 at 17:16

Will Ness · Answer 1 · 2018-08-03T09:48:42.183

The ldp n == n condition can be equivalently re-written as

ldpf primes n == n
=
null [() | p <- takeWhile (\p -> p^2 <= n) primes, rem n p==0]
=
and [rem n p > 0 | p <- takeWhile (\p -> p^2 <= n) primes]

so for any given n, the call prime n = ldp n == n only needs to generate the list

primes = 2 : filter prime [3..] 
       = 2 : filter (\n -> ldpf primes n == n) [3..]
       = 2 : filter (\n -> and [rem n p > 0 
                                | p <- takeWhile (\p -> p^2 <= n) primes])
                          [3..]

up to the smallest prime number q > floor (sqrt $ fromIntegral n), and for that only the primes not greater than q's square root are needed. And to generate those, only the numbers not greater than the square root of that were needed. Pretty soon we end up not needing any primes at all, e.g.

prime 3
= 
ldpf primes 3 == 3
=
and [rem 3 p > 0 | p <- takeWhile (\p -> p^2 <= 3) (2 : filter prime [3..])]
= 
and [rem 3 p > 0 | p <- takeWhile (<= 3) (4 : 
                                      map (\p -> p^2) (filter prime [3..]))]
= 
and [rem 3 p > 0 | p <- []]
=
and []
=
True

because 2 already fails the predicate: (2^2 <= 3) = (4 <= 3) = False.

And when testing 4, primes will be probed for containing the number 3, but that's OK as we've just seen above:

prime 4
=
and [rem 4 p > 0 | p <- takeWhile (\p -> p^2 <= 4) primes]
= 
and [rem 4 p > 0 | p <- takeWhile (<= 4) (4 : 
                               map (\p -> p^2) (filter prime [3..]))]
= 
and [rem 4 p > 0 | p <- 4 : takeWhile (<= 4) (9 :
                               map (\p -> p^2) (filter prime [4..]))]
= 
and [rem 4 p > 0 | p <- 4 : []]
=
False

and we can check it at the GHCi prompt after that,

> :sprint primes
2 : 3 : _

(for the above to work you'll need to take primes out of the prime function and make it a top-level entity in its own right).

cf. [related answer](https://stackoverflow.com/questions/21688063/haskell-to-fix-or-not-to-fix/21720650#21720650), and [another one](https://stackoverflow.com/questions/13894417/double-stream-feed-to-prevent-unneeded-memoization/13895347#13895347). — Will Ness, Aug 04 '18 at 10:34

Is this even a function in Haskell ? If so, how should we read it?

1 Answers1