Drucken eines Ergebnisses während einer Rekursion in Haskell

Question

Ich beginne Haskell zu lernen und ein Programm mache den iterativen Prozess zu tun:

n -> n/2 (for even n) 
n -> 3n+1 (for odd n) 

Also habe ich so weit: `

chain n  | n == 0  = error "What are you on about?" 
      | n == 1  = error "Finished" 
      | rem n 2 == 0 = chain (n `div` 2) 
      | rem n 2 /= 0 = chain (3 * n + 1) 

` Funktioniert das? Aber es macht nur die Berechnungen hinter den Kulissen, gibt es eine Möglichkeit, es als Liste das Ergebnis für n auf jeder Iteration anzuzeigen oder zu exportieren, bis es 1 erreicht, so dass ich die Länge der Liste später finden kann?

Auf einer Seite zur Kenntnis, ist es eine Möglichkeit, GHCi in einem bestimmten Ordner zu machen beginnen? (Ich verwende Windows)

Answer 1

Man könnte es eine Liste der Ergebnisse in der „Kette“, wie diese zurückkehrt :

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

Jetzt werden Sie wie diese Ergebnisse zu erzielen:

*Main> chain 3 
[10,5,16,8,4,2,1] 
*Main> chain 7 
[22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] 

Answer 2

Ja, sicher. Es gibt sogar eine Funktion aus dem Data.List-Modul, die dieses Verwendungsmuster erfasst.

import Data.List (unfoldr) 

chain 0 = [] 
chain n = unfoldr f n 
    where 
    f 1 = Nothing 
    f n = let n' | even n = n `div` 2 
       | otherwise = 3 * n + 1 
      in Just (n', n') 

Die Art der unfoldr ist: (B -> Vielleicht (a, b)) -> B -> [a]

b ist die Zustandsvariable, die die Liste zu erzeugen, verwendet. Die Funktion, die als erstes Argument für unfoldr zur Verfügung gestellt wird, sollte entweder Nothing (dh die Liste beenden) oder Just (b, a) zurückgeben, wobei a das Element ist, das der Liste hinzugefügt werden soll, und b die neue Statusvariable ist.

Answer 3

Sie werden feststellen, dass die beiden früheren Antworten das Paradigma "Erstellen Sie die ganze Liste und geben Sie es am Ende" anstatt "ein Element auf einmal ausgeben" verwenden. Dies ist die funktionale Art, Dinge zu tun.

Wenn Sie es wirklich in einem imperativen Stil tun möchten, müssen Sie monadische Programmierung verwenden, die ein fortgeschrittenes Thema ist. Hier ist ein Beispiel (keine Sorge, wenn Sie nicht alles verstehen kann, die vor sich geht ... Monaden sind recht geheimnisvoll und magisch):

import Control.Monad.Writer 

chain :: Int -> (String, [Int]) 
chain = runWriter . chain' 
    where 
     chain' 0 = return "Failure" 

     chain' 1 = do 
     tell [1]   -- write 1 
     return "Success" -- finished 

     chain' n = do 
     -- write n 
     tell [n] 
     -- calculate next n and recurse 
     if even n 
      then chain' $ n `div` 2 
      else chain' $ 3 * n + 1 

Welche Ergebnisse wie gibt:

*Main> chain 3 
("Success",[3,10,5,16,8,4,2,1]) 

Aber, Wie Sie sehen können, generiert der Autor monad immer noch nur die Liste hinter den Kulissen.

Dies scheint ineffizient zu sein. Was, wenn Sie eine Liste von 1.000.000 Elementen drucken möchten? Müssen Sie wirklich die gesamte Liste im Voraus generieren? Tatsächlich bedeutet Haskells faule Semantik, dass Haskell, wann immer möglich, den Code "Erzeuge die ganze Sache im Voraus und dann druckt es aus" in den Code "erzeuge und gebe nur ein Element auf einmal aus" kompiliert.

Answer 4

Die Funktion sollte nur die Liste der gefundenen Elemente zurückgeben. Diese Liste kann später weiter untersucht werden:

chain 0 = error "No no no." 
chain 1 = [1] 
chain n 
    | rem n 2 == 0 = n : chain (n `div` 2) 
    | otherwise = n : chain (3 * n + 1) 

Hier [1] ist eine Liste mit nur 1 und : ist eine Liste Konstruktor, der das Element auf der linken Seite in die Liste auf der rechten Seite hinzufügt.

Die von chain konstruiert Liste kann dann mit anderen Funktionen angezeigt oder verwendet werden:

*Main> chain 5 
[5,16,8,4,2,1] 
*Main> length (chain 31) 
107 

Answer 5

ist es eine Möglichkeit, sie anzuzeigen oder zu exportieren als Liste das Ergebnis für n bei jeder Iteration zu machen, bis es erreicht 1

Sie können Debug.Trace.trace verwenden, um Protokollmeldungen als Ausgabe auszugeben, wenn Werte ausgewertet werden. Gut für schnelles Debuggen.