functional programming / racket translating imperative nested loops

Question

If you have an algorithm that calls for something like (in C):

int pts[length];

for(int i = 0; i < length; ++i){
   for(int j = 0; j < length; ++j){
      if(pts[i] == pts[j]){

         //modify both pts[i] and pts[j] somehow

      }
   }
}

How would you translate this into a functional style? Meaning that it returns an array or list of points with the modifications without changing the original. Answer can be demonstrated with nested recursion, map/filter,etc, Racket style for loops or something else. While I'm trying this in Racket, I'm open to answers in other languages.

Answer 1

The first thing to say here is that there are algorithms that make a lot more sense in an imperative style, and most functional languages provide you with the mechanisms you need to do this. You use Racket as an example, and it would be totally reasonable to translate this code to nested loops (e.g. using racket's for) that perform mutation.

However, there are also algorithms that make perfect sense in a functional style; the answer to this is going to depend a lot on the modify both pts[i] and pts[j] somehow.

Let's make something up; suppose I have an array of boys at a party, and each one is wearing a dress, and if two of them are wearing the same dress, their happiness is decreased. This is the first thing that pops into my head, but honestly it generalizes pretty well.

One way to do this would be with a nested loop, as you describe. In order to do it functionally, I think I might just write it like this:

#lang racket

;; a boy is a structure: (make-boy symbol number)
(define-struct boy [dress-color happiness]
  #:transparent)

;; given a list of boys,
;; decrease each boy's happiness
;; by 3 for each other boy wearing the same color
;; dress
;; list-of-boys -> list-of-boys
(define (oh-noes boys)
  (oh-noes-helper boys (boy-colors boys)))

;; given a list of boys and a list of all the colors
;; decrease each boy's happiness
;; by 3 for each other boy wearing the same color
;; dress
;; list-of-boys list-of-colors -> list-of-boys
(define (oh-noes-helper boys all-colors)
  (cond [(empty? boys) empty]
        [else (cons (adjust-boy (first boys) all-colors)
                    (oh-noes-helper (rest boys) all-colors))]))

;; given a boy and a list of all the dress colors,
;; decrease the boy's happiness by three for every
;; *other* boy wearing the same color dress
;; boy list-of-colors -> boy
(define (adjust-boy boy all-colors)
  (make-boy (boy-dress-color boy)
            (- (boy-happiness boy)
               (* 3 (sub1 (num-occurrences (boy-dress-color boy)
                                           all-colors))))))

;; given a list of boys, return a list of colors
;; let's just use map...
(define (boy-colors boys)
  (map boy-dress-color boys))

;; given a list of colors, return the number of occurrences of that
;; color in the list
;; too lazy, just using foldl...
(define (num-occurrences element list)
  (length (filter (λ (c) (equal? element c)) list)))


(require rackunit)
(check-equal? (boy-colors (list (make-boy 'blue 13)
                             (make-boy 'green 15)
                             (make-boy 'orange 9)
                             (make-boy 'green 2)
                             (make-boy 'orange 2)
                             (make-boy 'green 1)))
              (list 'blue 'green 'orange 'green 'orange 'green))

(check-equal? (num-occurrences 'green
                               (list 'blue 'green 'orange
                                     'green 'orange 'green))
              3)

(check-equal? (oh-noes (list (make-boy 'blue 13)
                             (make-boy 'green 15)
                             (make-boy 'orange 9)
                             (make-boy 'green 2)
                             (make-boy 'orange 2)
                             (make-boy 'green 1)))
              (list (make-boy 'blue 13)
                    (make-boy 'green 9)
                    (make-boy 'orange 6)
                    (make-boy 'green -4)
                    (make-boy 'orange -1)
                    (make-boy 'green -5)))

Please note that I wrote this in a very HtDP-heavy style; you could do this in just a few lines if you gave yourself free rein of Racket.

How does this compare to the original implementation? Well, they both have n^2 running time. If you want to improve this, you probably want to create a small hash table mapping colors to number of occurrences, in both the imperative and functional solutions.

EDIT:

Here's the whole thing again in 5 loc:

;; once again more rackety-small
(define (oh-noes2 boys)
  (define colors (map boy-dress-color boys))
  (for/list ([b (in-list boys)])
    (match-define (struct boy (c h)) b)
    (boy c (- h (* 3 (sub1 (length (filter (λ(x)(eq? x c)) colors))))))))

Answer 2

If you want to use list to do stuff, then:

(define (my-list-update lst idx val) ; older version of Racket doesn't have list-update
  (if (= idx 0)
      (cons val (rest lst))
      (cons (first lst) (my-list-update (rest lst) (- idx 1) val))))

(define LENGTH 10)
(define initial-lst (build-list LENGTH (lambda (_) 0))) ; create list consisting of 0 for LENGTH entries
(define arr
  (foldl
    (lambda (i lst)
      (foldl
        (lambda (j lst) ; shadowing, change if you don't like it
          (my-list-update lst i (+ (list-ref lst i) (+ i j))))
        lst (range LENGTH))) ; for j = 0 -> LENGTH - 1
    initial-lst (range LENGTH))) ; for i = 0 -> LENGTH - 1

The above code is almost equivalent to the following pseudocode:

int arr[N] = initial_lst;
for(int i = 0; i < N; ++i){
    for(int j = 0; j < N; ++j){
        arr[i] += i + j; // not exactly, in Racket, we didn't mutate anything
    }
}

Post-Discussion

How would you translate this into a functional style?

Well, what is the definition of "functional style"? In particular, do you really want an array as the output? Because array is a mutable data structure, it is not purely functional. Is this acceptable to you?

returns an array or list of points with the modifications without changing the original.

If you want to output an array without modifying the original array. That's easy: just copy all entries from the original array to a new array. Then, you can mutate the new array, do whatever you want to do with it, and return it. However, this becomes the imperative style instead.

If you really want the program to be purely functional, arrays are not the option for you. Using lists like the above example is not ideal because updating and getting takes O(n), while arrays could do it in O(1). There is a better approach: use Okasaki's random access list. This data structure is purely functional, while letting you update an entry in O(log n). Its implementation is really simple (compared to some data structures like AVL Tree), and you can use it in place of lists easily.

Answer 3

You really don't do it like that in Algol either. You use a hash table to get rid of the O(n²).

;; finds and replaces duplicates in O(n) time
(define (replace-duplicates replacement-proc lst)
  ;; this goes through the list once
  ;; mapping every value into a hash
  ;; with their frequency
  (define h
    (foldl (lambda (e h)
             (hash-update h e add1 0))
           (hash)
           lst))

  ;; goes through the list once more
  ;; and replacing the elements that has
  ;; a frequency over 1 with the result of 
  ;; (replacement-proc e)
  (map (lambda (e)
         (if (> (hash-ref h e) 1)
             (replacement-proc e)
             e))
       lst))

(replace-duplicates (lambda (x) 'duplicate) 
                    '(1 2 3 4 1)) 
; ==> (duplicate 2 3 4 duplicate)