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


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 . #<>)

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))

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)))))))))
Harry Hedger
Author by

Harry Hedger

Updated on June 04, 2022


  • Harry Hedger
    Harry Hedger 6 months

    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:.../>

    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.

    • leppie
      leppie over 8 years
      (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
      Harry Hedger over 8 years
      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
      Sylwester over 8 years
      Why don't you use SRFI-41 Streams library?
    • leppie
      leppie over 8 years
      You should post your solution as the answer.