Wie würde ich den Zyklus als Lambda-Funktion schreiben?

Question

Just for fun, hier ist meine eigene Version von cycle:

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

Die rechte Seite bezieht sich sowohl auf den Namen der Funktion myCycle und dem Parameter xs.

Ist es möglich, myCycle zu implementieren ohnemyCycle oder xs auf der rechten Seite erwähnen?

myCycle = magicLambdaFunction 

Answer 1

Ist es möglich, ohne zu implementieren myCyclemyCycle oder xs auf der rechten Seite zu erwähnen?

Die Antwort ist ja und nein (nicht unbedingt in dieser Reihenfolge).

Andere Leute haben den Fixpunktkombinator erwähnt. Wenn Sie einen Fixpunktkombinator fix :: (a -> a) -> a haben, können Sie, wie Sie in einem Kommentar zu Pubbys Antwort schreiben, myCycle = fix . (++) schreiben.

Aber die Standard-Definition von fix ist dies:

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

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

Beachten Sie, dass die Definition von fix beinhaltet eine linksseitige Variable auf der rechten Seite seiner Definition (r in der ersten Definition zu erwähnen, fix' in der zweiten). Was wir bisher wirklich gemacht haben, ist das Problem auf fix zu schieben.

Das Interessante daran ist zu beachten, dass Haskell auf einem typisierten Lambda-Kalkül basiert, und das aus gutem technischen Grund, die meisten typisierten Lambda-Kalküle sind so ausgelegt, dass sie nicht „nativ“ den Punkt combinator fixiert auszudrücken. Diese Sprachen werden nur dann Turing-vollständig, wenn Sie ein zusätzliches Feature "on top" des Basiskalküls hinzufügen, das die Berechnung von Fixpunkten ermöglicht. Zum Beispiel wird jeder von diesen tun:

1. Fügen Sie fix als primitive zum Kalkül.
2. Hinzufügen rekursiver Datentypen (die Haskell hat; dies ist eine andere Möglichkeit, fix in Haskell zu definieren).
3. Lassen Sie zu, dass die Definitionen sich auf die zu definierende Kennung auf der linken Seite beziehen (die Haskell ebenfalls hat).

Dies ist eine nützliche Art von Modularität aus vielen Gründen-on ist, dass ein Lambda-Kalkül ohne Fixpunkte ist auch ein Proof-System für die Logik, eine andere, dass fix -weniger Programme in vielen solchen Systemen nachgewiesen werden kann, beenden .

---

EDIT: Hier fix mit rekursiven Typen geschrieben. Nun ist die Definition von fix selbst ist nicht rekursiv, aber die Definition des Rec Typs ist:

-- | 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

Ich denke, das funktioniert:

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

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

In Programmiersprachen, die anonyme Funktionen, ermöglichen Festpunkt combinators die Definition und Verwendung anonymer rekursiven Funktionen, dh ohne müssen solche Funktionen an Identifikatoren binden. In dieser Einstellung wird die Verwendung von Fixpunktkombinatoren manchmal als anonyme Rekursion bezeichnet.

Answer 3

Für Spaß ist dieses andere Zeug:

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

oder

let f = foldr1 (++) . repeat 

Answer 4

Niemand noch die „offensichtlich“ Version der Fixier-Lösung aufgezeigt. Die Idee ist, dass Sie den genannten rekursiven Aufruf in einen Parameter umwandeln.

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

Dieses "rekursiven Name" Trick Einführung ist ziemlich viel, was let in in Haskell tut. Der einzige Unterschied besteht darin, dass die Verwendung des integrierten Konstrukts einfacher und wahrscheinlich für die Implementierung angenehmer ist.