title: How to implement Binary numbers in Haskell
body: <p>I have seen the following data constructor for Church numerals </p>
  
  <pre><code>data Nat = Zero | Succ Nat deriving Show
  </code></pre>
  
  <p>But this is unary numbers.
  How do we implement a data constructor for Binary numbers in Haskell in this way?</p>
  
  <p>I have tried this:</p>
  
  <pre><code>data Bin = Zero | One | BinC [Bin] deriving Show
  </code></pre>
  
  <p>After this we can get, decimal 5 encoded as <code>BinC [One,Zero,One]</code></p>
  
  <p>But I think I am missing something here. My solution seems not as clever as the Church's solution. No surprise, I am not Church. Little bit of thinking, I found that my solution depends upon list, whereas the Nat doesn't depend upon any such external structure like list. </p>
  
  <p>Can we write a solution that is similar to Church's using a Succ type constructor for Binary numbers too? If yes, how? I tried a lot, but it seems my brain cannot get rid of the need of list or some other such structure.</p>