Iterieren eine Funktion und das Ergebnis in Haskell

Question

Ok Analyse, unter Rückgriff auf meine previous question, ich noch arbeiten an Haskell zu lernen und das derzeitige Problem der Suche nach der längsten Kette aus der folgenden Iteration zu lösen:

chain n | n == 0  = error "What are you on about?" 
     | n == 1  = [1] 
     | rem n 2 == 0 = n : chain (n `div` 2) 
     | otherwise = n : chain (3 * n + 1) 

Ich habe Dieses Bit ist sortiert, aber ich muss die längste Kette von einer Startnummer unter 1.000.000 finden. Also wie mache ich es so, dass jede Startnummer bis zu 1.000.000 und dann diejenige mit der längsten Kettenlänge gedruckt wird. Ich kann es mit für ein Beispiel tun:

Main> length (chain n) 

Ich nehme ich die Ausgabe als Array benötigen und dann die maximum Funktion den Wert größte Kettenlänge zu finden und dann sehen, wie weit sie in dem Array von Antworten.

Ist dies ein guter Weg, um eine Lösung zu finden, oder gibt es einen besseren Weg (vielleicht mit besserer Effizienz)?

Answer 1

Sie haben Recht über den maximum Teil. Um die Liste (das ist, was Haskells [] s sind, Arrays unterschiedliche Strukturen sind) können Sie die map Funktion höherer Ordnung verwenden müssen, wie folgt aus:

chainLength n = length (chain n) 

lengths = map chainLength [1..1000000] 

Im Wesentlichen map nimmt als Argumente eine Funktion und eine Liste. Sie wendet die Funktion auf jedes Element in der Liste an und gibt die Liste der Ergebnisse zurück.

Da Sie die Zahl, deren Kette hat, dass die Länge benötigen werden, können Sie die chainLength Funktion ändern möchten, die Anzahl als auch zurück, wie folgt aus:

chainLength n = (n, length (chain n)) 

diese Weise werden Sie eine Reihe von Paaren haben mit jeder Nummer und ihrer Kettenlänge.

Jetzt müssen Sie das Paar mit der größten zweiten Komponente erhalten. Das ist, wo die maximumBy Funktion hereinkommt. Es funktioniert genau wie maximum, aber nimmt eine Funktion als ein Parameter, um zu wählen, wie man die Werte vergleicht. In diesem Fall ist die zweite Komponente des Paares. Diese Vergleichsfunktion nimmt zwei Zahlen und gibt einen Wert vom Typ Ordering zurück. Dieser Typ hat nur drei mögliche Werte: LT, EQ, GT, für weniger als, gleich und größer als jeweils.

Wir brauchen also eine Funktion, die zwei Paare gegeben sagt uns, wie die zweiten Komponenten miteinander vergleichen:

compareSnd (_, y1) (_, y2) = compare y1 y2 
-- Or, if you import Data.Function, you can write it like this (thanks alexey_r): 
compareSnd = compare `on` snd     -- reads nicely 

ich die Standard-compare Funktion verwendet, die Zahlen vergleicht (na ja, not just numbers).

Jetzt brauchen wir nur die maximal mit dieser Funktion zu erhalten:

longestChain = maximumBy compareSnd lengths 

dass Sie ein Paar der Zahl mit der längsten Kette und der entsprechenden Länge bekommt. Fühlen Sie sich frei, und snd wie Sie bitte anwenden.

Beachten Sie, dass dies mit Hilfe von zip und Komposition viel präziser sein könnte, aber da Sie die Frage als Neuling markiert haben, dachte ich, es wäre besser, es so zu zerlegen.

Answer 2

So etwas wie

fst $ maximumBy (length . snd) $ zip [1..1000000] $ map chain [1..1000000] 

(ungetestet)

also nicht funktionieren, wie weit entlang der längste Kette in der Liste der längsten Ketten, sondern um die Seed-Werte mit den Ketten trägt statt .

Answer 3

SPOILER (das Problems für positive ganze Zahlen unter 100 Lösung):

module Test where 
import Data.List -- this contains maximumBy 

chain n 
     | n == 0  = error "What are you on about?" 
     | n == 1  = [1] 
     | rem n 2 == 0 = n : chain (n `div` 2) 
     | otherwise = n : chain (3 * n + 1) 

chains = map (\x -> (x,chain x)) [1..100] 

cmpSnd (a,b) (c,d) 
     | length b > length d  = GT 
     | length b == length d = EQ 
     | otherwise    = LT 

solve = (fst . maximumBy cmpSnd) chains 

Die Ketten-Funktion macht die Kartennutzung. Es wendet eine Funktion auf jedes Element einer Liste eines Wertes, so

map succ [1,2] 

ist die gleiche wie

[succ 1,succ 2] 

Die cmpSnd Funktion ist eine Vergleichsfunktion, die wahrscheinlich irgendwo tief in den Hierarchical Libraries existiert, aber Ich konnte es nicht finden, also habe ich es geschaffen. GT bedeutet "der erste Wert ist größer als der zweite", der Rest ist trivial.

Lösung verwendet das Maximum (unter Verwendung der zuvor definierten Vergleichsfunktion) der Liste. Dies wird ein Paar einer ganzen Zahl und einer Liste sein. Es gibt nur die ganze Zahl zurück (wegen der fst).

Ein Kommentar: Ihre Kettenfunktion ist nicht tail-rekursiv. Dies bedeutet, dass große Ketten unweigerlich zu einem Stapelüberlauf führen. Sie müssen eine explizite Akkumulatorvariable hinzufügen und sie tailrekursiv machen.

Answer 4

Ich habe Haskell vor Jahren studiert, also erinnere ich mich nicht so gut daran. Auf der anderen Seite habe ich diesen Code getestet und es funktioniert. Sie erhalten die maximale Kette und die Zahl, die sie erzeugt. Aber wie Fiships schon gesagt hat, wird es für große Werte überlaufen.

chain :: Int -> [Int] 
chain n 
    | n == 0 = [] 
    | n == 1 = [1] 
    | rem n 2 == 0 = n : chain (n `div` 2) 
    | otherwise = n : chain (3 * n + 1) 

length_chain :: Int -> Int 
length_chain n = length (chain n) 

max_pos :: (Int,Int) -> Int -> [Int] -> (Int,Int) 
max_pos (m,p) _ [] = (m,p) 
max_pos (m,p) a (x:xs) 
    | x > m = max_pos (x,a) (a+1) xs 
    | otherwise = max_pos (m,p) (a+1) xs 

Die Anweisung wird

Main> max_pos (0,0) 1 (map length_chain [1..10000]) 
(262,6171)