圖厄莫爾斯序列在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

回答

相關問題