Create a partition of list into three parts in scheme

Question

I am trying to find a way to split a list up into three parts. I have used a helper function and the parameters should be as follows: It evaluates to a list of three lists, containing 1) the items in the list less than pivot, 2) the items in the list equal to pivot, and 3) the items in the list greater than pivot.

(define (partition lst item)
  (define (partition-iter lst less same greater)
   (cond ((null? lst)(list less same greater ))
      ((< (car lst) item)(partition-iter (cdr lst)
                                         (cons (car lst) less)
                                         same
                                         greater ))
      ((= (car lst) item)
       less
       (cons (car lst) same)
       (else
        (partition-iter (cdr lst) (cons (car lst) greater))))))
(partition-iter lst '() '() '()))    

everything up to the else clause should work but after that i'm stuck. Any help is appreciated

Answer 1

Here's you code, indented so that the corresponding items are visually aligned:

(define (partition lst item)
  (define (partition-iter lst less same greater)
   (cond
      ((null? lst)
                      (list less same greater ))

      ((< (car lst) item)
                      (partition-iter (cdr lst)
                                      (cons (car lst) less)
                                      same
                                      greater))
      ((= (car lst) item)
                      less

                      (cons (car lst) same)

                      (else
                                      (partition-iter (cdr lst)
                                                      (cons (car lst) greater))))))
  (partition-iter lst '() '() '()))

I think you can see there's something wrong with it right away, now. It's asymmetrical, all out of wack, even if the parens are balanced. An else clause inside another cond clause? What is that??

The moral is, don't be afraid to use white space to see better. Lots and lots of white space.

Without it, Scheme tends to look like an impenetrable wall of words, parens or no parens. And the recommended indentation style. Does. Not. Help.

The fix is obvious, minimal, and simple: just complete the code in the same style you (??) started writing it. Handle the other two cases, building the three interim lists while iterating along the input list by taking repeated cdrs in each of the three cases:

(define (partition lst item)
  (define (partition-iter lst less same greater)
   (cond
      ((null? lst)
                      (list less same greater ))

      ((< (car lst) item)
                      (partition-iter (cdr lst)
                                      (cons (car lst) less)
                                      same
                                      greater ))
      ((= (car lst) item)
                      (partition-iter (cdr lst)
                                      less
                                      (cons (car lst) same)
                                      greater ))

      (else  ; (> (car lst) item)             ; keep it here for documentation!
                      (partition-iter (cdr lst)
                                      less
                                      same
                                      (cons (car lst) greater) )) ))
  (partition-iter lst '() '() '()))

I don't even have to load it into DrRacket now to see that it's alright.

Symmetry is beautiful. Symmetry is right.

---

BTW, in a pattern-matching pseudocode with guards, it could be written as

partition lst item = partition-iter lst [] [] []
  where
  partition-iter [] less same greater  =  [less,      same,      greater]
  partition-iter [a, ...lst] less same greater 
     | a < item   =  partition-iter  lst  [a, ...less]   same    greater 
     | a == item  =  partition-iter  lst  less    [a, ...same]   greater
     | else       =  partition-iter  lst  less    same    [a, ...greater]

which I think is much more visually apparent. Going back and forth between it and the proper Scheme is a matter of purely syntactical transformations.

Answer 2

The current helper function, partition-iter, will not work due to some severe mistakes in its design. But first, let me provide two versions which work:

The first (simple) version,

#lang racket

; LoN = List-of-Numbers

; partition :: LoN Number -> List-of-LoN
(define (partition1 lst pivot)
  (local([; auxiliary function
          ; part :: LoN LoN LoN LoN -> List-of-LoN
          define (part xs LT EQ GT)
          ; if empty list
          (if (null? xs) (list LT EQ GT)
              ;else
              (let* ([head (first xs)]
                     [tail (rest  xs)]
                     [prtd (part tail LT EQ GT)]                    
                     [LT* (first prtd)]
                     [EQ* (second prtd)]
                     [GT* (third prtd)])
                ;--in--
                (cond
                  ; if x < pivot, add the element to LT
                  [(< head pivot) (list {cons head LT*} EQ* GT*)]
                  ; if x = pivot, add the element to EQ
                  [(= head pivot) (list LT* {cons head EQ*} GT*)]
                  ; if x > pivot, add the element to GT
                  [else (list LT* EQ* {cons head GT*})]
                  )
                ) ) ]
         )
    ;--in--
    (part lst null null null)
    )
  )

The second version, which is closer to your implementation, but uses fold:

#lang racket

; partition :: LoN Number -> List-of-LoN
(define (partition2 lst pivot)
  (local([; auxiliary function
          ; part :: LoN LoN LoN LoN -> List-of-LoN
          define (part x LT-EQ-GT)
          (local ([define-values (LT* EQ* GT*) (apply values LT-EQ-GT)])
            ;--in--
            (cond
              ; if x < pivot, add the element to LT
              [(< x pivot) (list {cons x LT*} EQ* GT*)]
              ; if x = pivot, add the element to EQ
              [(= x pivot) (list LT* {cons x EQ*} GT*)]
              ; if x > pivot, add the element to GT
              [else (list LT* EQ* {cons x GT*})]
              )
            ) ]
         )
    ;--in--
    (foldr part '(() () ()) lst)
    )
  )

Try eg.,

(partition2 '(1 2 3 4 4 3 4 5 6) 4) ;; yields '((1 2 3 3) (4 4 4) (5 6)).

Notice that the second (fold-) version is faster (and better imo).

Finally, your implementation has mistakes in the following lines (line-numbering begins at 1):

-- lines 4-7 should be:

(partition-iter (cdr lst) (cons (car lst) less) same greater)

-- lines 9-10 should be:

(partition-iter (cdr lst) less (cons (car lst) same) greater)

-- line 12 should be:

(partition-iter (cdr lst) less same (cons (car lst) greater))

Finally, with your current implementation, you should use foldl or foldr (or something like that) in your last line.