(Scheme) Take a list and return new list with coun

Question

I am attempting to accept a list, have it count the positive, negative, and zeros, and return a new list.

The only thing I notice as I'm debugging is that the list is iterating through, but it is not utilizing any of the conditionals. So its successfully recursively calling itself, and then it just errors once its empty.

(define (mydisplay value)
(display value)
(newline)
#t
)

(define neg 0)
(define z 0)
(define pos 0)

  (define (posneg lst)

  (cond 
    ((NULL? lst))
    (NEGATIVE? (car lst) (+ 1 neg))
    (ZERO? (car (lst)) (+ 1 z))
    (else (+ 1 pos))
   )

  (posneg (cdr lst))
)
(mydisplay (posneg '(1 2 3 4 2 0 -2 3 23 -3)))
(mydisplay (posneg '(-1 2 -3 4 2 0 -2 3 -23 -3 0 0)))
(mydisplay (posneg '()))

Answer 1

A better way to keep values while computing are by making a helper that has the data you want to keep as arguments. Updating the value is the same as recursing by providing a new value:

(define (pos-neg-zero lst)
  (define (helper pos neg zero lst)
    (cond ((null? lst) (pnz pos neg zero)) ; the result
          ((positive? (car lst)) (helper (+ 1 pos) neg zero (cdr lst)))
          ((negative? (car lst)) (helper pos (+ neg 1) zero (cdr lst)))
          (else (helper pos neg (+ zero 1) (cdr lst)))))
  (helper 0 0 0 lst))

I like @naomik's abstraction but unboxing/boxing for each iteration within the helper is perhaps overkill. Though having a contract is nice and both Racket and R6RS supports making your own types:

;; scheme version (r6rs) 
(define-record-type (pnz-type pnz pnz?)
  (fields 
    (immutable p pnz-p)
    (immutable n pnz-n)
    (immutable z pnz-z)))

;; racket
(struct pnz (p n z) #:transparent)

An alternative would be it returned the values as separate results with values or it could take a continuation:

(define (pos-neg-zero lst . lcont)
  (define cont (if (null? lcont) values (car lcont)))
  (define (helper pos neg zero lst)
    (cond ((null? lst) (cont pos neg zero)) ; the result
          ((positive? (car lst)) (helper (+ 1 pos) neg zero (cdr lst)))
          ((negative? (car lst)) (helper pos (+ neg 1) zero (cdr lst)))
          (else (helper pos neg (+ zero 1) (cdr lst)))))
  (helper 0 0 0 lst))


(pos-neg-zero '(1 -3 0))                            ; returns 1, 1, and 1
(pos-neg-zero '(1 -3 0) pnz)                        ; returns result as an object
(pos-neg-zero '(1 -3 0) list)                       ; returns result as a list
(pos-neg-zero '(1 -3 0) (lambda (p n z) (+ p n z))) ; does something with the results 

#!racket has optional arguments so the prototype could be just without having to have the first expression to check if there was passed an extra argument or not:

(define (pos-neg-zero lst (cont values))
  ...)

Answer 2

OK, my favorite technique to apply here is wishful thinking as I learned it from Gerald Jay Sussman and Hal Abelson in the Structure and Interpretation of Computer Programs (SICP) course. Particularly, video lecture 2B. Compound Data will be of interest to you.

Let's start by just pretending (wishing) with have this data container available to us that holds 3 values: one for positives, one for negatives, and one for zeros. We'll call it pnz.

The way to create one of these is simple

; construct a pnz that has 1 positive, 4 negatives, and 2 zeros
(define x (make-pnz 1 4 2))

To select the positives value

(positives x) ;=> 1

To select a negatives value

(negatives x) ;=> 4

To select the zeros value

(zeros x) ;=> 2

Forget for a moment that these procedures don't exist (yet). Instead, just wish that they did and begin writing the procedure to solve your problem.

We'll start with some pseudocode

; pseudocode
define count-pnz xs
  if xs is null? return (make-pnz p n z)
  if (car xs) is positive, update the positive count by one
  if (car xs) is negative, update the negative count by one
  if (car xs) is zero, update the zero count by one
  return count-pnz (cdr xs)

OK, that's pretty straight forward actually. Well, with one little gotcha. Notice I'm saying "update the count by one"? Well we need somewhere to store that count as the procedure is iterating. Let's make a slight adjustment to the pseudocode, this time including a pnz parameter to keep track of our current count

; pseudocode v2
define count-pnz xs pnz=(0 0 0)
  if xs is null? return (make-pnz p n z)
  if (car xs) is positive, nextpnz = (make-pnz p+1 n z)
  if (car xs) is negative, nextpnz = (make-pnz p n+1 z)
  if (car xs) is zero, nextpnz = (make-pnz p n z+1)
  return count-pnz (cdr xs) nextpnz

Now this procedure makes sense to me. In the simplest case where xs is an empty list, it will simply return a pnz of (0 0 0). If xs has any number of values, it will iterate through the list, one-by-one, and increment the corresponding value in the pnz container.

Translating this into scheme is a breeze

; wishful thinking
; we will define make-pnz, positives, negatives, and zeros later
(define (count-pnz xs (pnz (make-pnz 0 0 0)))
  (let [(p (positives pnz))
        (n (negatives pnz))
        (z (zeros pnz))]
    (cond [(null? xs) pnz]
          [(> (car xs) 0) (count-pnz (cdr xs) (make-pnz (+ 1 p) n z))]
          [(< (car xs) 0) (count-pnz (cdr xs) (make-pnz p (+ 1 n) z))]
          [(= (car xs) 0) (count-pnz (cdr xs) (make-pnz p n (+ 1 z)))])))

You'll notice I used a let here to make it easier to reference the individual p, n, z values of the current iteration. That way, when we detect a positive, negative, or zero, we can easily increment the appropriate value by simply doing (+ 1 p), (+ 1 n), or (+ 1 z) accordingly. Values that are not meant to be incremented can simply be passed on untouched.

We're getting extremely close. Our procedure make logical sense but we need to define make-pnz, positives, negatives, and zeros before it can work. By the way, this methodology of defining data objects by creating constructors and selectors to isolate use from representation is called data abstraction. You'll learn more about that in the video I linked, if you're interested.

So here's the contract that we need to fulfill

; PNZ CONTRACT
; pnz *must* behave like this
(positives (make-pnz p n z)) ⇒ p
(negatives (make-pnz p n z)) ⇒ n
(zeros     (make-pnz p n z)) ⇒ z

Let's implement it !

; constructor
(define (make-pnz p n z)
  (list p n z))

; positives selector
(define (positives pnz)
  (car pnz))

; negatives selector
(define (negatives pnz)
  (cadr pnz))

; zeros selector
(define (zeros pnz)
  (caddr pnz))

Pff, well that was easy as can be ! Using a list, car, cadr, and caddr made our job simple and it's easy to understand how pnz behaves.

Without further ado, let's see this thing in action now

(define answer (count-pnz '(-1 2 -3 4 2 0 -2 3 -23 -3 0 0)))
(positives answer) ; => 4
(negatives answer) ; => 5
(zeros answer)     ; => 3

And there you have it. Wishful thinking and a dash of data abstraction to the rescue.

Data abstraction is a very powerful concept. You might be thinking, "Why didn't we just use list in the count-pnz procedure instead of all of this constructor/selector ceremony?" The answer may not be readily apparent, but it is a bit too much for me to get into with this post. Instead, I sincerely do hope you check out the learning resources I linked as I'm certain they will be of great benefit to you.

---

@DavinTryon says "@naomik's answer could be defined in something other than a list (even just functions)."

Yep, that's totally true. Let's see make-pnz, positives, negatives, and zero implemented in a different way. Remember, the contract still has to be fulfilled in order for this implementation to be considered valid.

; constructor
(define (make-pnz p n z)
  (λ (f) (f p n z)))

; selectors
(define (positives pnz)
  (pnz (λ (p n z) p)))

(define (negatives pnz)
  (pnz (λ (p n z) n)))

(define (zeros pnz)
  (pnz (λ (p n z) z)))

Pretty cool. This demonstrates the beauty of data abstraction. We were able to completely re-implement make-pnz, positives, negatives, and zeros in a different way, but because we still fulfilled the original contract, our count-pnz function does not need to change at all.

Answer 3

First, let me say that @naomik's answer is awesome. This is the way to deconstruct the problem and build it up step by step.

When I first read the question, what I ended up thinking was:

How can I reduce a list of integers to the defined list '(p n z)?

So reduce means perhaps using foldl or foldr.

Here is example with foldr (returning a list in the format '(p n z)):

(define (count-pnz xs)
  (foldr (lambda (next prev)
       (cond ((= next 0) (list (car prev) (cadr prev) (+ 1 (caddr prev))))
         ((< next 0) (list (car prev) (+ 1 (cadr prev)) (caddr prev)))
         (else (list (+ 1 (car prev)) (cadr prev) (caddr prev)))))
     '(0 0 0) xs))

The body of the solution is the lambda we are using to reduce. Essentially, this just adds 1 to the p, n or z position of the list (using car, cadr and caddr respectively).

*note, this solution is not optimized.