j'ai écrit une définition pour le Thue-Morse squence comme une liste infinie d'entiers dans une ligne de Haskell:Séquence Thue-Morse dans une ligne de Haskell
thueMorse = 0:1:f (tail thueMorse) where f = (\(x:xs) -> x:(1 - x):f xs)
Ceci est le résultat d'une tentative avortée de définir la séquence en une seule ligne, seulement en termes d'expressions lambda et elle-même, sans laisser ou où expressions (qui devrait vraiment être présenté sur deux lignes, faisant de la solution ci-dessus un double revêtement dans l'esprit). J'ai lu un peu sur le lambda-calcul, alors j'ai pensé que je l'essayerais comme un exercice. Je voudrais savoir si quelque chose comme ça est possible chez Haskell, et comment le faire si c'est possible.
thueMorse = 0:1:(\f xs -> f f xs) (\f (x:xs) -> x:(1 - x):f f xs) ((\(_:xs) -> xs) thueMorse)
L'expression ci-dessus est un peu difficile à lire, donc je vais le décomposer:
(\f xs -> f f xs)
prend une fonction et un argument et applique cette fonction elle-même et l'argument. Haskell n'évaluera pas cette expression car f a le type t = t -> a -> a, qui est le point crucial de mon problème.
(\f (x:xs) -> x:(1 - x):f f xs)
La fonction est passée à l'expression précédente, qui se prendra elle-même et une liste en arguments. C'est la partie qui calcule récursivement la séquence Thue-Morse. Cela a également un type infini t = t -> [a] -> [a].
((\(_:xs) -> xs) thueMorse)
Ceci est juste l'équivalent de (tail thueMorse), mais écrit en termes d'expressions lambda pour répondre aux conditions de l'exercice.
Haskell se plaint que ces expressions ont un type infini et refuse de les évaluer, peu je pense que si elles étaient évaluées, elles généreraient correctement la séquence Thue-Morse. Est-il possible de tordre l'interprète ou le bras du compilateur dans l'évaluation de ces expressions? Existe-t-il un moyen d'ajuster l'instruction pour qu'elle puisse être évaluée tout en utilisant seulement les opérateurs de lambda calculus, et en une ligne?
Si vous voulez juste voir si l'algorithme est correct (quel que soit son type), vous pourriez saupoudrer un peu [ 'unsafeCoerce'] (https : //hackage.haskell.org/package/base-4.7.0.0/docs/Unsafe-Coerce.html) sur le code. Ne faites pas cela en production, cependant. – rightfold
Vous avez besoin d'une récursivité, vous aurez donc besoin d'un opérateur de point fixe à un moment donné. Vous pouvez réutiliser la norme ('Data.Function.fix'), la définir vous-même, ou faire en sorte que votre définition produise à la fois' thuleMorse' et 'f' simultanément plutôt que seulement' thuleMorse'. –
@MadameElyse, merci pour la suggestion! L'insertion de 'unsafeCoerce' fait que l'interpréteur évalue l'expression, et le résultat est en effet la séquence de Thule-Morse! Ici c'est avec 'unsafeCoerce' inséré:' thuleMorseUnsafe = 0: 1: (\ f xs -> unsafeCoerce ff xs) (\ f (x: xs) -> x: (1 - x): unsafeCoerce ff xs) ((\ (_: xs) -> xs) thuleMorseUnsafe) '. Existe-t-il un moyen plus propre de faire cela? –