Haskell, zdefiniuj nieskończoną listę, dodaj dane w locie i sortuj w tym samym czasie. W jaki sposób?

trzeba utworzyć listę, w którym:Haskell, zdefiniuj nieskończoną listę, dodaj dane w locie i sortuj w tym samym czasie. W jaki sposób?

1 jest członkiem
jeśli n jest członkiem tak 2n + 1 3n + 1

więc lista jest nieskończona i muszą być posortowane. Po załadowaniu do GHCi, poleceniem:

"take 10 theList"

będzie produkować:

[1,3,4,7,9,10,13,15,19,21]

Poniżej są moje kody:

theList = ([1] ++ concat [[(x*2+1),(x*3+1)]|x<-theList])

wydaje się działać z wyjątkiem, że to nie jest posortowana, to samo polecenie co powyżej powoduje:

[1,3,4,7,10,9,13,15,22,21]

Czy ktoś ma jakiś pomysł, aby to rozwiązać? Dzięki

Źródło

2012-03-30 カオナシ

Twoja funkcja 'allInOne' to właśnie [' concat'] (http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:concat). Haskell ma wiele funkcji "wbudowanych", które można wyszukiwać według podpisu typu za pomocą [Hoogle] (http://www.haskell.org/hoogle/) (jest to jedno z narzędzi, dzięki którym Haskell jest niesamowity!), Np. 'allInOne' ma typ' [[a]] -> [a] 'i [pierwszy wynik] (http: //www.haskell.org/hoogle/? hoogle = \ [\ [a \] \] + - % 3E + \ [a \]) jest tym, którego szukasz. :) – huon

Istnieje ładne naturalne wdrożenie obejmujące _corecursion_. W pewnym sensie przypomina nieskończoną listę liczb Fibonacciego: 'fibs = 0: 1: zipWith (+) fibs (tail fibs)'. W jaki sposób rozszerzyłbyś listę, gdy masz już 'theList' o pewnym rozmiarze? – Vitus

Problemem może być choć jako nieskończonego drzewa binarnego (A i B są etykiety do gałęzi):

1__ B 
    | 4___ 
    | \ 13 ... 
A 3_ \ 
    | \ 9 ... 
    7 10 
    ...

Z myślą o tym w ten sposób, możemy zobaczyć, że chcemy napisać funkcja ("listify"), która konwertuje "drzewo" na posortowaną listę. Tutaj Haskell jest naprawdę niezły: jeśli mamy funkcję (merge), która zajmuje dwie (nieskończone) posortowane listy i łączy je w jedną posortowaną listę (należy napisać tę funkcję), a następnie listify - na drzewie jest po prostu listify -ing dwie gałęzie, łącząc je i oddanie korzeń na początku, czyli w drzewie powyżej

1:merge (listify A) (listify B)

Ponieważ jest to praca domowa nie powiem dużo więcej, ale każda gałąź drzewa jest całkowicie określona przez korzeń węzeł, więc sygnatura typu listify może być Integer -> [Integer]. A kiedy już masz listify, to theList = listify 1.

Źródło

2012-03-30 07:09:32 huon

Dziękuję. Właśnie próbowałem, ale ponieważ listy nie są sortowane, nie ma możliwości ich scalenia lub sortowania. Gdyby to zadziałało, musiałbym tylko wstawić inną funkcję "sortowania" przed definicją listy. Chodzi o to, że gdybym to zrobił, i spróbowałem 'wziąć 20 TheList' Haskell miałby awarię (co oznacza, że nie powrócił do polecenia' Main> '. Chyba muszę utworzyć listę w locie i sortować ją, gdy tylko zostanie w nią wstawiony nowy element. Jedyny sposób, jaki mogę wymyślić to: theList = [x | x <- [1 ..], spełniają x] gdzie spełniają x ..... Ale utknąłem w "zaspokoić" lokalnych definicja. –

Listy * są * posortowane, jeśli poprawnie wpisałeś 'listify' i' merge' (to niezbyt pomocne, wiem). Haskell prawdopodobnie zawiesza się, ponieważ tworzysz nieskończoną pętlę (może "' listify n' "pojawia się po prawej stronie definicji' listify n'? Lub podobnej w 'merge'?). – huon

Problem polega na tym, że duplikaty są przetwarzane tylko na etapie scalania, a nie podczas generowania, co z czasem powoduje dużo niepotrzebnej pracy. Tworzy jednak bardzo zwięzłą, deklaratywną definicję. –

Innym sposobem zobaczenia tego jest filtrowana lista liczb całkowitych. Liczba n jest częścią sekwencji, jeśli n = 1 (mod 2) i (n-1)/2 jest częścią sekwencji, lub jeśli n = 1 (mod 3) i (n-1)/3 jest część sekwencji.

Źródło

2012-03-30 07:28:25 Joni

Dziękuję za odpowiedź, ale nie będzie działać z liczbami całkowitymi, jak (6 - 1) 'mod' 3 = 1, ale 6 nie powinno znajdować się na liście jak widać na moim pytaniu. Istnieje tutaj duży problem z zaokrąglaniem. –

@crazyfffan, myślę, że to działa: 6/= 1 (mod 3), więc nie jest nawet brany pod uwagę przez podział. ('mod' i' div' są różnymi funkcjami) – huon

Haskell, zdefiniuj nieskończoną listę, dodaj dane w locie i sortuj w tym samym czasie. W jaki sposób?

Odpowiedz

Powiązane problemy