Explain this chunk of haskell code that outputs a stream of primes

by

Contrary to what others have stated here, this function does not implement the true sieve of Eratosthenes. It does returns an initial sequence of the prime numbers though, and in a similar manner, so it’s okay to think of it as the sieve of Eratosthenes.

I was about done explaining the code when mipadi posted his answer; I could delete it, but since I spent some time on it, and because our answers are not completely identical, I’ll leave it here.

Firs of all, note that there are some syntax errors in the code you posted. The correct code is,

let sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) in sieve [2..]

  1. let x in y defines x and allows its definition to be used in y. The result of this expression is the result of y. So in this case we define a function sieve and return the result of applying [2..] to sieve.

  2. Now let us have a closer look at the let part of this expression:

    sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs)
    1. This defines a function sieve which takes a list as its first argument.
    2. (p:xs) is a pattern which matches p with the head of said list and xs with the tail (everything but the head).
    3. In general, p : xs is a list whose first element is p. xs is a list containing the remaining elements. Thus, sieve returns the first element of the list it receives.

    4. Not look at the remainder of the list:

      sieve (filter (\x -> x `mod` p /= 0) xs)
      1. We can see that sieve is being called recursively. Thus, the filter expression will return a list.
      2. filter takes a filter function and a list. It returns only those elements in the list for which the filter function returns true.

      3. In this case xs is the list being filtered and

        (\x -> x `mod` p /= 0)

        is the filter function.

      4. The filter function takes a single argument, x and returns true iff it is not a multiple of p.

  3. Now that sieve is defined, we pass it [2 .. ], the list of all natural numbers starting at 2. Thus,

    1. The number 2 will be returned. All other natural number which are a multiple of 2 will be discarded.
    2. The second number is thus 3. It will be returned. All other multiples of 3 will be discarded.
    3. Thus the next number will be 5. Etc.

More Related Contents:

  1. Does Haskell have tail-recursive optimization?
  2. How is this fibonacci-function memoized?
  3. What’s so bad about Lazy I/O?
  4. foldl versus foldr behavior with infinite lists
  5. New state of the art in unlimited generation of Hamming sequence
  6. double stream feed to prevent unneeded memoization?
  7. What does the exclamation mark mean in a Haskell declaration?
  8. Why is lazy evaluation useful?
  9. Non-Trivial Lazy Evaluation
  10. Is Haskell’s mapM not lazy?
  11. battleships game – Haskell [closed]
  12. What is a monad?
  13. Why shouldn’t I mix tabs and spaces?
  14. How to define a function in ghci across multiple lines?
  15. How do I deal with many levels of indentation?
  16. Memoization in Haskell?
  17. Wrong IO actions order using putStr and getLine
  18. Difference between `data` and `newtype` in Haskell
  19. How do functors work in haskell?
  20. Currying subtraction
  21. Haskell: how to evaluate a String like “1+2”
  22. Why does haskell’s bind function take a function from non-monadic to monadic
  23. What is a monad?
  24. Why is there “data” and “newtype” in Haskell? [duplicate]
  25. Why are side-effects modeled as monads in Haskell?
  26. haskell running out of memory with finite lists
  27. Haskell – simple constructor comparison (?) function
  28. Apostrophe in identifiers in Haskell
  29. Haskell: why the convention to name a helper function “go”?
  30. What is predicativity?

Leave a Comment