Returning from a function while inside one or more nested loops?

Question

Is there a way to immediately return from a function when in one or more nested loops?

Here's some sample code illustrating the problem:

; Grid data structure
; -------------------
(defstruct grid :width :height)

(defn create-grid [w h initial-value]
  (struct-map grid
    :width  w
    :height h
    :data   (ref (vec (repeat (* w h) initial-value)))))

(defn create-grid-with-data [w h gdata]
  (struct-map grid
    :width w
    :height h
    :data (ref gdata)))

(defn get-grid [g x y]
  (let [gdata (g :data)
        idx   (+ x (* (g :width) y)) ]
    (gdata idx)))

(defn set-grid [g x y value]
  (let [data  (deref (g :data))
        idx   (+ x (* (g :width) y)) ]
    (dosync (alter (g :data) (fn [_] (assoc data idx value))))))

(defn get-grid-rows [g]
  (partition (g :width) (deref (g :data))))



; Beginning of test app
; ---------------------

; The Tetris playing field  
(def current-field (create-grid 20 10 0))


; A tetris block (the L-Shape)
(def current-block {
  :grid (struct-map grid :width 3 :height 3 :data [ 0 1 0
                                                    0 1 0
                                                    0 1 1 ])

  ; upper-left corner of the block position in the playing field
  :x (ref 0) 
  :y (ref 0)
} )


; check-position-valid checks if the current position
; of a block is a valid position in a playing field
(defn check-position-valid [field block]
  (dotimes [ x ((block :grid) :width) ]
    (dotimes [ y ((block :grid) :height) ]
      (if
        (let [ g           (block :grid)
               block-value (get-grid g x y)
               field-x     (+ x (deref (block :x)))
               field-y     (+ y (deref (block :y))) ]
          (if (not (zero? block-value))
            (if-not
              (and (>= field-x 0)
                   (< field-x (field :width))
                   (< field-y (field :height))
                   (zero? (get-grid field field-x field-y)))
              false ; invalid position, function should now return false
              true ; ok, continue loop
              )))
        true
        false))))

(println (check-position-valid current-field current-block))

Perhaps I'm approaching the problem too much in an imperative way.

Update
Ok, I found a solution:

; check-position-valid checks if the current position
; of a block is a valid position in a playing field
(defn check-position-valid [field block]
  (let [stop-condition (ref false)]
    (loop [ x 0 ]
      (when (and (not (deref stop-condition))
                 (< x ((block :grid) :width)))
        (println "x" x)
        (loop [ y 0 ]
          (when (and (not (deref stop-condition))
                     (< y ((block :grid) :height)))
            (println "y" y)
            (let [ g           (block :grid)
                   block-value (get-grid g x y)
                   field-x     (+ x (deref (block :x)))
                   field-y     (+ y (deref (block :y))) ]
              (if (not (zero? block-value))
                (if-not
                  (and (>= field-x 0)
                       (< field-x (field :width))
                       (< field-y (field :height))
                       (zero? (get-grid field field-x field-y)))
                  (do
                    (println "stop is true")
                    (dosync (alter stop-condition (fn [_] true)))))))
            (recur (inc y))))
        (recur (inc x))))
    (not (deref stop-condition))))

(println (check-position-valid current-field current-block))

It uses a mutable reference as a stop flag, breaking the functional style of programming. But I'm happy to have a solution. Feel free to share a better way.

Update
For those interested, I've finished a first version version of my Clojure Tetris game. Feel free to give it a try :)

Answer 1

Untested:

(defn position-valid? [field block]
  (let [g (block :grid)]
    (every? true? (for [x (range 0 (inc (g :width)))
                        y (range 0 (inc (g :height)))
                        :let [block-value (get-grid g x y)
                              field-x     (+ x @(block :x))
                              field-y     (+ y @(block :y))]]
                    (and (not (zero? block-value))
                         (>= field-x 0)
                         (< field-x (field :width))
                         (< field-y (field :height))
                         (zero? (get-grid field field-x field-y)))))))

for is lazy, so every? will only go until it reaches the first non-true value.

Answer 2

