Jest to fajne ćwiczenie, dzięki któremu można płynniej posługiwać się tym językiem programowania, którego zamierzałeś się uczyć, ale majstrowałeś tylko lekko. Obejmuje to pracę z obiektami, używanie lub symulowanie zamknięć i rozciąganie układu czcionek.
Twoim zadaniem jest napisanie kodu do zarządzania listami leniwymi, a następnie użycie go do zaimplementowania tego algorytmu do generowania liczb Fibonacciego:
Próbki kodu znajdują się w Haskell
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
in take 40 fibs
Wynik:
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]
Implementacja listy leniwej powinna spełniać następujące wytyczne:
- Węzeł listy jest jedną z trzech rzeczy:
- Zero - pusta lista.
[]
- Wady - Pojedynczy element, w połączeniu z listą pozostałych elementów:
1 : [2,3,4,5]
(:
jest operatorem wad w Haskell) - Thunk - odroczone obliczenia, które w razie potrzeby tworzą węzeł List.
- Zero - pusta lista.
- Obsługuje następujące operacje:
- zero - Zbuduj pustą listę.
- Minusy - Zbuduj komórkę przeciw.
- thunk - Zbuduj Thunk, biorąc pod uwagę funkcję, która nie przyjmuje argumentów i zwraca zero lub minus.
- force - Biorąc pod uwagę węzeł listy:
- Jeśli jest to zero lub minus, po prostu go zwróć.
- Jeśli jest to Thunk, wywołaj jego funkcję, aby uzyskać zero lub minusy. Wymień thunk na zero lub minusy i zwróć go.
Uwaga: Zastąpienie thunk jego wymuszoną wartością jest ważną częścią definicji „leniwy” . Jeśli ten krok zostanie pominięty, powyższy algorytm Fibonacciego będzie zbyt wolny.
- puste - Sprawdź, czy węzeł listy ma wartość zero (po wymuszeniu).
- head (aka „car”) - Zdobądź pierwszą pozycję na liście (lub rzuć dopasowanie, jeśli to zero).
- tail (aka „cdr”) - Pobierz elementy za nagłówkiem listy (lub rzuć pas, jeśli jest zero).
- zipWith - Biorąc pod uwagę funkcję binarną (np.
(+)
) i dwie (być może nieskończone) listy, zastosuj funkcję do odpowiednich pozycji list. Przykład:
zipWith (+) [1,2,3] [1,1,10] == [2,3,13]
- take - Biorąc pod uwagę liczbę N i listę (być może nieskończoną), weź pierwsze N elementów listy.
- print - Wydrukuj wszystkie elementy z listy. Powinno to działać przyrostowo, jeśli podano długą lub nieskończoną listę.
fibs
używa się w swojej własnej definicji. Konfigurowanie leniwej rekurencji jest nieco trudne; musisz zrobić coś takiego:- Przydziel thunk za
fibs
. Na razie pozostaw to w stanie manekina. - Zdefiniuj funkcję thunk, która zależy od odwołania do
fibs
. - Zaktualizuj thunk z jego funkcją.
Możesz ukryć tę hydraulikę, definiując funkcję,
fix
która wywołuje funkcję zwracającą listę z własną wartością zwracaną. Rozważ krótką drzemkę, aby ten pomysł mógł się wprowadzić.- Przydziel thunk za
Polimorfizm (zdolność do pracy z listami dowolnego rodzaju przedmiotów) nie jest wymagany, ale sprawdź, czy możesz znaleźć sposób, aby to zrobić, idiomatyczne w twoim języku.
- Nie martw się o zarządzanie pamięcią. Nawet języki z odśmiecaniem mają tendencję do przenoszenia obiektów, których już nigdy nie użyjesz (np. Na stosie wywołań), więc nie zdziw się, jeśli twój program wycieknie pamięć podczas przeglądania nieskończonej listy.
Zachęcamy do nieznacznego odstępstwa od tych wytycznych, aby uwzględnić szczegóły dotyczące Twojego języka, lub do poszukiwania alternatywnych podejść do leniwych list.
Zasady:
- Wybierz język, którego nie znasz dobrze. Nie mogę tego „wymagać”, stąd tag „honor-system”. Głosujący mogą jednak sprawdzić Twoją historię, aby zobaczyć, w jakich językach piszesz.
Nie używaj wbudowanej obsługi leniwych list w swoim języku do robienia wszystkiego. Zamieść coś znaczącego lub co najmniej interesującego.
Haskell jest prawie nieobecny. To znaczy, chyba że zrobisz coś takiego:
data List a = IORef (ListNode a) data ListNode a = Nil | Cons !a !(List a) | Thunk !(IO (ListNode a))
Uwaga: nie ścisła ocena Haskell nie jest niedostępna, ale implementacja leniwej listy nie powinna bezpośrednio czerpać z niej możliwości. W rzeczywistości interesujące byłoby stworzenie wydajnego, czysto funkcjonalnego rozwiązania, które nie wymaga lenistwa.
Pyton:
- Nie używaj narzędzi itertools.
- Generatory są w porządku, ale korzystasz z nich, musisz znaleźć sposób na zapamiętanie wartości wymuszonych.
źródło
zipWith
dwóch list o różnych długościach?zipWith (+) [1,2,3,4,5] [0,0,0] == [1,2,3]
. Nie ma to jednak znaczenia dla powyższego algorytmu Fibonacciego, ponieważ oba argumenty zipWith są nieskończonymi listami.fibs
poprawnie go wdrożyć , ponieważ zależy to od niego samego. Zaktualizowałem pytanie, aby rozwinąć leniwą rekurencję. FUZxxl sam to zrozumiał.Odpowiedzi:
Postscriptum
Mam grał z PostScript przed , ale nie powiedziałbym, wiem to szczególnie dobrze (w rzeczywistości, wydaje mi się, że można policzyć liczbę ludzi na świecie, który naprawdę zna PostScript jedną ręką).
Odszedłem od twojej specyfikacji, ponieważ funkcja użyta do utworzenia thunk może zwrócić kolejną thunk;
force
będzie kontynuować ocenę, aż wynik będzie anil
lub acons
.Listy są implementowane jako słowniki:
Kod następuje. Zauważ, że nadpisujemy niektóre wbudowane operatory (w szczególności
print
; nie sprawdziłem, czy jest więcej); w prawdziwym świecie trzeba to uważać. Oczywiście nie będzie żadnego zastosowania w świecie rzeczywistym, więc nie ma sprawy.Komentarze przed procedurami należy rozumieć jako
tzn. wyświetlenie oczekiwanej zawartości stosu przed wywołaniem i wynikowej zawartości stosu po wywołaniu. Komentarze w ramach procedur pokazują zawartość stosu po wykonaniu określonego wiersza.
Załaduj to do Ghostscript, ignorując wyświetlaną stronę - pracujemy tylko z tłumaczem. Oto algorytm Fibonacciego:
Dwie dodatkowe ciekawe funkcje:
Rozpocznij liczenie od 5, pomnóż każdy element wynikowej listy przez 3 i wyświetl pierwsze dziesięć wartości:
Odnośnie polimorfizmu: Pomimo tego, że PostScript jest silnie pisany, pozwala na dowolne typy jako wartości słownikowe, dzięki czemu możesz wrzucić dowolne:
Pamiętaj, że błędy literowe, np. Podczas próby dodania ciągów do liczb, będą występować tylko w czasie oceny:
źródło
force
zapamiętuje zwrócone wartości?copy
operator kopiuje zawartość ocenionej wersji do oryginału, nadpisując/type
i ewentualnie ustawiając inne wartości. Po rekurencyjnie oceny dopóki mamynil
lubcons
, to również (przezundef
) usuwa/func
i, w stosownych przypadkach/data
. Ostatni krok nie jest absolutnie konieczny (/func
i/data
zostałby po prostu zignorowany), ale pozostawienie tego krokudo
Jestem całkowicie początkującym w C, ten kod jest właściwie pierwszą prawdziwą rzeczą, którą napisałem w C. Kompiluje się bez ostrzeżeń i działa dobrze w moim systemie.
Jak zbudować
Najpierw pobierz tarball z mojego serwera . Zawiera plik makefile, więc po prostu uruchom,
make
aby go zbudować, a następniemake run
uruchomić. Następnie program wypisuje listę pierwszych 93 liczb Fibonacciego. (Po numerze 94 przepełnia się 64-bitowa liczba całkowita bez znaku)Wyjaśnienie
Rdzeniem programów jest plik
lazy-list.c
. W odpowiednim pliku nagłówkowym definiuję structlist
, czyli naszą leniwą listę. To wygląda tak:Członek
kind
jest rodzajem tagu. Oznacza to, czy odwołaliśmy listę end (NIL
), komórkę, która jest już oceniana (CONS
), czy thunk (THUNK
). Potem następuje związek. To jestZawartość związku jest potwierdzana przez tag. Jeśli tag jest
NIL
, treść związku jest niezdefiniowana.Definiując funkcje pomocnicze wspomniane w powyższej specyfikacji, zwykle można wyodrębnić definicję listy z jej użycia, np. możesz po prostu zadzwonić,
nil()
aby uzyskać pustą listę zamiast tworzyć ją samodzielnie.Trzy najciekawsze funkcje to
zipWith
:take
ifibonaccis
. Ale nie chcę wyjaśniaćtake
, ponieważ jest bardzo podobny dozipWith
. Wszystkie działające leniwie funkcje mają trzy elementy:W przypadku
zipWith
, sązipWith
,__zipWith
i__zipArgs
. Pokazuję je tutaj bez dalszych wyjaśnień, funkcja powinna być całkiem jasna:Inną interesującą funkcją jest
fibonaccis()
. Problem polega na tym, że musimy przekazać wskaźnik pierwszej i drugiej komórki do nasadki trzeciej, ale aby utworzyć te komórki, potrzebujemy również wskaźnika do nasadki. Aby rozwiązać ten problem,NULL
najpierw wypełniłem wskaźnik do klocka i po utworzeniu zmieniłem go w klocek. Oto słuchanie:Możliwe ulepszenia
content_t
, który można zmienić na dowolny pasujący.źródło
void*
tego typucontent_t
.void*
, ale pomyślałem, że zbyt daleko posunęłoby się to do omijania systemu. Czy nie jest to możliwe przy użyciu szablonów?void*
i znajomych.kind
jest rodzajem tagu”. Możesz to nazwaćtag
, ponieważ jest to dość akceptowany termin na pojęcie (np. Tagged union , Spinless Tagless G-machine . Z drugiej strony, „kind” ma inne znaczenie w . kontekst Haskell: typ typuInt
ma miły*
,[]
ma rodzaj* -> *
i(,)
ma miły* -> * -> *
.C ++
To największa rzecz, jaką kiedykolwiek napisałem w C ++. Zwykle używam Objective-C.
Jest polimorficzny, ale nigdy niczego nie uwalnia.
Moja
main
funkcja (iadd
funkcja doZipWith
) wyglądała tak:To daje
Klasy działają w następujący sposób:
Pełne źródło: tutaj . To bałagan, głównie dlatego, że jest w jednym dużym pliku.
Edycja: zmieniono link (stary nie żył).
źródło
()
operatora) i używanie dziedziczenia, aby uniknąć konieczności używaniavoid*
. Zobacz tutaj trywialny przykład takiego działania.Pyton
Nie używa generatorów do implementacji listy, tylko do implementacji
__iter__
metody do użycia zfor
.Lista Fibonacciego jest tworzona w następujący sposób:
źródło
self.__class__ = node.__class__
. Zauważ, że trafia to w NotImplemented wyjątek, gdy osiąga 2971215073 (długi), co jest najwyraźniej niepoprawnym argumentem dla int .__ add__. Aby wesprzeć duże liczby całkowite, wykonajfib.append(fib.zip_with(lambda a,b: a+b, fib.tail()))
Rubin
Mój pierwszy program Ruby. Wszystkie węzły reprezentujemy jako tablice, których długość określa typ tablicy:
Kod jest więc dość prosty, z hackem, aby zresetować funkcję thunk, aby skonfigurować rekurencyjne fib.
źródło
[...]
zamiastArray[...]
.Google Go
Względnie nowy język i nauczyłem się go,
CTRL+F
wprowadzając Spec .Problem został rozwiązany, radząc sobie z thunk-in-a-thunks. Wydaje się jednak, że kompilator online nie może przyjąć 40 elementów, być może z powodu pamięci. Później przetestuję to na moim systemie Linux.
Przetestowałem kod za pomocą kompilatora online , ponieważ nie mogę łatwo zainstalować Go w systemie Windows.
źródło
iota
generator stały. Zobacz przykład w specyfikacji języka programowania Go i odpowiedź na temat StackOverflow .Fibs
funkcja nie działa, ponieważ Go używa ścisłej oceny iFibs
powtarza się bez warunku zakończenia.Fibs0
/Fibs1
używa prostego podejścia generatora zamiast algorytmu opisanego w moim poście, więc nie spełnia on „wymagań”. Zaktualizowałem swój post, aby rozwinąć leniwą rekurencję, która jest konieczna do wdrożeniafibs = 0 : 1 : zipWith (+) fibs (tail fibs)
.Cons(0, Cons(1, ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs)))))
, traci pamięćCons(0, Cons(1, Thunk(func() List { return ZipWith(Plus, Thunk(Fibs), Thunk(func() List { return Tail(Fibs()) })) })))
i pojawia się błąd nieprawidłowego adresu pamięciKryształ
Pomimo przestrzegania repozytorium GitHub, do tej pory nigdy nie korzystałem z Crystal. Crystal to statycznie wpisany wariant Ruby z pełnym wnioskowaniem typu. Mimo że istnieje już odpowiedź Ruby, statyczne pisanie Crystal doprowadziło mnie do użycia polimorfizmu zamiast tablicy do reprezentowania węzłów. Ponieważ Crystal nie zezwala na modyfikację
self
, stworzyłem klasę otoki o nazwieNode
, która owinąłaby wszystko inne i zarządzałaby zespołami.Wraz z klas I stworzył funkcji konstruktora
lnil
,cons
orazthunk
. Nigdy wcześniej nie używałem Ruby do więcej niż 20-liniowego skryptu, więc blokowanie mnie trochę odrzuciło.Oparłem tę
fib
funkcję na odpowiedzi Go .źródło
Wygiąłem trochę reguły, ponieważ nie ma tu jeszcze rozwiązania .NET - lub bardziej ogólnie rozwiązania OOP, z wyjątkiem rozwiązania w Pythonie, które korzysta z dziedziczenia, ale jest wystarczająco różne od mojego rozwiązania, aby uczynić oba interesującymi (w szczególności od Pythona pozwala modyfikować
self
instancję, dzięki czemu implementacja Thunk jest prosta).To jest C # . Pełne ujawnienie: nie jestem nigdzie w pobliżu początkującego w C #, ale od jakiegoś czasu nie dotknąłem tego języka, ponieważ w tej chwili nie mam z niego pożytku w pracy.
Istotne punkty:
Wszystkie klasy (
Nil
,Cons
,Thunk
) wywodzą się od wspólnego abstrakcyjnej klasy bazowejList
.Thunk
Klasa używa Koperta-literowy wzór. Zasadniczo emuluje toself.__class__ = node.__class__
przypisanie w źródle Pythona, ponieważthis
odwołania nie można modyfikować w języku C #.IsEmpty
,Head
ITail
mają właściwości.Wszystkie odpowiednie funkcje są zaimplementowane rekurencyjnie i leniwie (z wyjątkiem tych
Print
, które nie mogą być leniwe) przez zwracanie części. Na przykład jest toNil<T>.ZipWith
:… A to jest
Cons<T>.ZipWith
:Niestety, C # nie ma wielu wysyłek, w przeciwnym razie mógłbym również pozbyć się
if
instrukcji. Niestety, nie ma kości.Teraz nie jestem naprawdę zadowolony z mojej implementacji. Do tej pory jestem szczęśliwy, ponieważ wszystkie powyższe są całkowicie proste. Ale … Wydaje mi się, że definicja
Fib
jest niepotrzebnie skomplikowana, ponieważ muszę zawrzeć argumenty w gromady, aby działało:(Tutaj
List.Cons
,List.Thunk
iList.ZipWith
są obwolut wygody.)Chciałbym zrozumieć, dlaczego następująca znacznie łatwiejsza definicja nie działa:
Concat
oczywiście z odpowiednią definicją . Jest to w zasadzie to, co robi kod Pythona - ale nie działa (= rzucanie pasowaniem)./ EDIT: Joey zwrócił uwagę na oczywistą wadę tego rozwiązania. Jednak zamiana drugiej linii na thunk również powoduje błąd (Mono segfaults; Podejrzewam przepełnienie stosu, którego Mono nie radzi sobie dobrze):
Pełny kod źródłowy można znaleźć w GitHub jako gist .
źródło
fib.ZipWith
ifib.Tail
używaj staregofib
, który pozostaje[0,1]
i nie zmienia się. Tak więc dostajesz[0,1,1]
(tak myślę), a twojaTake
funkcja nie pozwala ci brać od zera (jednak przyjmuje Haskell ). Spróbuj zawinąć wartość drugiego wiersza w grube, aby odnosiła się do nowej,fib
a nie starej.Pico
dla przypomnienia , w tym rozwiązaniu zastosowano translację siły opóźnienia schematu zdefiniowanej w srfi-45 . i na tym buduje leniwe listy.
wygląd wyjściowe tak: (ale w zależności od sposobu
tpico
, jest połatany może mieć więcej cudzysłowów w nimdisplay
. normalnie drukuje łańcuchy z cytatami czyli wszystkie występy[
,,
,]
musiałby cudzysłowy wokół nich niczym"["
).ze względu na ograniczenia typu danych liczb całkowitych w tpico nie udaje się to przy obliczeniu 45. (lub 46. przesunięcia) liczby Fibonacciego.
Zauważ, że tpico 2.0pl11 jest zepsuty w tym
begin(a,b)
(co zwykle jest pisane jako{a;b}
), aif
funkcja nie jest rekurencyjna. nie wspominając o tym, że zajęło mi 5 lat, aby dowiedzieć się, dlaczegobegin
nie był rekurencyjny. również w tym czasie napisałem tłumaczenie srfi-45 w Pico. okazało się, żebegin
czekało na wartośćb
przed powrotem, gdy nie musiało czekać. a kiedy już to dostałem, byłem w stanie to naprawić,if
ponieważ miał ten sam problem. był też inny błąd, który spowodował, że konstruktor meta-poziomumake
nie działał.Pico pozwala funkcji kontrolować, czy jej argumenty są sprawdzane, zanim funkcja zostanie wywołana lub po prostu spakowana jako thunks. w przypadku tego kodu mogę wymyślić wielokropek wywołania według funkcji .
Pico nie ma wnioskowania o typie. zastanawiałem się przez chwilę, ale natknąłem się na problem z powodu osobliwości wywołania według funkcji . wpadłem na stwierdzenie, że typy muszą kodować istnienie powiązanych nazw zmiennych . ale myślałem głównie o tym, jak dostosować wnioskowanie typu Hindleya-Milnera do podzbioru Pico bez mutacji. główną ideą było to, że moduł sprawdzania typu zwraca wiele możliwych schematów, jeśli istnieje więcej niż jedno możliwe powiązanie, a sprawdzanie typu kończy się powodzeniem, jeśli istnieje co najmniej jeden możliwy schemat typów . możliwym schematem jest taki, który nie powoduje konfliktu przypisania typu.
źródło