title: How to "iterate" over a function whose type changes among iteration but the formal definition is the same
body: <p>I have just started learning Haskell and I come across the following problem. I try to "iterate" the function <code>\x-&gt;[x]</code>. I expect to get the result <code>[[8]]</code> by</p>
  
  <pre><code>foldr1 (.) (replicate 2 (\x-&gt;[x])) $ (8 :: Int)
  </code></pre>
  
  <p>This does not work, and gives the following error message:</p>
  
  <blockquote>
    <p>Occurs check: cannot construct the infinite type: <code>a ~ [a]</code></p>
    
    <p>Expected type: <code>[a -&gt; a]</code></p>
    
    <p>Actual type: <code>[a -&gt; [a]]</code></p>
  </blockquote>
  
  <p>I can understand why it doesn't work. It is because that <code>foldr1</code> has type signature <code>foldr1 :: Foldable t =&gt; (a -&gt; a -&gt; a) -&gt; a -&gt; t a -&gt; a</code>, and takes <code>a -&gt; a -&gt; a</code> as the type signature of its first parameter, not <code>a -&gt; a -&gt; b</code></p>
  
  <p>Neither does this, for the same reason:</p>
  
  <pre><code>((!! 2) $ iterate (\x-&gt;[x]) .) id) (8 :: Int)
  </code></pre>
  
  <p>However, this works:</p>
  
  <pre><code>(\x-&gt;[x]) $ (\x-&gt;[x]) $ (8 :: Int)
  </code></pre>
  
  <p>and I understand that the first <code>(\x-&gt;[x])</code> and the second one are of different type (namely <code>[Int]-&gt;[[Int]]</code> and <code>Int-&gt;[Int]</code>), although formally they look the same.</p>
  
  <p>Now say that I need to change the 2 to a large number, say 100. </p>
  
  <p><strong>My question is</strong>, is there a way to construct such a list? Do I have to resort to meta-programming techniques such as Template Haskell? If I have to resort to meta-programming, how can I do it?</p>
  
  <p>As a side node, I have also tried to construct the string representation of such a list and <code>read</code> it. Although the string is much easier to construct, I don't know how to <code>read</code> such a string. For example,</p>
  
  <pre><code>read "[[[[[8]]]]]" :: ??
  </code></pre>
  
  <p>I don't know how to construct the <code>??</code> part when the number of nested layers is not known <em>a priori</em>. The only way I can think of is resorting to meta-programming.</p>
  
  <p>The question above may not seem interesting enough, and I have a "real-life" case. Consider the following function:</p>
  
  <pre><code>natSucc x = [Left x,Right [x]]
  </code></pre>
  
  <p>This is the <code>succ</code> function used in the <a href="https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers" rel="nofollow noreferrer">formal definition of natural numbers</a>. Again, I cannot simply <code>foldr1-replicate</code> or <code>!!-iterate</code> it.</p>
  
  <p>Any help will be appreciated. Suggestions on code styles are also welcome.</p>
  
  <p><strong>Edit</strong>:
  After viewing the 3 answers given so far (again, thank you all very much for your time and efforts) I realized this is a more general problem that is not limited to lists. A similar type of problem can be composed for each valid type of functor (what if I want to get <code>Just Just Just 8</code>, although that may not make much sense on its own?).</p>