tA
/
Collatz
1
0
Fork 0
Código Incidencias 0 Pull Requests 0 Lanzamientos 0 Wiki Actividad
Collatz in Type Level
No puede seleccionar más de 25 temas Los temas deben comenzar con una letra o número, pueden incluir guiones ('-') y pueden tener hasta 35 caracteres de largo.
2 Commits
1 Rama
28KB
Rama: master
Ramas Etiquetas
${ item.name }
Crear rama ${ searchTerm }
desde 'master'
${ noResults }
Collatz/README.md

847B
Original Enlace permanente Blame Histórico

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 ]