Avoid using set! into functional programming style algorithm

Question

I'm not sure if I can ask this question here. If this is not the right place, please tell me and I will delete it.

I'm learning Racket and someone has told me something about avoiding using set! in functional programming style. But I'm confused, I don't understand the meaning of "functional programming style". Just to learn, I want to ask this question.

I have the following code:

 (define lst1 '())

 (do ([i n (- i 1)])
   ((zero? i))
   ; Get an item.
   (set! item (random-chooser original-list))
   ; Insert it into an auxiliary list, lst1
   (set! lst1 (cons item lst1))
   ; Remove the item from the original list
   (set! original-list (remove item original-list)))

 (append (list lst1) (list original-list))))))

This code is working perfectly. I have to choose n items from original-list list randomly, without repetition. And then create a list with two sub-lists with the n items chosen in lst1 and as the second sub-list, the remaining items on original-list.

Is there a better way to do this without using set!?

Answer 1

Solution

shuffle is really a good solution and very functional. Functional style forbids mutation/change of existing/defined variable values (thus no set!). Rather one creates/copies an existing object and mutates it or creates it in mutated form. shuffle creates/copies the original list in mutated order.

You can use take and drop to get or leave the first n position of any list. Or use the split-at function.

However, since this returns the result as values but the task was to return a list, you use let-values to bind the two return results and bind them into a single list.

(define (choose-n-and-rest lst n)
  (let-values ([(chosen rest) (split-at (shuffle lst) n)])
    (list chosen rest)))

or:

(define (choose-n-and-rest lst n)
  (let ((new-lst (shuffle lst)) ; so that `take` & `drop` use the same shuffled list
    (list (take new-list n) (drop new-list n))))

But as you can read here, split-at might be slightly more efficient than the combination of take and drop.

Try it out with:

(choose-n-and-rest '(a b c d e 1 2 3 4 5) 3) 
;; e.g. '((a 4 2) (1 b 3 5 c e d))

By the way, set! or better: mutating functions is/are not completely forbidden in lisp-style functional programming. The reason is performance. Copying every lengthy list is costly. An example is common-lisp's nreverse which changes order of original list (reverses the order). The non-mutating reverse creates a new list with elements in reverse order. But for that it has to copy. If you mutate local variables (defined by let), it can lead to gain of performance - but very cautiously, of course, since mutation is a dangerous thing.

Answer 2

In functional programming we write code by composing existing procedures whenever possible. All of the operations you're doing can be expressed by using list procedures:

(define n 5)
(define lst '(0 1 2 3 4 5 6 7 8 9))

(let ((shuffled (take (shuffle lst) n)))
  (list shuffled (remove* shuffled lst)))

=> '((5 8 9 6 2) (0 1 3 4 7))

In the end you'll have two lists, the first contains n elements randomly chosen from the original list, and the second contains the remaining elements.

In functional programming we try really hard to avoid explicit loops (we use recursion in its place) and set!. We use existing procedures, composition, and create new data (say, lists) instead of modifying existing data.

I can tell that you come from a procedural background, it's kinda hard to let go of loops and assignments, but that's the beauty of functional programming: it makes you think differently about how you solve problems. Mutating data is the source of many difficulties, especially when doing concurrent programming, that's why FP avoids it at all costs.

Note that mutating data is avoided as much as possible, but Scheme, being an impure functional programming language allows it. For instance, the shuffle procedure must change state at some point, when picking random values. But it's all encapsulated away, and in normal, day-to-day programming you can do most of your work without ever using set!.

Answer 3

In order to remove the use of set! and explicit loops, you need to use recursion, with the "updated" values being passed in as parameters.

Scheme has some nice syntactic sugar around letrec (recursive let, used for bindings that can reference themselves), which allows you to create and call a function in one go: named let. This is often used for looping, so the function is often called loop, but it can be called anything else. The important thing is to call it with modified parameters when looping, and not to call it when the loop is over.

(define (take-random n lst)
  ; Syntactic sugar that creates a 3-parameter function called `loop` and calls it
  ; with the values `n`, `'()` and `lst`
  (let loop ((n n)
             (picked '())
             (lst lst))
    ; If the loop counter reaches zero or if there are no more items to take
    (if (or (zero? n) (null? lst))
        ; Then combine the picked items and the remaining unpicked items
        (list picked lst)
        ; Otherwise, pick a random item from the list
        (let ((item (random-chooser lst)))
          ; And loop again, decreasing the loop counter to be nearer zero,
          ; adding the picked item to the list of picked items, and removing
          ; it from the list of remaining items to pick from
          (loop (- n 1)
                (cons item picked)
                (remove item lst))))))

;; Examples
(take-random 3 '(1 2 3 4 5 6))
; => ((4 1 6) (2 3 5))
(take-random 3 '(1 2))
; => ((2 1) ())

Óscar López's answer is a good presentation of the more functional way of doing this.