In a loop-recur structure, you do some sort of check to see if you need to keep looping, and recur if you do, or return a value if you don't. In a while loop, you'd just make the predicate equal false. There is no break and continue in Clojure, because it doesn't make sense in Clojure.

I think you're looking for loop, and not dotimes.

Answer 3

Since in another question by the OP I proposed a different data structure for the playing grid -- namely a vector of vectors -- I'm tempted to show how I'd go about solving this problem with that representation. For the purposes of this problem, it seems easiest to me to use 0 and 1 to represent grid cell states. Adapting the code for the case of a more complex grid cell structure (possibly a map holding the number or a Boolean somewhere inside) would present no problem.

This is the function being discussed:

(defn check-position-valid [field-grid block]
  (let [grid-rect (subgrid field-grid
                           @(block :x)
                           (-> block :grid :width)
                           @(block :y)
                           (-> block :grid :height))
        block-rect (-> block :grid :data)]
    (and grid-rect
         (not-any? pos?
                   (mapcat #(map (comp dec +) %1 %2)
                           grid-rect
                           block-rect)))))

I removed the grid struct map; instead, all grids are simple vectors of vectors. Note that holding explicit :width and :height keys may not necessarily be much help performance-wise, as Clojure vectors keep a count of their members (as do many other Clojure collections). There's no particular reason not to have them, though, I just found it simpler to do without. This affects my terminology below: the word 'grid' always refers to a vector of vectors.

The following creates the grid on which the other functions operate; also enjoy the bonus printout function:

(defn create-grid
  ([w h] (create-grid w h 0))
  ([w h initial-value]
     (let [data (vec (map vec (repeat h (repeat w initial-value))))]
       data)))

(defn print-grid [g]
  (doseq [row g]
    (apply println row)))

The key to the above version of check-position-valid is this function, which gives as a subgrid of the given grid:

(defn subgrid
  "x & y are top left coords, x+ & y+ are spans"
  [g x x+ y y+]
  (if (and (<= (+ x x+) (count g))
           (<= (+ y y+) (count (first g))))
    (vec
     (map #(subvec % x (+ x x+))
          (subvec g y (+ y y+))))))

subvec is advertised by its docstring as an O(1) (constant time) operation which is very fast, so this should be pretty fast too. In the above, it's used to extract a window into the given grid, which is itself a grid (and can be printed with print-grid). check-position-valid takes such a window into the grid and examines it side-by-side with the block's grid to determine whether the block is in a valid position.

It is assumed that completely nonsensical argument values (negative x, x+, y, y+) will not occur, however in case the window would "stick out" of the grid on the right or at the bottom, nil is returned instead of subvec's index out of bounds exception.

Finally, a definition of current-block usable with the above:

(def current-block
     {:grid [[0 1 0]
             [0 1 0]
             [0 1 1]])
      :x (ref 0) 
      :y (ref 0)})

And some utility functions (which all return grids):

(defn get-grid [g x y]
  (get-in g [y x]))

(defn set-grid [g x y v]
  (assoc-in g [y x] v))

(defn swap-grid [g x y f & args]
  (apply update-in g [y x] f args))

(defn get-grid-row [g y]
  (get g y))

(defn set-grid-row [g y v]
  (assoc g y (vec (repeat (count (g 0)) v))))

(defn get-grid-col [g x]
  (vec (map #(% x) g)))

(defn set-grid-col [g x v]
  (vec (map #(assoc-in % [x] v) g)))

The latter four can be used to build up a test grid quickly like so (the 2s and 3s make no sense in connection with the code above as it is presently written, but they serve to illustrate what happens):

user> (print-grid (set-grid-row (set-grid-col (create-grid 6 10) 1 2) 0 3))
3 3 3 3 3 3
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
0 2 0 0 0 0
nil

Answer 4

You're on the right track by replacing the dotimes with loop/recur. Now, to get rid of that mutable stop flag:

1. Add a second variable to represent the stop flag to your loops, like

   (loop [x 0 stop false] ...
   

2. Do an if/then to see if the stop flag is true as the first operation within the loops.

   (if stop (println "I'm all done) (...
   

3. Deep in your nested code where you have the if-not test, have both branches call recur with the appropriate value set for false. To paraphrase:

   (if (stop-condition-is-true) (recur y true) (recur (inc y) false))