如何在Haskell中编写递归lambda表达式？ [英] How to write recursive lambda expression in Haskell?

问题描述

我不确定这是否是好的编程习惯，但我想知道是否可以使用lambda表达式定义递归函数。

这是我编写的一个仿真例子：所以可以递归地定义Haskell中的阶乘函数如下

  factorial :: Integer  - >整数
阶乘1 = 1 
阶乘（n + 1）=（n + 1）*阶乘n 
  

现在，我想要一个函数 f ，使得 fn =（factorial n）+ 1 。我不想为 factorial n （即事先定义它）命名，而是定义 f ，其中 factorial n 在 f 定义内给出了一个lambda表达式。我可以在 f 中使用递归lambda定义来代替使用名称阶乘吗？

解决方案

使用纯lambda表达式执行递归的规范方法是使用 fixpoint combinator ，是一个带有属性的函数

$ p $ fixpoint fx = f（fixpoint f）x


如果我们假设存在这样一个组合器，我们可以将递归函数写为

  factorial = fixpoint（\ff n  - > if n == 1 then 1 else n * ff（n-1））
  

唯一的问题是 fixpoint 本身仍然是递归的。在纯lambda演算中，可以创建仅包含lambda表达式的定点组合器，例如经典的Y combinator：

  fixpoint f =（\ x  - > f（xx））（\ x  - > f（xx））
  

但是我们仍然有问题，因为根据Haskell这个定义不是很好的类型 - 并且可以证明有没有办法来编写一个很好的类型仅使用lambdas和函数应用程序的fixpoint组合器。它可以通过使用辅助数据类型来完成某种类型的递归：

  data Paradox a = Self（Paradox a - > a）
固定点f =让一半（自己的双胞胎）= f（双胞胎（自己的双胞胎））
一半（自己的一半）
  pre> 
 
 
（请注意，如果单数据类型的注入和投影被删除，这就是Y组合！）
I am not sure if this is good programming practice, but I would like to know if one can define a recursive function using the lambda expression. 

This is an artificial example I made up: So one can defined the factorial function in Haskell recursively as follows 
factorial :: Integer -> Integer 
factorial 1 = 1
factorial (n + 1) = (n + 1) * factorial n
Now, I want a function f such that f n = (factorial n) + 1. Rather than using a name for factorial n (i.e. defining it before hand), I want to define f where factorial n is given a lambda expression within the definition of f. Can I use a recursive lambda definition in f in place of using the name factorial? 
解决方案
The canonical way to do recursion with pure lambda expressions is to use a fixpoint combinator, which is a function with the property
fixpoint f x = f (fixpoint f) x
If we assume that such a combinator exists, we can write the recursive function as
factorial = fixpoint (\ff n -> if n == 1 then 1 else n * ff(n-1))
The only problem is that fixpoint itself is still recursive. In the pure lambda calculus, there are ways to create fixpoint combinators that consist only of lambdas, for example the classical "Y combinator":
fixpoint f = (\x -> f (x x)) (\x -> f (x x))
But we still have problems, because this definition is not well-typed according to Haskell -- and it can be proved that there is no way to write a well-typed fixpoint combinator using only lambdas and function applications. It can be done by use of an auxiliary data type to shoehorn in some type recursion:
data Paradox a = Self (Paradox a -> a)
fixpoint f = let half (Self twin) = f (twin (Self twin))
             in half (Self half)
(Note that if the injections and projections from the singleton data type are removed, this is exactly the Y combinator!)

                        
这篇关于如何在Haskell中编写递归lambda表达式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！