Wie überprüfe ich eine Liste in Haskell?

Question

Dies ist mein Code:

module Main where 

import Data.Graph.Inductive 
import Data.Graph.Inductive.Example 

func :: Graph gr=> gr a b ->[Node]->Int-> [(Node,Int)] 
func graph (x:xs) y 
     |indeg graph x == 0 = (x,y+1):func (delNode x graph) xs (y+1) 

graph2:: Gr Int Int 
graph2 = mkGraph (genLNodes 1 14)[(1,2,1), 
       (1,3,1),  
       (3,14,1), 
       (14,6,1), 
       (14,7,1), 
       (2,4,1), 
       (2,5,1), 
       (4,6,1), 
       (5,7,1), 
       (6,8,1), 
       (7,9,1), 
       (8,10,1), 
       (9,11,1), 
       (10,12,1), 
       (11,12,1), 
       (12,13,1), 
       (14,13,1)] 

Graph2 hat 14 Knoten und eg (1,2,1) bedeutet, Kante von Knoten 1 zu Knoten 2 mit einem Gewicht von 1

Func my Graph2 nimmt , topologische Sortierung Vertices und einige Zahl zB 0. Func prüft, ob nach innen gebundene Grad des Knotens gleich 0 ist und erstellt eine Liste von Tupel, wo x ist IdNode und y steigt, wenn Indeg Graph x == 0 ist wahr. Der Scheitelpunkt ist

entfernt und hier ist mein Problem, ich möchte sehen, ob mehr Eckpunkten einen Grad von 0 hat und fügen 1.

EDIT:

Die Funktion wie folgt handeln sollte:

TOPSORT: [1,3,14,2,5,7,9,11,4,6,8,10,12,13]

1. check in gebundenen Grad für jeden Knoten in der Liste.
2. Wenn der Grad gleich 0 ist, addiere 1 zur Pfadlänge (Knoten 1 ist gleich 0, also Pfadlänge = 1)
3. Knoten aus Graph entfernen und eingehend gebundenen Knoten nach dem Entfernen Knoten und Rückkehr zu 2. Schritt

fort Beispiel:

nach 1-Knoten zu entfernen, die Knoten 2 und 3 haben in-bound = 0 so I 1 bis Weglänge hinzuzufügen (path Länge = 2 für den Knoten 2 und 3) und Ich entferne Knoten 2 und 3.

Nun in Grad = 0 haben 14,4,5 so ich füge 1 zu Pfad Leng hinzu th (Pfadlänge = 3) und ich entferne diese Knoten und so weiter

Ich hoffe, dass das Bild des Diagramms hilft.

Answer 1

Mit lazy evaluation Sie die "tie-the-Knoten" Methode verwenden, können Sie die Tiefen berechnen sehr deklarativ:

minOr0 [] = 0 
minOr0 ds = minimum ds 

depths :: Graph gr => gr a b -> [(Node, Int)] 
depths gr = 
    let pairs = [ (x, depth x) | x <- nodes gr ] 
     depth x = 1 + minOr0 [ d | y <- pre gr x, let Just d = lookup y pairs ] 
    in pairs 

test2 = depths graph2 

Die Definition zwischen pairs und depth kreisförmig ist: ein Tupel in pairs Anrufe Auswertung depth. Rufen Sie depth auf, suchen Sie nach anderen Tupeln in pairs. Wenn der Graph keine Zyklen hat, wird der Prozess schließlich beenden.

Aufgrund der Art, wie Lazy-Evaluierung in Haskell funktioniert, sind die Aufrufe an depth effektiv protokolliert.