图厄莫尔斯序列在Haskell

的一行我在Haskell的一行写的Thue-Morse squence定义为整数的无限名单：图厄莫尔斯序列在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序列的部分。这也有一个无限的类型t = t -> [a] -> [a]。

((\(_:xs) -> xs) thueMorse)

这是(tail thueMorse)只是相当，但写在lambda表达式的条款，以满足行权条件。

Haskell抱怨说这些表达式有无限类型并拒绝评估它们，我认为如果评估它们，它们会正确地生成Thue-Morse序列。有什么方法可以将解释器或编译器的手臂转换为评估这些表达式吗？有没有办法调整语句，以便它可以被评估，但仍然只能使用lambda微积分运算符，并在一行中？

来源

2016-02-06 castle-bravo

如果你只是想看到的算法是否正确（不管其类型），你可以撒上一些['unsafeCoerce']（HTTPS ：//hackage.haskell.org/package/base-4.7.0.0/docs/Unsafe-Coerce.html）。不过，不要在生产中这样做。 – rightfold

您需要递归，所以您需要在某个点有一个定点操作符。你可以重用标准的（'Data.Function.fix'），自己定义它，或者让你的定义同时生成'thuleMorse'和'f'，而不是'thuleMorse'。 –

@MadameElyse，谢谢你的建议！插入'unsafeCoerce'让解释器评估表达式，结果确实是Thule-Morse序列！这里使用'unsafeCoerce'插入：'（\ f（xs） - > x：（1-x）：unsafeCoerce ff xs）（（ \（_：xs） - > xs）thuleMorseUnsafe）'。有没有一种更清洁的方式来做到这一点？ –

这里是相同的算法，但没有明确的fix：

thueMorse = 0 : 1 : (tail thueMorse >>= \x -> [x, 1 - x])

来源

2016-02-07 01:43:16 user3237465

这是迄今为止最简洁的变化。 –

它比我的基于修正的版本稍微快一点，为了获得序列的第1亿个元素，使用基于修正的版本获得12.281秒，使用你的版本获得11.079秒（'ghc -e“...”'）。我的原始版本也花了超过12秒。 –

图厄莫尔斯序列在Haskell

回答

相关问题