To what extent can we modify a function template when defining a function?

Question

This is a theoretical question regarding templates as taught in htdp. I just solved an exercise (ex.176) where the data definitions and main function are given:

; A Matrix is one of: 
;  – (cons Row '())
;  – (cons Row Matrix)
; constraint all rows in matrix are of the same length

; A Row is one of: 
;  – '()
;  – (cons Number Row)

; Matrix -> Matrix
; transposes the given matrix along the diagonal 
(define (transpose lln)
  (cond
    [(empty? (first lln)) '()]
    [else (cons (first* lln) (transpose (rest* lln)))]))

and the auxiliary ones first* and rest* are to be defined. It's mentioned that the design for transpose is not possible with the so far seen material, which is ok. But in defining the auxiliary functions (one of which you can see below), there is a bit of confusion.

; Matrix -> List-of-numbers
; produces the first column as a list of numbers

(define (first* m)
  (cond
    [(empty? m) '()]
    [else
     (cons (first (first m))
           (first* (rest m)))]))

Normally, a function definition uses the outline of a template and a template is the outline based on the data definitions in the design process. While not all elements of the outline have to be used, depending on what is needed for the definition, the base case in first* (and rest*) - (empty? m) had me confused for a while.

Having assumed that the base case (empty? merely mirrors the data definition, and given that the definition for the first case of Matrix says (cons Row '()), I went on with (empty? (rest m)), because that's the most basic form of Matrix - it can't be empty itself, only its second part. From the tests, it became obvious the answer was wrong, but I was still clueless for a while, until I reasoned that through recursion, regardless of the data definition, the input m had to become empty at some point for the desired output, as a result of using (rest m). Turns out, just ignoring the definition worked.

So my question is: how do we know to ignore/ change certain parts of the template, especially when they're based on the definitions which are at the core of this design process? How much leeway do we have to modify the outline?

(Also asking whether there is something about the problem or the idea of templates that I've possibly missed, which could help enhance understanding. I reached a solution to the exercise, but besides that little reasoning, it was mainly by trial and error.)