Dopcn's Blog

life and work

过程数据二元对立之用过程复合数据

Posted at — Nov 12, 2015

复合数据只要拥有满足一定条件的构造函数、选择函数和约束规则,甚至不需要是由基本数据复合,church 计数是一个以 lambda 表达式为唯一元素,构建数值、数值运算等编程要素的系统,在church 计数中 0 和 加1 运算分别被定义为

func zero<T>(f:(T->T)) -> T->T {
    return {x in
        return x}
}

func add_1<T>(n:(T->T) -> T->T) -> (T->T) -> T->T {
    return {f in
        return {x in
            return f(n(f)(x))
        }
    }
}

0 是一个以函数为参数返回一个函数的过程,加1 运算是作用于类似 0 这样的过程之上返回一个新过程的函数,将 0 带入 加1 运算得到 1 的定义,带入 1 得到 2 的定义

func one<T>(f:(T->T)) -> T->T {
    return {x in
        return f(x)}
}

func two<T>(f:(T->T)) -> T->T {
    return {x in
        return f(f(x))
    }
}

形式上讲 church 计数的正整数可以看做应用参数函数的过程,0 是应用 0 次直接返回原值,1 是返回应用 1 次得到的返回值,以此类推。加法的定义是先应用第一个加数次,再应用第二个加数次,乘法是应用次数之积次

func plus<T>(operand1 operand1: (T->T) -> T->T, operand2: (T->T) -> T->T) -> (T->T) -> T->T {
    return {f in
        return {x in
            return operand2(f)(operand1(f)(x))
        }
    }
}

func mult<T>(operand1 operand1: (T->T) -> T->T, operand2: (T->T) -> T->T) -> (T->T) -> T->T {
    return {f in
        return {x in
            return operand2(operand1(f))(x)
        }
    }
}

减法的定义先考虑简单的情况,任意给定一个过程进行减 1,从概念上讲应该是应用给定过程的减 1 次,实现方法:

我没想出来