Oz: Translating Python into Oz

I've been working my way through Concepts, Techniques, and Models of Computer Programming. In chapter 3, one of the exercises was to transpose a matrix.

I immediately felt completely overwhelmed. I couldn't even remember what it meant to transpose a matrix, and I definitely hadn't seen anything matrix-related in the book. I went to Wikipedia and figured out that transposing a matrix just means swapping the rows and the columns. That seemed more possible, but I still didn't think I had the necessary tools to code it in Oz yet.

I decided to try solving the problem in Python. Python is sometimes called "executable pseudocode", and sure enough, the solution came to me pretty easily:

m = [[1, 2, 3],
     [4, 5, 6]]

def transpose(m):
    transposed = []
    if len(m) >= 1:
        len_cols = len(m[0])
        for col in xrange(len_cols):
            transposed_row = []
            for row in m:
                transposed_row.append(row[col])
            transposed.append(transposed_row)
    return transposed

print transpose(m)

Now, in real life, I might refactor that into the following:

m = [[1, 2, 3],
     [4, 5, 6]]

def transpose(m):
    if not m:
        return []
    return [[row[col] for row in m]
            for col in xrange(len(m[0]))]

print transpose(m)

However, the goal was to write the solution in Oz, not Python. Hence, I started refactoring the code into something I could translate to Oz. Oz uses Lisp-like lists, not arrays, and at least for the chapter I'm in, it uses recursion, not foreach loops. Hence I ended up with:

m = [[1, 2, 3],
     [4, 5, 6]]

def transpose(m):

    def transpose_row(m, i, transposed_row):
        if not m:
            transposed_row.reverse()
            return transposed_row
        car, cdr = m[0], m[1:]
        transposed_row.insert(0, car[i])
        return transpose_row(cdr, i, transposed_row)

    def iter_row_len(i, transposed):
        if i == row_len:
            transposed.reverse()
            return transposed
        transposed.insert(0, transpose_row(m, i, []))
        return iter_row_len(i + 1, transposed)

    if not m:
        return m
    row_len = len(m[0])
    transposed = iter_row_len(0, [])
    return transposed

print transpose(m)

At this point, it was fairly straightforward to translate that into Oz:

declare M
M = [[1 2 3]
     [4 5 6]]

declare
fun {Transpose M}
   fun {TransposeRow M I TransposedRow}
      case M
      of nil then
  {Reverse TransposedRow}
      [] M1|Mr then
  {TransposeRow Mr I {List.nth M1 I}|TransposedRow}
      end
   end
   fun {IterRowLen I Transposed}
      if I==RowLen+1 then
  {Reverse Transposed}
      else
  {IterRowLen I+1 {TransposeRow M I nil}|Transposed}
      end
   end
   RowLen
in
   case M
   of nil then nil
   [] M1|Mr then
      RowLen={Length M1}
      {IterRowLen 1 nil}
   end
end

{Browse {Transpose M}}  % Prints [[1 4] [2 5] [3 6]]

Viola! Problem solved!

That solution is pretty long, which just goes to show how bad an Oz programmer I am. I found someone else's solution online:

fun {Transpose Matrix}
   {List.foldR Matrix
    fun {$ R1 R2} {List.zip R1 R2 fun {$ E1 E2} E1|E2 end} end
    for E in Matrix.1 collect:C do {C nil} end}
end

Obviously, he knows Oz and functional programming in general a heck of a lot better than I do.

The moral of the story is that Python can indeed serve as executable pseudocode, but it won't help me to think like an Oz programmer.