title: Triangularizing a list in Haskell
body: <p>I'm interested in writing an efficient Haskell function <code>triangularize :: [a] -&gt; [[a]]</code> that takes a (perhaps infinite) list and "triangularizes" it into a list of lists. For example, <code>triangularize [1..19]</code> should return</p>
  
  <pre><code>[[1,  3,  6,  10, 15]
  ,[2,  5,  9,  14]
  ,[4,  8,  13, 19]
  ,[7,  12, 18]
  ,[11, 17]
  ,[16]]
  </code></pre>
  
  <p>By efficient, I mean that I want it to run in <code>O(n)</code> time where <code>n</code> is the length of the list.</p>
  
  <hr>
  
  <p>Note that this is quite easy to do in a language like Python, because appending to the end of a list (array) is a constant time operation. A very imperative Python function which accomplishes this is:</p>
  
  <pre><code>def triangularize(elements):
      row_index = 0
      column_index = 0
      diagonal_array = []
      for a in elements:
          if row_index == len(diagonal_array):
              diagonal_array.append([a])
          else:
              diagonal_array[row_index].append(a)
          if row_index == 0:
              (row_index, column_index) = (column_index + 1, 0)
          else:
              row_index -= 1
              column_index += 1
      return diagonal_array
  </code></pre>
  
  <hr>
  
  <p>This came up because I have been using Haskell to write some "tabl" sequences in the <a href="https://oeis.org/" rel="noreferrer">On-Line Encyclopedia of Integer Sequences</a> (OEIS), and I want to be able to transform an ordinary (1-dimensional) sequence into a (2-dimensional) sequence of sequences in exactly this way.</p>
  
  <p>Perhaps there's some clever (or not-so-clever) way to <code>foldr</code> over the input list, but I haven't been able to sort it out.</p>