403
правки
Изменения
Нет описания правки
\begin{array}{r c l}
\langle Term \rangle & ::= & \langle Variable \rangle \\
& || & \langle Term \rangle \langle Term \rangle \\ & || & \lambda \langle Variable \rangle \to \langle Term \rangle\\ & || & ( \langle Term \rangle )\\
\langle Variable \rangle & ::= & \langle Char \rangle *\\
\end{array}
...и всего через 314007 <tex>\beta</tex>-редукций вы узнаете, что третье простое число {{---}} семь!
Для работы со списками чисел нам понадобятся следующие функции:
Список будем хранить в следующем виде: $<tex>\langle len, p_1^{a_1}p_2^{a_2}\ldots p_{len}^{a_{len}} \rangle$</tex>. При этом, голова списка будет храниться как показатель степени при $<tex>p_{len}$</tex>. <tex>\operatorname{empty} = \operatorname{pair}\ \operatorname{zero}\ \bar 1</tex> <tex>\operatorname{cons} = \lambda h \to \lambda t \to \operatorname{pair}\ (\operatorname{succ}\ (\operatorname{fst}\ t))\ (\operatorname{mult}\ (\operatorname{snd}\ t)\ (\operatorname{power}\ (\operatorname{ithPrime}\ (\operatorname{fst}\ t))\ h))</tex>
head = Lam "list" $ getExponent `App` (snd'' `App` Var "list")
`App` (ithPrime `App` (pred' `App` (fst'' `App` Var "list")))