0

so i was asked to write a function diag :: [[a]] -> [a] in haskell for my weekly assignment which returns all diagonals of a well-formed matrix like:

matrix

Resulting in the list: [a11,a12,a21,a13,a22,a31,a14,a23,a32,a24,a33,a34].

Since we're not allowed to use any third-party packages like Data.matrix and me not beeing able to completly understand the implementation in this post i would appreciate your help with this one.

EDIT:

I understood this one, but it only returns one diagonal in the wrong order. I also understood the math, but it didn't really help me either.

Community
  • 1
  • 1
GabbaGandalf
  • 119
  • 7
  • If the rows are `(x:xs)`, how is `diagonals (x:xs)` related to `diagonals xs`? – ErikR May 29 '16 at 16:39
  • I'd be happy to explain more about my implementation in the linked answer if you say which parts you did/didn't understand. – Daniel Wagner May 29 '16 at 17:12
  • @DanielWagner This part confused me: `go b es_ = [h | h:_ <- b] : case es_ of [] -> transpose ts e:es -> go (e:ts) es where ts = [t | _:t <- b]`. I'm new to FP and i know there is a function called go, with arguments `b` and `es_`. But what exactly does `case` and this "pattern matching" (thats what it looks like to me). – GabbaGandalf May 29 '16 at 17:52
  • @ErikR I'm not quite sure what you're intending to point at.. – GabbaGandalf May 29 '16 at 17:55
  • @GabbaGandalf `case es_ of [] -> branch1; e:es -> branch2` checks whether `es_` is an empty list, in which case its value is `branch1`, or whether it is nonempty, in which case it names the first element `e`, the rest of the list `es`, and then becomes the value `branch2`. Think "base case" vs. "recursive case" if you're familiar with thinking in those terms about recursive functions. In this particular `case`, `es_` is keeping track of which rows we have not started walking through in our traversal, so it will take the first branch until it reaches the longest diagonal. – Daniel Wagner May 29 '16 at 21:04

1 Answers1

1

Notice what happens when you pad each row so that the left pointing arrows point straight down:

a11 a12 a13 a14
    a21 a22 a23 a24
        a31 a32 a33 a_34

You would get your required result if you could just "stack" the columns on each other somehow. But we can't stack the columns, unfortunately. Of course, if we transpose the matrix, then the columns will be the rows, and they can be joined together with concat, and this would have the same effect as stacking columns. But we need to preserve the padding when we do the transpose.

Here's an idea. What if we wrap all the values in Just and insert Nothing in the padded spots?

(Just a11) (Just a12) (Just a13) (Just a14) Nothing    Nothing
Nothing    (Just a21) (Just a22) (Just a23) (Just a24) Nothing
Nothing    Nothing    (Just a31) (Just a32) (Just a33) (Just a34)

Now when we transpose, the shifts will be preserved. It just remains to remove all the Nothings, concat the rows into a single list, and unwrap each Just.

Of course, with this being homework, you'll have to write the code yourself. But I hope this at least gives you a good idea of how you might approach the problem.

user2297560
  • 2,953
  • 1
  • 14
  • 11