tA
/
Collatz
1
0
Förgrening 0
Kod Ärenden 0 Pull-förfrågningar 0 Släpp 0 Wiki Aktiviteter
Collatz in Type Level
Du kan inte välja fler än 25 ämnen Ämnen måste starta med en bokstav eller siffra, kan innehålla bindestreck ('-') och vara max 35 tecken långa.
2 Incheckningar
1 Gren
28KB
Gren: master
Grenar Taggar
${ item.name }
Skapa branchen ${ searchTerm }
från 'master'
${ noResults }
Collatz/README.md

847B
Rå Permalänk Blame Historik

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 ]