CODEWITHSUNDEEP
schemeracket
Noam
Noam

Reputation: 1804

Scheme: sort elements by pivot

I'm new to Scheme and to functional programming so please be gentle. I'm trying to implement a function that takes a list and a pivot and return a list that contains the following 2 lists:

One for all elements that are less or equal to the pivot,

and one for all the elements that are greater than the pivot.

So I wrote the following code (EDITED (& WORKING) CODE - PROBLEM SOLVED):

define helper (lambda (lst pivot)
             (define lst1 null)
             (define lst2 null)
             (define my-split (lambda (lst pivot lst1 lst2)
                                 (if (null? lst)
                                     (list lst1 lst2)
                                     (if (<= (car lst) pivot)
                                         (my-split (cdr lst) pivot (cons (car lst) lst1) lst2)                                         
                                         (my-split (cdr lst) pivot lst1 (cons (car lst) lst2))))))                                   
              (my-split lst pivot lst1 lst2)))

My current problem is that lst1 and lst2 are null at the end of the run so I guess the problem is with the lines (cons (car lst) lst1) & (cons (car lst) lst2))).

I saw some implementations on the web which use some complex commands that I'm not allowed to use (yes, it's homework).

Please offer ways to fix my code rather than offering your own.

Thanks

Upvotes: 0

Views: 355

Answers (2)

Sylwester
Sylwester

Reputation: 48745

Just like an expression like str.concat("hey") in Java doesn't change what str is (cons 1 lst1) doesn't change what lst1 is. It just returns a new value. Most of your function consist of dead code and if you really want to learn functional programming then altering bindings and objects are off limits.

You need to do something like this:

(define (count-odds lst)
  (define (helper lst odds)
    (cond ((null? lst) 
           odds)
          ((odd? (car lst)) 
           (helper (cdr lst) (+ 1 odds)))
          (else 
           (helper (cdr lst) odds))))    
  (helper lst 0))

(count-odds '(1 2 3))
; ==> 2

We never alter odds, we just update what is sent to the next recursion. Since Scheme has tail call elimination this is just like updating the variable in a while loop without actual mutation.

Upvotes: 1

Brendan Cannell
Brendan Cannell

Reputation: 679

You correctly identified the two lines that are the main problem. cons just builds and returns a new list, whereas you're trying to mutate the variables lst1 and lst2. The correct way to do this is (set! lst1 (cons (car lst) lst1)) and (set! lst2 (cons (car lst) lst2)). Keep in mind, though, that good functional programming style avoids mutation. A good way to do that in this case would be to pass the two sub-lists as arguments as you recur down the main list, then return them when you get to the end.

Upvotes: 1

Related Questions