Unendliche Liste in Haskell kombiniert mit Falte * berechnet nicht

Question

Sagen wir, ich möchte eine sortierte unendliche Liste aller Primepower bis zum Exponenten n bekommen.

Ich habe eine Funktion, zwei sortierte Listen und eine Funktion, die mir Primzahlen gibt, zusammenzuführen.

merge :: Ord t => [t] -> [t] -> [t] 
merge (x:xs) (y:ys) 
    | (x <= y) = x : merge xs (y:ys) 
    | otherwise = y : merge (x:xs) ys 
merge xs [] = xs 
merge [] ys = ys 

primes :: [Integer] 
primes = sieve [2..] 
    where 
     sieve [] = [] 
     sieve (p:xs) = p : sieve (filter (\x -> x `mod` p /= 0) xs) 

Ich habe zwei Versionen der listOfPrimepowers Funktion:

primepowers :: Integer -> [Integer] 
primepowers n = foldr (merge) [] (listOfPrimepowers n)  

-- terminating 
listOfPrimepowers' n = map(\x -> (map(\y -> y^x) primes)) [1..n] 

-- non terminating  
listOfPrimepowers'' n = map(\x -> (map(\y -> x^y) [1..n])) primes 

One liefert das richtige Ergebnis und die andere nicht. Der einzige Unterschied besteht darin, dass die erste Version die Primepower auf eine Art wie [[2,3,5,7, ...],[4,9,25,...]] abbildet und die zweite Version die Primepower wie [[2,4,8],[3,9,27],[5,25,125], ...] abbildet. Sie sehen, die Unendlichkeit ist auf einer anderen Ebene in der Liste.

Haben Sie eine Erklärung, warum die 2. Funktion keine Ausgabe erzeugt?

Answer 1

Es wird von foldr merge verursacht wird, die alle Listen schauen durch das minimale Element zu finden an der Spitze einer der Listen. Wenn foldr merge eine unendliche Liste endlicher Listen erhält, kann foldr merge niemals das erste Element der Liste berechnen - es sucht weiter nach dem minimalen Element des Rests der Liste von Listen, bevor es es mit dem ersten Element des ersten vergleichen kann Liste - 2. Auf der anderen Seite, wenn foldr merge eine endliche Liste von unendlichen Listen gegeben wird, kann foldr merge das erste Element der zusammengeführten Liste bestimmen und geht zum nächsten über. Auf diese Weise können Sie im ersten Fall eine beliebige Anzahl von Elementen erzeugen, im zweiten Fall jedoch keine einzige.

---

Lasst uns foldr merge [] erweitern:

foldr merge [] (xs0:xs1:xs2:...:[]) = 
merge xs0 (merge xs1 (merge xs2 (merge xs3 ... []))) 

Klar, wenn (xs0:xs1:xs2:...:[]) unendlich ist, ruft die "verschachtelte" eine unendliche Kette zu verschmelzen bilden. Aber was ist mit Haskell "faul"? primes ist auch in Bezug auf sich selbst definiert, aber es produziert Ausgabe? Nun, es gibt tatsächlich eine Regel von foldr: es kann Ausgabe für unendliche Listen nur dann erzeugen, wenn die an foldr übergebene Funktion in ihrem zweiten Argument nicht streng ist - dh manchmal kann sie Ausgabe erzeugen, ohne das Ergebnis von foldr für den Rest auswerten zu müssen Die Liste.

Die merge Muster entspricht das zweite Argument - das allein kann nicht Abbruch führen - und verwendet eine strenge Funktion <=, so ist merge streng im zweiten Argumente, und die unendliche Kette wird das erste Element jeder bewerten hat Liste vor der obersten Ebene merge kann jedes Ergebnis produzieren.

Da merge ist streng, und weil merge assoziativ ist, können Sie - und sollten - verwenden foldl' statt foldr die endliche Liste der unendlichen Listen zu verschmelzen.

Answer 2

Weder Ihre Funktionen

Die erste Sache ist beendet, dass primes eine unendliche Liste. Das bedeutet, dass das Verständnis des Programms in seiner lazy evaluation wohnt

für die erste Funktion

primepowers :: Integer -> [Integer] 
primepowers n = foldr (merge) [] (listOfPrimepowers n)  

listOfPrimepowers n = map (\x -> (map (\y -> y^x) primes)) [1..n] 

wird nicht wegen beendet. Auch wenn die äußere Karte gilt für eine endliche Liste [1..n] jeder \x konsumieren durch die innere map gilt für eine unendliche Liste primes.

Die zweite Funktion

primepowers :: Integer -> [Integer] 
primepowers n = foldl (merge) [] (listOfPrimepowers n) 

listOfPrimepowers n = map(\x -> (map(\y -> x^y) [1..n])) primes 

nicht beendet werden, weil die äußere map auf eine unendliche Liste direkt anwenden wird primes

Answer 3

Die zweite Version gibt Ihnen keine Ausgabe, da die Eingabe eine unendliche Liste von Listen ist. Wenn Sie darüber nachdenken, erstellt foldr merge [] eine sortierte Liste aus einer Liste von Listen, daher ist das Kopfelement der resultierenden Liste das Minimum aller Kopfelemente der Listen. Natürlich ist das Minimum einer unendlichen Liste nicht terminierend, so dass die Funktion nicht einmal an den Punkt kommt, an dem das erste Element des Ergebnisses verfügbar wird.

Answer 4

Sie können beide Varianten ziemlich einfach arbeiten lassen. Die Technik ist wissenswert.

Ihr Code entspricht

primepowers n = 
    foldr merge [] 
     -- terminating: 
-- [[p^k | p <- primes] | k <- [1..n]] -- n infinite lists 

     -- non terminating: 
     [[p^k | k <- [1..n]] | p <- primes] -- infinite list of n-length lists 

"Naturally, taking the minimum of an infinite list is non-terminating" ist die Wahrheit und nur die Wahrheit, aber es ist nicht die ganze Wahrheit, hier.

Hier ist die unendliche Liste primesbereits sortiert in aufsteigender Reihenfolge seiner Elemente. So sind die Köpfe der Listen [p^k | k <- [1..n]] sortiert und steigend, und die Listen selbst sind sortiert und steigen auch. Basierend auf diesem Wissen allein, können wir sofort produzieren das Kopfelement der zusammengeführten Ströme — das Minimum der unendlichen Liste der Köpfe aller dieser Listen — in O (1) Zeit, ohne tatsächlich zu überprüfen alle von ihnen, außer dem allerersten (was die Antwort selbst ist).

imerge (x:xs) ys = x : merge xs ys 

(wie gesehen in den Code von Richard Bird in the article by Melissa O'Neill):

Ihr Problem wird durch Verwendung der folgenden Funktion anstelle von merge im foldr Ausdruck somit gelöst. Jetzt werden beide Varianten einfach funktionieren. imerge ist in seinem 2. Argument nicht strikt und wird natürlich mit foldr verwendet, sogar mit endlichen Listen.

foldl statt foldr ist einfach falsch mit der 2. Variante, weil foldl auf einer unendlichen Liste nicht terminiert ist. Wenn mit foldl mit der ersten Variante, obwohl möglich (da die Liste selbst ist endlich), ist hier suboptimal: es wird die am häufigsten produzierenden Ströme am unteren Ende der gesamten Kette von Zusammenführungen, dh es wird langsamer laufen als die mit foldr.

siehe auch: folds on wikipedia.