我如何将循环写为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