title: Implement reverse in Haskell that runs in linear time
body: <p>I'm just learning Haskell, so sorry if my question is stupid. I'm reading learnyouahaskell.com and now I'm at chapter 5 "Recursion". There's an example of implementation of standard 'reverse' function:</p>
  
  <pre><code>reverse' :: [a] -&gt; [a]  
  reverse' [] = []  
  reverse' (x:xs) = reverse' xs ++ [x]  
  </code></pre>
  
  <p>But it seems that it runs in O(N^2) time, while the standard reverse runs in O(N) (I hope so). The following code illustrates this:</p>
  
  <pre><code>sum (reverse [1,2..1000000]) -- runs pretty fast
  sum (reverse' [1,2..1000000]) -- never finishes
  </code></pre>
  
  <p>So, I started thinking how to implement my own reverse faster. It's pretty easy to do in imperative languages. Maybe I need some more advanced material from subsequent chapters to do this? Any hints are welcomed.</p>