标签: lambda-calculus

我将Thue-Morse 序列的定义写为一行 Haskell 中的无限整数列表：

thueMorse = 0:1:f (tail thueMorse) where f = (\(x:xs) -> x:(1 - x):f xs)

这是尝试在一行中定义序列失败的结果，仅根据 lambda 表达式及其本身，没有 let 或 where 表达式（实际上应该在两行中呈现，使上述解决方案在精神上成为两行） ）。我已经阅读了一些有关 lambda 演算的内容，所以我想我应该尝试将其作为练习。我想知道 Haskell 中是否有可能实现这样的事情，如果可能的话该怎么做。

thueMorse = 0:1:(\f xs -> f f xs) (\f (x:xs) -> x:(1 - x):f f xs) ((\(_:xs) -> xs) thueMorse)

上面的表达式有点难以阅读，所以我将其分解：

(\f xs -> f f xs)

接受一个函数和一个参数，并将该函数应用于自身和参数。Haskell 不会计算这个表达式，因为 f 的类型是t = t -> a -> a，这是我问题的关键。

(\f (x:xs) -> x:(1 - x):f f xs)

是传递给前一个表达式的函数，它将自身和列表作为参数。这是递归计算 Thue-Morse …

lambda 演算中的 Eta 抽象意味着跟随。

函数f可以写成\x -> f x

• Eta 抽象在减少 lambda 表达式时有什么用处吗？
• 它只是某些表达式的另一种书写方式吗？

实际用例将不胜感激。

一段时间以来，我一直在为 Lambda 微积分苦苦挣扎。有很多资源可以解释如何减少嵌套的 lambda 表达式，但很少能指导我编写自己的 lambda 表达式。

我正在尝试使用纯 lambda 演算（即，单参数函数，教堂数字）在 Racket 中编写递归斐波那契解决方案。

这些是我一直在使用的教会数字的定义：

(define zero  (? (f) (? (x) x)))
(define one   (? (f) (? (x) (f x))))
(define two   (? (f) (? (x) (f (f x)))))
(define three (? (f) (? (x) (f (f (f x))))))
(define four  (? (f) (? (x) (f (f (f (f x)))))))
(define five  (? (f) (? (x) (f (f (f (f (f x))))))))
(define six   (? (f) (? (x) (f (f (f (f …

我正在研究 Haskell lambda 演算解释器。我有一种方法可以将表达减少到正常形式。

type Var = String

data Term =
    Variable Var
  | Lambda   Var  Term
  | Apply    Term Term
  deriving Show

normal :: Term -> Term
normal (Variable index)      = Variable index
normal (Lambda var body)       = Lambda var (normal body)
normal (Apply left right) = case normal left of
    Lambda var body  -> normal (substitute var (normal right) body)
    otherwise -> Apply (normal left) (normal right)

如何将所采取的步骤保存到集合中？

我的正常函数输出这个： \a. \b. a (a (a (a b))) 我的目标是让所有步骤如下：

(\f. …

如何扩展简单类型的 lambda 演算以拥有支持类似 monad 类型的类型系统？基本上，我目前对简单类型的 lambda 演算有很好的理解，并且我想了解将 monad 添加到该基础的“最低要求”。通过“添加 monad”，我的意思是任何会产生具有操作语义和类型分配的语言，允许人们在某种程度上识别 monad 对程序的“有用性”。例如，Haskell 在合理的意义上支持 monad，即使它不要求程序员完全证明他们的“monad”实例实际上遵守 monad 定律。

我希望了解一些使用 monad 扩展 STLC 的最小方法，以便更多地了解与编程语言理论相关的 monad。就我个人而言，我发现在更精简/基本的环境中学习这些东西更容易（而不是仅仅在像 haskell 这样的语言中在实践中使用它们）。出于这个原因，除了我上面写的内容之外，我无法对我正在寻找的内容进行更准确的描述。

编辑，关于@Ben 的评论：你能不能有某种设置，你有一个“原子”单子M的签名，然后你的简单类型T现在是：

T = ? | Ť ₁？T ₂ | 米 Ť

在哪里？是来自原子类型签名的原子类型，并且m是M的元素。

然后也许您还向 lambda 演算项添加常数项：

t = x | t ₁ t ₂ | ? ×。吨| 返回t | t ₁ >>= t ₂ $

我不确定这是否可行，但看起来像这样的事情是可能的。

在Haskell中实现call-by-value lambda-calculus时,我是否应该强制对对象语言中的函数的参数求值(即,按值调用lambda-calculus)来绕过需要的调用元语言的评估顺序(即Haskell)？

具体而言,对于使用高阶抽象语法的以下实现:

data Exp
  = Abs (Exp -> Exp)
  | App Exp Exp

eval :: Exp -> Exp
eval exp = case exp of
  Abs _       -> exp
  App opr opd -> case eval opr of
    Abs fun -> eval (fun $ eval opd)  -- argument evaluation

与注释的行,我应该逼的评价eval opd用fun $! eval opd呢？

我知道CPS转换可以避免对象和元级别之间的评估顺序依赖性.但我暂时不想打扰它.我只是想确保在Haskell中忠实地实现call-by-value.我提出了这个问题,因为我看到的许多示例实现似乎都没有考虑到这一点.我的意思是那些实现不强制eval opd.我想知道是否是他们忽视它或者我考虑得太多了.谢谢.

我正在做lambda演算,在我的教科书中,它说你将如何let*使用lambda演算.

我的答案:x,y和z是参数; v1,v2和v3参数; e是身体:

((lambda (x y z) (e)) v1 v2 v3)

书中的答案:

  ((lambda(x)
    ((lambda(y)
      ((lambda(z) e) v3))
      v2))
    v1)

我不确定我的回答是否相同.如果没有,为什么我的回答是错误的,如何得出原始答案？

我正在研究haskell中一个非常基本的问题.我试图计算字符串中的小写字母数.我的解决方案是这个

import Data.Char

lowercaseCount :: String -> Int
lowercaseCount x = length $ filter isLower x

我正在看实际的实现,lowercaseCount并看到它似乎应该能够减少eta.我试过这个

lowercaseCount = length $ filter isLower

但GHC对我大喊大叫

无法将预期类型[Char] -> Int 与实际类型匹配Int

我想知道为什么这个eta减少是非法的,并且如果有办法使这个功能能够以eta减少的形式.

我正在尝试编写一些读取Lambda表达式并输出beta缩减版本的内容.Lambdas的输入方式如下:\ variable - > expression和applications将采用(表达式)(表达式)的形式.因此,如果在字符串的开头找到'\',它知道处理一个Lambda,如果找到'(',它知道处理一个应用程序.

我有一个Lambda表达式定义的类型:

data Expression = Variable String
                | Lambda Expression Expression 
                | Apply Expression Expression 

这是我第一次尝试编写读取输入的函数

processInput :: String -> Expression
processInput ('\':input) = processLambda input
processInput ('(':input) = processApply input
processInput str         = Variable str

当我尝试加载此功能时,我得到了

lexical error in string/character literal at ':'

所以我尝试使用警卫:

processInput input
    | head input == '\'                      = processLambda (tail input)
    | head input == '('                      = processApply (tail input)
    | otherwise                              = Variable input

但得到了

lexical error in string/character literal …

如何在不使用lambda演算的递归的情况下编写阶乘函数？这意味着数学符号不能在任何特定的编程语言中实现.