title: Idiomatic efficient Haskell append?
body: <p>List and the cons operator <code>(:)</code> are very common in Haskell. Cons is our friend. But sometimes I want to add to the end of a list instead.</p>
  
  <pre><code>xs `append` x = xs ++ [x]
  </code></pre>
  
  <p>This, sadly, is <em>not</em> an efficient way to implement it.</p>
  
  <p>I wrote up <a href="http://en.wikipedia.org/wiki/Pascal&#39;s_triangle" rel="noreferrer">Pascal's triangle</a> in Haskell, but I had to use the <code>++ [x]</code> anti-idiom:</p>
  
  <pre><code>ptri = [1] : mkptri ptri
  mkptri (row:rows) = newRow : mkptri rows
      where newRow = zipWith (+) row (0:row) ++ [1]
  </code></pre>
  
  <p>imho, this is a lovely readable Pascal's triangle and all, but the anti-idiom irks me. Can someone explain to me (and, ideally, point me to a good tutorial) on what the idiomatic data structure is for cases where you want to append to the end efficiently? I'm hoping for near-list-like beauty in this data structure and its methods. Or, alternately, explain to me why this anti-idiom is actually not that bad for this case (if you believe such to be the case).</p>
  
  <hr>
  
  <p>[edit] The answer I like the best is <code>Data.Sequence</code>, which does indeed have "near-list-like beauty." Not sure how I feel about the required strictness of operations. Further suggestions and different ideas are always welcome.</p>
  
  <pre><code>import Data.Sequence ((|&gt;), (&lt;|), zipWith, singleton)
  import Prelude hiding (zipWith)
  
  ptri = singleton 1 : mkptri ptri
  
  mkptri (seq:seqs) = newRow : mkptri seqs
      where newRow = zipWith (+) seq (0 &lt;| seq) |&gt; 1
  </code></pre>
  
  <p>Now we just need List to be a class, so that other structures can use its methods like <code>zipWith</code> without hiding it from Prelude, or qualifying it. :P</p>