1

I wish to create a function in Scheme that takes in a predicate and a list of elements, and then outputs two separate lists. One with elements of the original list that MATCH the given predicate, and one with elements that DON'T match it.

The code I have right now I believe should isolate those which match the predicate and output a list of them but the code will not work.

    (define tear
(lambda (pred xs)
    (cond[(null? xs) '()]
         [(list? (car xs))(cons((tear (pred (car xs)))(tear (pred (cdr xs)))))]
         [(pred (car xs))(cons((car xs)(tear (pred (cdr xs)))))]
         [else tear (pred (cdr xs))])))
(tear number? '(1 2 3 a b c))

The resulting output on my compiler is:

    tear: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1
  arguments...:
   #f
  context...:
   /home/jdoodle.rkt:2:4: tear
Command exited with non-zero status 1

Any help/info that you can give would be much appreciated.

Paddy Gorry
  • 21
  • 2
  • What is the purpose of the second clause? `[(list? (car xs))(cons((tear (pred (car xs)))(tear (pred (cdr xs)))))]` – coredump Jul 30 '18 at 11:01
  • `[else tear (pred (cdr xs))]` is not calling `tear`, I think you meant `[else (tear ...)]` – coredump Jul 30 '18 at 11:02
  • `(cons((car xs)(tear (pred (cdr xs)))))`: you are calling `cons` with one argument, careful about extraneous parentheses. – coredump Jul 30 '18 at 11:04
  • the second clause is used to check if the first element is a list itself, my understanding is that i need to do this to reduce it down to dealing with elements rather than the list. I see now where my bracketing was wrong, i fixed that but the function still outputs nothing – Paddy Gorry Jul 30 '18 at 11:19
  • 1
    (1) Your inputs are a predicate and a list of elements. You are not supposed to care if the elements themselves are lists or not. Once you eliminated the empty list case, you know you have a non-empty list. (2) You can check yourself with the interpreter, see for example: https://repl.it/repls/RotatingExcitableNumericalanalysis – coredump Jul 30 '18 at 11:23
  • Ah of course that's rather silly of me, I'm working off examples from a bad lecturer so there's not much in the way of notes to fully understand the ins and outs of the code. How would I split the output into elements that match the predicate and elements that don't? – Paddy Gorry Jul 30 '18 at 11:27
  • Even if your code worked, it will have problems with long lists. A classic approach to fix this is to have a local auxiliary function which gets called with one or more extra 'accumulator' arguments, and then iterates tail-recursively down the list. –  Jul 30 '18 at 11:33
  • You need to define a data-structure D which represents the two lists you want to build. It could be as simple as a cons cell, with the car the list of matches and the cdr the list of non-matches. Then, define an auxiliary function F which takes such a D value, an element E, a predicate P and compute the next D value by putting E in front of the appropriate list, according to whether (P E) holds. You main recursive functions builds a series of D values starting from an empty D by calling F successively on each element E with the previously known D. – coredump Jul 30 '18 at 11:39
  • 1
    google sheep trick from the pitmanual, for a related read. – Will Ness Jul 30 '18 at 11:52

3 Answers3

5

Lets fix your code step by step. Adding indentation and whitespace to make it readable:

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       '()]
      [(list? (car xs))
       (cons ((tear (pred (car xs))) (tear (pred (cdr xs)))))]
      [(pred (car xs))
       (cons ((car xs) (tear (pred (cdr xs)))))]
      [else 
       tear (pred (cdr xs))])))

(tear number? '(1 2 3 a b c))

The first problem I see is a problem of putting parentheses on the inside (around the arguments) of a function call instead on the outside. You do this with cons and with the recursive calls to tear. For instance in tear (pred (cdr xs)) you should move the first paren to before the function. Remember that parentheses in an expression almost always mean a function call in the shape of (function argument ...).

  • (cons (A B)) should be rewritten to (cons A B)
  • (tear (Pred Xs)) should be rewritten to (tear Pred Xs)
  • tear (Pred Xs) should be rewritten to (tear Pred Xs)

With these fixes your code looks like this:

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       '()]
      [(list? (car xs))
       (cons (tear pred (car xs)) (tear pred (cdr xs)))]
      [(pred (car xs))
       (cons (car xs) (tear pred (cdr xs)))]
      [else 
       (tear pred (cdr xs))])))

(tear number? '(1 2 3 a b c))
;=> (1 2 3)
(tear number? '(1 2 "not a number" 3 4))
;=> (1 2 3 4)

However, it still does something weird when there's a nested list:

(tear list? (list '(1 2 3) "not a list" '(4 5)))
;=error> (() ())

To be consistent it should put the two lists into a list: ((1 2 3) (4 5)). To do that just remove the second cond case:

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       '()]
      [(pred (car xs))
       (cons (car xs) (tear pred (cdr xs)))]
      [else 
       (tear pred (cdr xs))])))

