haskell - 我如何将循环编写为 lambda 函数？

Question

只是为了好玩，这是我自己的版本cycle：

myCycle :: [a] -> [a]
myCycle xs = xs ++ myCycle xs

右侧指的是函数名myCycle和参数xs。

是否可以myCycle 不提及myCycle或xs在右侧实施？

myCycle = magicLambdaFunction

Answer 1

是否可以myCycle不提及myCycle或xs在右侧实施？

答案是肯定的和否定的（不一定按这个顺序）。

其他人提到了定点组合器。如果您有一个定点组合器fix :: (a -> a) -> a，那么正如您在对 Pubby 答案的评论中提到的那样，您可以编写myCycle = fix . (++).

但标准定义fix是这样的：

fix :: (a -> a) -> a
fix f = let r = f r in r

-- or alternatively, but less efficient:
fix' f = f (fix' f)

请注意， 的定义fix涉及在其定义的右侧提及左侧变量（r在第一个定义中，fix'在第二个定义中）。所以到目前为止，我们真正做的是把问题推到fix.

有趣的是，Haskell 基于类型化的 lambda 演算，出于良好的技术原因，大多数类型化的 lambda 演算都被设计为不能“原生”表达定点组合子。如果您在允许计算固定点的基本微积分“顶部”添加一些额外功能，这些语言才会成为图灵完备的。例如，其中任何一个都可以：

1. 添加fix为微积分的基元。
2. 添加递归数据类型（Haskell 有；这是fix在 Haskell 中定义的另一种方式）。
3. 允许定义引用正在定义的左侧标识符（Haskell 也有）。

这是一种有用的模块化类型，原因有很多——一个是没有固定点的 lambda 演算也是逻辑的一致证明系统，另一个是fix许多此类系统中的更少程序可以被证明可以终止。

---

编辑：这里是fix用递归类型编写的。现在fix本身的定义不是递归的，但是Rec类型的定义是：

-- | The 'Rec' type is an isomorphism between @Rec a@ and @Rec a -> a@:
--
-- > In  :: (Rec a -> a) -> Rec a
-- > out :: Rec a        -> (Rec a -> a)
--
-- In simpler words:
--
-- 1. Haskell's type system doesn't allow a function to be applied to itself.
--
-- 2. @Rec a@ is the type of things that can be turned into a function that
--    takes @Rec a@ arguments.
--
-- 3. If you have @foo :: Rec a@, you can apply @foo@ to itself by doing
--    @out foo foo :: a@.  And if you have @bar :: Rec a -> a@, you can do 
--    @bar (In bar)@.
--
newtype Rec a = In { out :: Rec a -> a }

-- | This version of 'fix' is just the Y combinator, but using the 'Rec'
-- type to get around Haskell's prohibition on self-application (see the
-- expression @out x x@, which is @x@ applied to itself):
fix :: (a -> a) -> a
fix f = (\x -> f (out x x)) (In (\x -> f (out x x)))

Answer 2

我认为这有效：

myCycle = \xs -> fix (xs ++)

http://en.wikipedia.org/wiki/Fixed-point_combinator

在支持匿名函数的编程语言中，定点组合器允许定义和使用匿名递归函数，即不必将这些函数绑定到标识符。在这种情况下，定点组合器的使用有时称为匿名递归。

Answer 3

为了好玩，这是另一回事：

let f = foldr (++) [] . repeat 

或者

let f = foldr1 (++) . repeat

Answer 4

还没有人指出修复解决方案的“明显”版本。这个想法是将命名的递归调用转换为参数。

let realMyCycle = fix (\myCycle xs -> xs ++ myCycle xs)

这个“递归名称”引入技巧几乎就是let inHaskell 中所做的。唯一的区别是使用内置结构更直接，并且可能更好地实现。