鉴于一个教堂编码数字作为CEK机器的封闭结果，如何取回数字？

Question

我已经实现了CEK机器。鉴于此算法的闭包结果以及此闭包是Church编码数字的知识，打印数字的最佳方法是什么？

使用以下类型：

data Term = Var String | Abs String Term | App Term Term
data Clos = Clos String Term Env
type Env = [(String, Clos)]

编辑：使这个模糊的问题更清楚：用(\n f x -> f (n f x)) (\f x -> x)（s z）启动我的机器我最终得到：

(\f -> (\x -> (f ((n f) x)))) :: Term
[("n", Clos((\f -> (\x -> x)), []))] :: Env

这是一个数据结构，表示代表教堂数字的闭包。如何将此结构更改为数字？我是否必须遍历闭包的环境并替换Term中的变量（听起来效率低下）？我需要重命名吗？

编辑：实际代码：

data Term = Var String | Abs String Term | App Term Term deriving (Show)
data Clos = Clos String Term Env deriving (Show)
type Env = [(String, Clos)]
data Frame = FArg Term Env | FFun Clos deriving (Show)
data State = State Term Env [Frame] deriving (Show)

step :: State -> Maybe State
step (State (Var x) env k) = fmap (\(Clos y b env') -> State (Abs y b) env' k) $ lookup x env
step (State (App a b) env k) = return $ State a env (FArg b env : k)
step (State (Abs x b) env (FArg t env' : k)) = return $ State t env' (FFun (Clos x b env) : k)
step (State (Abs x b) env (FFun (Clos y b' env') : k)) = return $ State b' ((y, Clos x b env) : env') k
step _ = Nothing

steps :: State -> State
steps st = maybe st steps (step st)

z = Abs "f" $ Abs "x" $ Var "x"
s = Abs "n" $ Abs "f" $ Abs "x" $ App (Var "f") $ App (App (Var "n") (Var "f")) (Var "x")
term = App s z
result = steps $ State term [] []
main = putStrLn $ show result

结果是：

State (Abs "f" (Abs "x" (App (Var "f") (App (App (Var "n") (Var "f")) (Var "x"))))) [("n",Clos "f" (Abs "x" (Var "x")) [])] []

Answer 1

教会数字是两个参数的函数

type Church a = (a -> a) -> a -> a

第二个参数是零的情况，第一个参数是增量情况。所以你只需要将数字应用于一对合适的参数以获得一些（通常是数字的）数据类型：

fromChurch c = c (+ 1) (0 :: Int)