Haskell, definisce una lista infinita, aggiunge dati al volo e ordina allo stesso tempo. Come?

devo definire un elenco in cui:Haskell, definisce una lista infinita, aggiunge dati al volo e ordina allo stesso tempo. Come?

1 è un membro
se n è un membro, quindi sono 2n + 1 e 3n + 1

Così la lista è infinita e deve essere ordinato. Una volta caricato a GHCi, il comando:

"take 10 theList"

produrrà:

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

Qui di seguito sono i miei codici:

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

Sembra funzionare, tranne per ciò che non è ordinato, il lo stesso comando come sopra produce:

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

Qualcuno ha qualche idea per risolverlo? Grazie

fonte

2012-03-30 カオナシ

La funzione 'allInOne' è precisamente [' concat'] (http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:concat). Haskell ha molte funzioni "built-in" che puoi cercare per tipo di firma usando [Hoogle] (http://www.haskell.org/hoogle/) (è uno degli strumenti che rende Haskell incredibile!), Ad es. 'allInOne' ha tipo' [[a]] -> [a] 'e [il primo risultato] (http: //www.haskell.org/hoogle/? hoogle = \ [\ [a \] \] + - % 3E + \ [a \]) è quello che stai cercando. :) – huon

C'è una bella implementazione naturale che coinvolge _corecursion_. In un certo senso assomiglia alla lista infinita di numeri di Fibonacci: 'fibs = 0: 1: zipWith (+) fibs (fib di coda)'. Come estenderesti la lista quando hai già "la lista" di una certa dimensione? – Vitus

Il problema può essere anche se, come un albero binario infinito (A e B sono etichette per i rami):

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

Pensando in questo modo, possiamo vedere che vogliamo scrivere un funzione ("listify") che converte la "struttura" in una lista ordinata. Qui è dove Haskell è veramente bello: se abbiamo una funzione (merge) che prende due (infiniti) elenchi ordinati e li unisce in un elenco ordinato (dovresti scrivere questa funzione), quindi listify -ing l'albero è semplicemente listify -ing i due rami, fondendole e mettendo la radice alla partenza, cioè nell'albero sopra

1:merge (listify A) (listify B)

Trattandosi compiti non dico più, ma qualsiasi ramo dell'albero è interamente determinato dalla radice nodo, quindi la firma del tipo di listify può essere Integer -> [Integer]. E una volta che hai listify, quindi theList = listify 1.

fonte

2012-03-30 07:09:32 huon

Grazie. Ho appena provato, ma dal momento che gli elenchi non sono ordinati non c'è modo di unirli o ordinarli. Se avesse funzionato, avrei dovuto solo mettere un'altra funzione 'sort' davanti alla definizione dell'elenco. Il fatto è che, se l'ho fatto, e ho provato 'prendi 20 theList' Haskell si bloccherebbe (il che significa che non è tornato al comando' Main> '. Credo di dover creare l'elenco al volo e ordinarlo non appena viene inserito un nuovo elemento. L'unico modo che posso pensare è: theList = [x | x <- [1 ..], soddisfare x] dove soddisfare x ..... Ma sono bloccato nel locale 'satisfare ' definizione. –

Gli elenchi * sono * ordinati se hai scritto 'listify' e' merge' correttamente (questo non è molto utile, lo so). Probabilmente Haskell si blocca perché stai creando un ciclo infinito (forse "' listify n' "appare sul lato destro della definizione di' listify n'? O simile in 'merge'?). – huon

Il problema con questo è che i duplicati vengono trattati solo nella fase di unione, non durante la generazione, che, nel tempo, causa un sacco di lavoro non necessario. Tuttavia crea una definizione molto concisa e dichiarativa. –

Un altro modo di vedere questo è come un elenco filtrato di numeri interi. Il numero n fa parte della sequenza se n = 1 (mod 2) e (n-1)/2 è una parte della sequenza, o se n = 1 (mod 3) e (n-1)/3 è un parte della sequenza.

fonte

2012-03-30 07:28:25 Joni

Grazie per la risposta, ma non funzionerà con i numeri interi, come (6 - 1) 'mod' 3 = 1, ma 6 non dovrebbe essere nella lista come puoi vedere nella mia domanda. C'è un grosso problema di arrotondamento qui. –

@crazyfffan, penso che funzioni: 6/= 1 (mod 3), quindi non è nemmeno considerato dalla divisione. ('mod' e' div' sono diverse funzioni) – huon

Haskell, definisce una lista infinita, aggiunge dati al volo e ordina allo stesso tempo. Come?

risposta

Problemi correlati