标签: lambda-calculus

我现在明白了类型签名s (s k):

s (s k)  :: ((t1 -> t2) -> t1) -> (t1 -> t2) -> t1

我可以在Haskell WinGHCi工具中创建无错误的示例:

示例:

s (s k) (\g -> 2) (\x -> 3)

回报2.

示例:

s (s k) (\g -> g 3) successor

回报4.

其中successor定义如下:

successor = (\x -> x + 1)

尽管如此,我仍然没有一个直观的感受了什么s (s k)呢.

该组合子s (s k)采取任何两个函数f和g.什么是s (s k)用做f …

我想弄清楚如何为下面的表达式绘制语法树.首先,这究竟是怎么表现的？看起来它需要1和2作为参数,如果n是0,它将只返回m.

此外,有人可以指出一个开始解析树,或一个例子？我找不到一个.

我刚刚为即将到来的OCaml测试做了一些功课,我遇到了一些麻烦.

考虑由以下抽象语法定义的λ项的语言(其中x是变量):

t ::= x | t t | ?x. t  

写一个类型术语来表示λ术语.假设变量表示为字符串.

好的,男孩.

# type t = Var of string | App of (t*t) | Abs of string*t;;
type t = Var of string | App of (t * t) | Abs of (string * t)

术语t的自由变量fv(t)由归纳定义如下:

fv(x) = {x}  
fv(t t') = fv(t) ? fv(t')  
fv(?x. t) = fv(t) \ {x}

当然可以.

# let rec fv term = match term with
Var x -> [x]
  | App (t, t') …

一般问题

我有一对数据类型,它们是表示同一事物的两种不同方式,一种是在String中记录变量名,另一种是在Int中记录变量名.目前,它们都是定义的.但是,我想描述第一个表示,第二个表示将由某种关系生成.

具体例子

具体来说,第一个是STLC术语Universe的用户定义版本,而第二个是同一事物的de Bruijn索引版本:

{-# LANGUAGE RankNTypes, GADTs, DataKinds, TypeOperators, KindSignatures, PolyKinds, TypeFamilies, UndecidableInstances, FunctionalDependencies, FlexibleInstances  #-} 


-- * Universe of Terms * -- 

data Term :: Type -> * where 
    Var :: Id -> Term a
    Lam :: Id -> Type -> Term b -> Term (a :-> b)
    App :: Term (a :-> b) -> Term a -> Term b 

    Let :: Id -> Term a -> Term b -> Term b 
    Tup :: Term a -> …

(这个问题是在研究Haskell时对此问题的跟进.)

我曾经发现"变量"和"价值"之间的概念令人困惑.因此,我阅读了关于lambda演算的wiki页面以及上面的上一个答案.我出来以下解释.

我可以确认这些是否正确吗？只想双重确认,因为这些概念非常基本但对函数式编程至关重要.欢迎任何建议.

维基的前提:

Lambda Calculus语法
exp→ID
| (exp)
| λID.exp//抽象
| exp exp //应用程序

(符号:"<=>"相当于)

解释:

1. "值":它是存储在计算机中的实际数据或指令.
   "变量":它是一种定位数据的方式,一种替换值的引用,但本身不是存储在计算机中的数据或指令集.
   "抽象"<=>"函数"∈句法形式.(/sf/answers/1773041021/)
   "应用程序":它接受"抽象"的输入,并且"lambda表达式"的输入产生"lambda表达式".
   "抽象"被称为"抽象",因为在通常的函数定义中,我们将(通常更长的)函数体缩写为更短的形式,即函数标识符后跟一个形式参数列表.(虽然lambda抽象是匿名函数,但其​​他函数通常都有名称.)

2. "可变" <=>"符号" <=>"引用"
   一个"可变的"是经由被称为"绑定"处理的"值"相关联.

3. "常数"∈"变量"
   "文字"∈"值"
   "形式参数"∈"变量"
   "实际参数"(参数)∈"值"

4. "变量"可以具有"数据"的"值"=>例如变量"a"具有值3

5. "变量"也可以具有"一组指令"的"值"=>例如,运算符"+"是变量

背景

我知道Iota减少用于减少/扩展递归函数.例如,给定以下简单递归函数的应用(自然数上的阶乘):

((fix fact (n:nat):nat := match n with | O => 1 | S m => n * fact m end) 2)

Iota缩减扩展了递归调用,有效地迭代递归函数一次:

Eval lazy iota in ((fix fact (n:nat):nat := match n with | O => 1 | S m => n * fact m end) 2).
 = (fun n:nat =>
    match n with
    | 0 => 1
    | S m =>
        n *
        (fix fact (m : nat) : nat :=
           match m with
           | 0 => …

这是一个无类型的lambda演算,其条款由它们的自由变量索引.我正在使用singletons库来获取类型级别字符串的单例值.

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}

import Data.Singletons
import Data.Singletons.TypeLits

data Expr (free :: [Symbol]) where
    Var :: Sing a -> Expr '[a]
    Lam :: Sing a -> Expr as -> Expr (Remove a as)
    App :: Expr free1 -> Expr free2 -> Expr (Union free1 free2)

A Var引入了一个自由变量.lambda抽象绑定一个在体内看起来是自由的变量(如果有匹配的那个).应用程序连接表达式的两个部分的自由变量,删除重复项(因此自由变量x y是x和y,而自由变量x x …

文章更简单,更容易!声称即使没有"Pi"存在也可以对依赖类型系统进行编码 - 也就是说,你可以重复使用"Lam"构造函数.但是,如果在某些情况下对"Pi"和"Lam"的处理方式不同,那又怎么可能呢？

此外,可以删除"明星"吗？我认为你可以用"λx.x"(id)替换它的所有出现.

我是haskell的初学者,并试图实现自然数字的Church编码,如本指南中所述.我从这个答案中使用了y组合器的定义,但不确定如何应用它.

我想实现在演算一个简单的功能,computues的[1..1]作为证明的总和这里.

{-# LANGUAGE RankNTypes #-}

import Unsafe.Coerce

y :: (a -> a) -> a
y = \f -> (\x -> f (unsafeCoerce x x)) (\x -> f (unsafeCoerce x x))

true = (\x y -> x)
false = (\x y -> y)

newtype Chur = Chr (forall a. (a -> a) -> (a -> a))

zer :: Chur
zer = Chr (\x y -> y)

suc :: Chur -> Chur
suc (Chr cn) …

所以我一直插科打诨与Python有点最近,我试图找到一种方式来输出Fibonacci序列的第n个数在一个单一的表达.这是我到目前为止编写的代码:

(lambda f: f if f<2 else (f-1)+(f-2))(n)
# n == 1 -> 1
# n == 2 -> 1
# n == 3 -> 3
# n == 4 -> 5
# n == 5 -> 7
....

但是,正如我在上面评论的那样,它只输出一组奇数.我很困惑为什么会发生这种情况,因为如果我要将其重新编写为命名的lambda函数,它看起来像这样:

f = lambda n: n if n<2 else f(f-1)+f(f-2)
# f(1) -> 1
# f(2) -> 1
# f(3) -> 2
# f(4) -> 3
...
# f(10) -> 55
...

现在我添加Lambda Calculus标签的原因是因为我不确定这个问题是否属于简单理解Python如何处理这个问题的范畴.我读过关于演算的Y组合一点点,但是这是一个外语对我无法从我发现这个约演算推导资源什么.

现在,我想这样做的一行代码,而不是命名它的原因,是因为我想尝试,并把这个lambda函数到列表理解.所以做这样的事情:

[(lambda f: f if f<2 else …