title: Functional Programming à la 1940s: Minimalistic Implementation of Factorial
body: <p>I have watched the amazing talk by John Hughes titled <a href="https://youtu.be/XrNdvWqxBvA" rel="nofollow noreferrer">Why Functional Programming Matters</a> a couple of times and only recently decided to actually try implementing the "minimalist" version of booleans, integers, and of course factorial, as shown in the <a href="https://youtu.be/XrNdvWqxBvA?t=1m28s" rel="nofollow noreferrer">video</a>. </p>
  
  <p>I implemented <code>true</code>, <code>false</code>, <code>ifte</code>, <code>zero</code>, <code>one</code>, <code>two</code>, <code>iszero</code>, <code>decr</code> and finally <code>fact</code> <a href="https://repl.it/Nm3P/7" rel="nofollow noreferrer">here</a> as follow:</p>
  
  <pre><code>-- boolean
  true x y = x
  false x y = y
  ifte bool t e = bool t e
  
  -- positive integers
  three f x = f $ f $ f x
  two f x = f $ f x
  one f x = f x
  zero f x = x 
  
  -- add and multiplication
  add m n f x = m f $ n f x
  mul m n f x = m (n f) x 
  
  -- is zero check
  iszero n =  n (\_ -&gt; false) true
  
  -- decrement
  decr n = 
    n (\m f x -&gt; f (m f zero))
      zero
      (\x-&gt;x)
      zero
  
  
  -- factorial
  fact n =
    ifte (iszero n)
      one
      (mul n (fact (decr n)))
  </code></pre>
  
  <h2>Problem</h2>
  
  <p>I tested every function, and they all compile and work perfectly, except for <code>decr</code> and <code>fact</code>. </p>
  
  <p>Even though John Hughes promises at <a href="https://youtu.be/XrNdvWqxBvA?t=6m37s" rel="nofollow noreferrer">6:37</a> that his implementation of <code>decr</code> works, it fails to compile with the following error:</p>
  
  <blockquote>
    <p>error: Variable not in scope: incr</p>
  </blockquote>
  
  <p>I am not certain how <code>incr</code> should be implemented in <code>(\m f x -&gt; f (m incr zero))</code>. </p>
  
  <p>Now if I define them as <code>incr = (+1)</code> and change the definition of <code>decr</code> to the following, then <code>decr</code> compiles and works fine, but <code>fact</code> still causes compilation failure. </p>
  
  <pre><code>decr n = 
    n (\m f x -&gt; f (m incr x))
      zero
      (\x-&gt;x)
      zero'
  </code></pre>
  
  <p>Is there a bug in the lambda <code>(\m f x -&gt; f (m incr zero))</code> used in the definition of <code>decr</code>, or should <code>incr</code> be defined differently? </p>
  
  <h2>Update</h2>
  
  <p>When I define <code>incr</code> as <code>incr n = (\f x -&gt; f (n f x))</code>, <code>decr n</code> works fine, but <code>fact n</code> fails to compile. Here's the readable portion of the error message:</p>
  
  <blockquote>
    <p>factorial.hs:30:1: error:
        • Occurs check: cannot construct the infinite type:</p>
    
    <p>...</p>
    
    <p>| fact n =<br>
       | ^^^^^^^^...</p>
    
    <p>...</p>
    
    <p>factorial.hs:33:6: error:
        • Occurs check: cannot construct the infinite type:</p>
    
    <p>...</p>
  
  <pre><code>• In the third argument of ‘ifte’, namely ‘(mul n (fact (decr n)))’
    In the expression: ifte (iszero n) one (mul n (fact (decr n)))
    In an equation for ‘fact’:
        fact n = ifte (iszero n) one (mul n (fact (decr n)))
  </code></pre>
    
    <p>...</p>
    
    <p>|     (mul n (fact (decr n)))<br>
       |      ^^^^^^^^^^^^^^^^^^^^^</p>
  </blockquote>
  
  <p>Note: the complete error message is several pages long.</p>