Jak napisać cykl jako funkcję lambda?

Question

Tak dla zabawy, tu jest moja własna wersja cycle:

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

Bok prawy odnosi się zarówno do nazwy funkcji myCycle i parametru xs.

Czy możliwe jest wdrożenie myCyclebez wspomnieć myCycle lub xs na prawej stronie?

myCycle = magicLambdaFunction 

Answer 1

Czy możliwe jest wdrożenie myCycle bez wymieniania myCycle lub xs na prawej stronie?

Odpowiedź brzmi: tak i nie (niekoniecznie w tej kolejności).

Inne osoby wspomniały o stałym punkcie połączenia. Jeśli masz kombinator o stałym punkcie fix :: (a -> a) -> a, to jak wspominasz w komentarzu do odpowiedzi Pubby'ego, możesz napisać myCycle = fix . (++).

Ale średnia definicja fix to:

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

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

Należy zauważyć, że definicja fix polega wspomnieć zmienną lewy-boczny z prawej strony jego definicji (r w pierwszej definicji, fix' w drugim). Tak więc to, co do tej pory zrobiliśmy, to zepchnąć problem do zaledwie fix.

Interesującą rzeczą jest, aby pamiętać, że Haskell jest oparta na rachunku lambda wpisany, i nie bez powodu technicznej najbardziej wpisywanych kamieni lambda są zaprojektowane tak, że nie może„natywnie” wyrazić operator paradoksalny. Języki te stają się Turing-complete, jeśli dodasz dodatkową funkcję "na wierzchu" rachunku bazowego, która pozwala na obliczanie stałych punktów. Na przykład dowolny z nich będzie:

1. Dodaj fix jako prymitywu do rachunku.
2. Dodaj rekursywne typy danych (które ma Haskell, jest to inny sposób definiowania fix w Haskell).
3. Pozwolić, aby definicje odnosiły się do definiowanego identyfikatora po lewej stronie (który ma również Haskell).

Jest to przydatna rodzaj modułowości dla wielu powodów, jeden jest, że rachunek lambda bez punktów stałych jest również spójny dowód system logiki, inny że fix programy nie- w wielu takich systemów mogą być sprawdzone, aby zakończyć .

---

EDIT: Oto fix napisane rekurencyjnych typów. Teraz definicja samego fix nie jest rekurencyjny, ale definicja typu Rec jest:

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

myślę, że to działa:

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

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

W językach programowania, które obsługują funkcje anonimowe, kombinatorów stałoprzecinkowych pozwolić na określenie i wykorzystanie anonimowych rekurencyjnych funkcji, czyli bez konieczności wiązania takich funkcji z identyfikatorami. W tym ustawieniu użycie kombinatorów stałoprzecinkowych jest czasami nazywane rekondycją anonimową.

Answer 3

Dla zabawy Jest to kolejny materiał:

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

lub

let f = foldr1 (++) . repeat 

Answer 4

Nikt nie wskazał na „oczywisty” wersję rozwiązania fix jeszcze. Pomysł polega na przekształceniu nazwanego wywołania rekursywnego w parametr.

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

Ten „rekurencyjne nazwa” wprowadzenie trik jest dość dużo, co let in robi w Haskell. Jedyna różnica polega na tym, że użycie wbudowanego konstruktu jest prostsze i prawdopodobnie lepsze dla implementacji.