Lab 8

Implement a set of two-dimensional array operations using a monadic style.

Here are some data definitions:

; the store!
(define-type-alias Location number)
(define-type-alias Store (hashof Location Value))

; the empty store
(define empty-store (hash empty))

; represents a runtime value
(define-type Value
  [numV (n : number)]
  [boolV (b : boolean)]
  [arrayV (l : Location)
          (size : number)])

;
;
; OH NO! THE STORE MONAD!
;
;

; uh oh, here comes the store monad...

; lift a value to a computation
(define (lift v)
  (lambda ([s : Store]) (values v s)))

; bind an 'a computation to an 'a -> 'b computation
(define (bind a b)
  (lambda ([s : Store])
    (local [(define-values (ar s2) (a s))]
      ((b ar) s2))))

; fetch a value from the store
(define (store-lookup loc)
  (lambda ([sto : Store])
    (type-case (optionof Value) (hash-ref sto loc)
      [some (v) (values v sto)]
      [none () (internal-missing-location-error loc)]))) ; HERE

; insert a value into the store
(define (store-set! loc new-val)
  (lambda ([s : Store])
    (values #f (hash-set s loc new-val))))

; return the first free store location
(define store-next-loc
  (lambda (sto)
    (values (add1 (foldl max -1 (hash-keys sto)))
            sto)))

; run a computation
(define (run computation store)
  (computation store))

; run a computation, return the value
(define (run/val computation store)
  (local [(define-values (v s) (run computation store))]
    v))

; the 'do' syntax that makes it all palatable
(define-syntax (do stx)
  (syntax-case stx (<-)
    [(_ [dc <- rhs]) #'rhs]
    [(_ rhs) #'rhs]
    [(_ [name <- rhs] clause ...)
     #'(bind rhs (lambda (name) (do clause ...)))]
    [(_ rhs clause ...)
     #'(bind rhs (lambda (unused) (do clause ...)))]))

; a location has vanished!
(define (internal-missing-location-error loc)
  (error 'interp
         (strings (list "internal error, missing location: " (to-string loc)))))

; strings : append a list of strings
(define (strings l) (foldr string-append "" l))

Implement the create-2d-array function, that accepts a number of columns, a number of rows, and an initial value, and returns a arrayV computation, creating an array that contains the given number of rows, each of which is an array containing the given number of vectors. Note that each of these row arrays must be a separate array; it should not be the case that mutating one of them mutates all of them.
Implement the 2d-array-ref function, that accepts a 2d-array, a column, and a row, and returns a Value computation representing the value in that cell.
Implement the 2d-array-set! function, that accepts a 2d-array, a column, a vector, and a new value, and updates the cell at the given column and vector within the 2d array to contain the new value.
Implement the 2d-array-transpose function, that accepts a 2d-array, and returns a new transposed version of that array.

Don’t use any form of mutation—mutable hash tables, boxes, etc.—for this lab.