Print numbers from 1 to 100 without using any numbers in the code

Hundred.hs

{-# LANGUAGE NoImplicitPrelude #-}

{-
 Problem statment: "Is it possible to print numbers from 1 to 100
 without using any numbers in the code? If yes, how?"

 Source:
 https://www.quora.com/Is-it-possible-to-print-numbers-from-1-to-100-without-using-any-numbers-in-the-code-If-yes-how

 For generality, this solution can print any ranges of natural numbers
 in any base from 2 to 36 using characters '0-9' and 'A-Z' to
 represents digits.

 The problem parameters: output base, and range are hardcoded as
 binary constants using data types defined below.
-}

module Main where

import           Prelude (Char, Eq, IO, String, map, mapM_, putStrLn, reverse,
                          succ, ($), (==))

{-
First, we define a number system to represent natural numbers without
using Haskell numeric types and use it to encode constants without use
of decimal ASCII number literals.

We could have used classic natural number encoding with with Zero and
Succ constructors, but we to be able to represent large constants like
more tersly, we opted for a binary encoding instead.

Our insipration:
https://coq.inria.fr/distrib/current/stdlib/Coq.Numbers.BinNums.html

Positive is a datatype representing the strictly positive integers in
a binary way. Starting from 1 (represented by XH), one can add a new
least significant digit via XO (digit 0) or XI (digit 1).
-}
data Positive = XI Positive | XO Positive | XH
  deriving (Eq)

-- successor function for positive numbers
psucc:: Positive -> Positive
psucc (XI p) = XO (psucc p)
psucc (XO p) = XI p
psucc  XH    = XO XH

-- Natural numbers: zero or strictly positive
data N = NZ | NP Positive
  deriving (Eq)

-- For convinience, define 1 constant for N
n_one::N
n_one = NP XH

-- successor function for natural numbers
nsucc :: N -> N
nsucc NZ     = n_one
nsucc (NP p) = NP (psucc p)

{-
Next, we define a type for numbers in arbitrary base.  We parametrise
it by 'base', which is for convenience stored as `maxdigit=base-1`

In dependenty typed language like Gallina, `BaseN` would be
dependently typed with base as a parameter. Unfortunately could not do
this in Haskell. Some possible workarounds include using ReaderMonad
or typeclasses
(e.g. https://okmij.org/ftp/Haskell/number-parameterized-types.html)
For simplicity, here we just define `maxdigit` global constant and
assume that `BaseN` type always represents numbers in `maxdigit+1`
base.
-}

-- max digit value (same as base-1)
maxdigit::N
maxdigit = NP (XI (XO (XO XH))) -- 9 for decimal
--maxdigit = NP (XI (XI (XI XH)))  -- 15 for hex
--maxdigit = n_one -- 1 for binary

{-
`BaseN` number type is just a non-empty list of digits (least
significant first). Again, in dependently typed languages like Gallina
there are more elgant ways to represent these, but in Haskell we opt
for a simple solution. (see also
https://okmij.org/ftp/Haskell/dependent-types.html#non-empty-list)
-}
data BaseN = BaseN N [N]

-- Add a least significant digit a digit to BaseN number
basen_append_digit:: N -> BaseN -> BaseN
basen_append_digit h (BaseN x xs) = BaseN h (x:xs)

-- successor for BaseN
bsucc:: BaseN -> BaseN
bsucc (BaseN x xs) =
  if x == maxdigit
  then
    (case xs of
        []     -> BaseN NZ [n_one]
        (b:bs) -> basen_append_digit NZ (bsucc$BaseN b bs))
  else BaseN (nsucc x) xs

-- For convinience, define 0 constant for BaseN
bzero::BaseN
bzero = BaseN NZ []

-- For convinience, define 1 constant for BaseN
bone::BaseN
bone = BaseN n_one []

{-
Converting N (binary) number to BaseN (arbitrary base)
1. Obviously this implementation is quite inefficient.
2. We avoid defining predecessor functoins for N and BaseN
   types and rely only on sucessor functions.
-}
basen_of_n:: N -> BaseN
basen_of_n NZ = bzero
basen_of_n (NP p) =
  loop XH bone
  where
    loop p' b =
      if p' == p
      then b
      else loop (psucc p') (bsucc b)

{-
A hacky way to produce '0' without mentioning it ascii
representation there may be other smart ways to disguise it
-}
binitial::Char
binitial = succ '/'

{-
Convert single digit from N to Character we use '0'-'9' to encode up
to base 10. For bases above that we proceed with characters starting
from 'A' which allows to represent hex numbers in a conventional way.
-}
char_of_N :: N -> Char
char_of_N NZ = binitial
char_of_N (NP p) =
  loop XH binitial
  where
    n_ten = XO (XI (XO XH)) -- 10
    loop p' c =
      if p' == psucc p
      then c
      else loop (psucc p')
           (if p' == n_ten then 'A' else (succ c))

-- Converts `BaseN` to a String
string_of_basen:: BaseN -> String
string_of_basen (BaseN x xs) =
  map char_of_N $ reverse (x:xs)

-- Generates sequence of numbers of type N in range [n;to)
n_range:: N -> N -> [N]
n_range n to =
  if n == to
  then []
  else n:(n_range (nsucc n) to)

main :: IO ()
main =
  let
    -- Natural number constant for for 100
    n_one_hundred  = NP (XO (XO (XI (XO (XO (XI XH))))))
    ns = n_range n_one (nsucc n_one_hundred)
    bs = map basen_of_n ns
    ss = map string_of_basen bs
  in
    mapM_ putStrLn ss