tA
/
Collatz
1
0
Fork 0
Koodi Ongelmat 0 Pull-pyynnöt 0 Julkaisut 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 Commitit
1 Haara
28KB
Haara: master
Branchit Tagit
${ item.name }
Create branch ${ searchTerm }
from 'master'
${ noResults }
Thorn Avery ed469e5c49 cleanup 4 vuotta sitten
README.md first commit 4 vuotta sitten
collatz.hs cleanup 4 vuotta sitten

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 ]