Scheme: "mcar: contract violation, expected: mpair, given: #<procedure:..."

Question

I am trying to use streams to generate a list of prime numbers in Scheme and I am encountering an error that I can't seem to wrap my head around. I have been spending hours trying different things and feel like I somewhat understand the problem, but I can't quite wrap my head around it. I have looked at similar posts, but I don't think I'm experienced enough to be able to relate them to my problem.

(define int-builder$
    (lambda (n)
      (cons  n (lambda() (int-builder$ (+ n 1))))))

(define filter-out-mults$
    (lambda (num lst)
          (if (= (modulo (car lst) num) 0)
              (filter-out-mults$ num (cdr lst))
              (cons (car lst) (lambda () (filter-out-mults$ num (cdr lst)))))))
(define take$
    (lambda (m s)
      (if (or (= m 0) (null? s))
          '()
          (cons (car s) (take$ (- m 1) ((cdr s)))))))

int-builder$ generates an infinite stream of integers starting at n. filter-out-mults$ should filter out any non-prime numbers. take$ takes the first m primes from the list.

Here is how I am running it, along with the error message:

> (take$ 10 (filter-out-mults$ 2 (int-builder$ 2)))


mcar: contract violation
expected: mpair?
given: #<procedure:.../prime-stream.ss:10:8>

I believe the problem has to do with how filter-out-mults$ is called in the if/else statement, in that a new int/procedure pair is not passed in, but I can't seem to figure out how to fix it. Any help would be greatly appreciated.

Solution 1

This can be solved with the SRFI-41 Streams library. It's available in many implementations including Racket. Racket also has it's own stream library with many similar procedures/syntax. SRFI-41 is available from both #!Racket and #!R6RS.

;(import (rnrs) (srfi :41)) ; For #!R6RS language
(require srfi/41)          ; For #!Racket language

(define-stream (filter-out-multipliers n v stream)
  (let ((a (stream-car stream)))
    (cond ((< a n) (stream-cons a (filter-out-multipliers n v (stream-cdr stream))))
          (else (filter-out-multipliers (+ n v) v (if (= a n) (stream-cdr stream) stream))))))

(define-stream (primes stream)
  (let ((a (stream-car stream)))
    (stream-cons a (primes (filter-out-multipliers (+ a a) a (stream-cdr stream))))))

(stream->list (stream-take 20 (primes (stream-from 2))))
; ==> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)

Solution 2

I managed to answer my own question shortly after posting and wanted to share my solution.

In filter-out-mults$, each

(cdr lst)

needed to be

((cdr lst))

Since int-builder$ is a stream, it returns pairs containing an integer and a procedure to get the next integer token. For example:

> (int-builder$ 2)
(2 . #<procedure:...prime-stream.rkt:10:8>)

In order to get the next integer, the procedure needs to be invoked. The problem was that (cdr lst) would return the procedure, but not invoke it. To illustrate:

> (cdr (int-builder$ 2))
#<procedure:...prime-stream.rkt:10:8>

Once the extra parentheses were added, the next pair was returned:

> ((cdr (int-builder$ 2)))
(3 . #<procedure:...hedgerh.lab6.rkt:10:8>)

Hopefully that helps someone.

Here is the full definition of filter-out-mults$:

(define filter-out-mults$
    (lambda (num lst)
      (if (null? lst)
          '()
          (if (= (modulo (car lst) num) 0)
              (filter-out-mults$ num ((cdr lst)))
              (cons (car lst) (lambda () (filter-out-mults$ num ((cdr lst)))))))))

Comments

[leppie]

(cons n (lambda() (int-builder$ (+ n 1)))) and then (filter-out-mults$ num (cdr lst)) => KABOOM! (you probably want list instead of cons there)

[Harry Hedger]

I figured it out. As I mentioned in my edit, I needed an extra set of parentheses around (cdr lst) in order to invoke it. The lambda prior to (filter-out-mults$ num ((cdr lst))) actually makes the procedure lazy so that it doesn't go forever. Thanks for the help!

[Sylwester]

Why don't you use SRFI-41 Streams library?

[leppie]

You should post your solution as the answer.