tA
/
Collatz
1
0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
Collatz in Type Level
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
28KB
Branch: master
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'master'
${ noResults }
Collatz/README.md

README.md 847B
Raw Permalink Normal View History

first commit
4 years ago
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
​
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 
  1. # Collatz Conjecture

  2. 

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

  4. 

  5. ## Running

  6. 

  7. in `ghci` load the file:

  8. 

  9. ```

  10. :load collatz.hs

  11. ```

  12. 

  13. and run with the following:

  14. 

  15. ```

  16. :t solution (nil :: X)

  17. ```

  18. 

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

  20. 

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

  22. 

  23. ## Example

  24. 

  25. ```

  26. *Main> :t solution (nil :: (S (S (S Z))))

  27. solution (nil :: (S (S (S Z))))

  28.   :: Cons

  29.        (S (S (S Z)))

  30.      (Cons

  31.        (S (S (S (S (S (S (S (S (S (S Z))))))))))

  32.      (Cons

  33.        (S (S (S (S (S Z)))))

  34.      (Cons

  35.        (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S (S Z))))))))))))))))

  36.      (Cons

  37.        (S (S (S (S (S (S (S (S Z))))))))

  38.      (Cons

  39.        (S (S (S (S Z))))

  40.      (Cons

  41.        (S (S Z))

  42.      (Cons

  43.        (S Z)

  44.      Nil)))))))

  45. ```

  46. 

  47. which translates to the following list:

  48. 

  49. ```

  50. [ 3 10 5 16 8 4 2 1 ]

  51. ```