(tear number? '(1 2 3 a b c))
;=> (1 2 3)
(tear list? (list '(1 2 3) "not a list" '(4 5)))
;=> ((1 2 3) (4 5))

It now seems to do exactly half of what you want. You want it to return two lists: one for elements that passed, and one for the elements that failed. It currently is returning just the first list.

The first thing you should do is document how it returns those two lists. Since there are always exactly two, you can return them as multiple values. 

;; tear returns two values:
;;  - a list of the elements of `xs` that passed `pred`
;;  - a list of the elements of `xs` that failed `pred`

There are two parts of using multiple values: returning them and receiving them. Use (values A B) to return them, and (let-values ([(A B) ....]) ....) to match on a result, like the result of a recursive call.

That means every recursive call like this (f .... (tear ....) ....) should become

(let-values ([(A B) (tear ....)])
  (values (f .... A ....)
          ???))

Applying that to your code:

;; tear returns two values:
;;  - a list of the elements of `xs` that passed `pred`
;;  - a list of the elements of `xs` that failed `pred`
(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       (values '()
               ???)]
      [(pred (car xs))
       (let-values ([(A B) (tear pred (cdr xs))])
         (values (cons (car xs) A)
                 ???))]
      [else
       (let-values ([(A B) (tear pred (cdr xs))])
         (values A
                 ???))])))

Now to fill in the ??? holes, use examples.

  • (tear number? '()) should return two empty lists: () ()
  • (tear number? '(1 2)) should return a full list and an empty list: (1 2) ()
  • (tear number? '(a b)) should return an empty list and a full list: () (a b)

The first example corresponds to the first ??? hole, the second example corresponds to the second hole, and so on.

This tells us that the first hole should be filled in with '(), the second hole should be filled in with B, and the third hole should be filled in with (cons (car xs) B).

(define tear
  (lambda (pred xs)
    (cond
      [(null? xs) 
       (values '() '())]
      [(pred (car xs))
       (let-values ([(A B) (tear pred (cdr xs))])
         (values (cons (car xs) A)
                 B))]
      [else
       (let-values ([(A B) (tear pred (cdr xs))])
         (values A
                 (cons (car xs) B)))])))

(tear number? '(1 2 3 a b c))
;=> (1 2 3)
;   (a b c)
(tear list? (list '(1 2 3) "not a list" '(4 5)))
;=> ((1 2 3) (4 5))
;   ("not a list")
Alex Knauth
  • 8,133
  • 2
  • 16
  • 31
3

This is a classic fold use-case. You're aggregating the list into two lists : 

(define tear (lambda (pred lst)
    (fold-right ; Aggregate over lst
      (lambda (elem agg) 
        (let ((accepted (car agg)) 
              (rejected (cadr agg)))
          (if (pred elem) 
; Create a new agg by adding the current element to the accepted list
              `(,(cons elem accepted) ,rejected) 
; Or, if the predicate rejected the element, 
; Create a new agg by adding the current element to the rejected list
              `(,accepted ,(cons elem rejected))))) 
      `(() ())
      lst)))

So, if you use even? as your predicate, you can get:
> (tear even? `(1 2 3 4 5 6 7 8)) ((2 4 6 8) (1 3 5 7))

Neowizard
  • 2,981
  • 1
  • 21
  • 39
1

Here's another way you can do it using continuation-passing style; this puts the recursive call in tail position.

(define (partition p xs (return list))
  (if (null? xs)
      (return null null)
      (partition p
                 (cdr xs)
                 (lambda (t f)
                   (if (p (car xs))
                       (return (cons (car xs) t)
                               f)
                       (return t
                               (cons (car xs) f)))))))

(partition number? '())
;; => '(() ())

(partition number? '(a 1 b 2 c 3))
;; => '((1 2 3) (a b c))

(partition list? '(1 2 (3 4) (5 6) 7 8))
;; => '(((3 4) (5 6)) (1 2 7 8))

Above, we make use of Racket's default arguments. Below we show how to define partition using a helper function instead

;; procedure above, renamed to partition-helper
(define (partition-helper p xs return)
  ...)

;; new procedure without optional parameter
(define (partition p xs)
  ;; call helper with default continuation, list
  (partition-helper p xs list))

Comments may help distill some of the style's mysterious nature

;; default continuation is `list`, the list constructor procedure
(define (partition p xs (return list))
  (if (null? xs)

      ;; base case: empty list; return the empty result
      (return null null)

      ;; inductive case: at least one x; recur on the tail...
      (partition p
                 (cdr xs)

                 ;; ...specifying how to continue the pending computation
                 (lambda (t f)
                   (if (p (car xs))

                       ;; if predicate passes, cons x onto the t result
                       (return (cons (car xs) t)
                               f)

                       ;; otherwise cons x onto the f result
                       (return t
                               (cons (car xs) f)))))))

@WillNess asks why we delay evaluating the predicate; I don't have a reason other than I think the readability above is pretty good. We can alter the implementation to check the predicate right away, if we please. The impact here is very subtle. If you don't see it, I encourage you to play pen-and-paper evaluator and compare the two processes to understand it.

;; default continuation is `list`, the list constructor procedure
(define (partition p xs (return list))
  (if (null? xs)

      ;; base case: empty list; return the empty result
      (return null null)

      ;; inductive case: at least one x; recur on the tail...
      (partition p
                 (cdr xs)

                 ;; ...specifying how to continue the pending computation
                 (if (p (car xs))

                   (lambda (t f)
                       ;; if predicate passes, cons x onto the t result
                       (return (cons (car xs) t)
                               f))

                   (lambda (t f)
                       ;; otherwise cons x onto the f result
                       (return t
                               (cons (car xs) f)))))))
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Mulan
  • 129,518
  • 31
  • 228
  • 259