Collatz/README.md

# Collatz Conjecture

Collatz Conjecture (Snowflake / `3n+1`) done in the GHC Type System.

## Running

in `ghci` load the file:

```
:load collatz.hs
```

and run with the following:

```
:t solution (nil :: X)
```

where `X` is the church encoding using `S n` and `Z`, ie

`(S (S (S Z)))` is the number `3`

## Example

```
*Main> :t solution (nil :: (S (S (S Z))))
solution (nil :: (S (S (S Z))))
  :: Cons
       (S (S (S Z)))
     (Cons
       (S (S (S (S (S (S (S (S (S (S Z))))))))))
     (Cons
       (S (S (S (S (S Z)))))
     (Cons
       (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S Z))))))))))))))))
     (Cons
       (S (S (S (S (S (S (S (S Z))))))))
     (Cons
       (S (S (S (S Z))))
     (Cons
       (S (S Z))
     (Cons
       (S Z)
     Nil)))))))
```

which translates to the following list:

```
[ 3 10 5 16 8 4 2 1 ]
```