Wenn Sie den Wert einer Variablen in Haskell nicht ändern können, wie erstellen Sie Datenstrukturen?

Question

Wie der Titel.

Ich habe den folgenden Code, der einen binären Suchbaum erstellt, aber wenn ich möchte, dass er dynamisch mit Benutzereingabe erstellt und geändert wird, wie würde ich das tun, wenn ich den Wert einer Variablen in haskell nicht ändern kann?!?

find :: (Ord a) => Node a -> a -> Bool 
find (Node val left right) s 
    | s == val  = True 
    | s < val  = find left s 
    | s > val  = find right s 

find Empty s = False 

data Node a = Node a (Node a) (Node a) 
       | Empty 

myTree = Node "m" (Node "a" Empty Empty) 
        (Node "z" Empty Empty) 

Vielen Dank im Voraus!

Answer 1

Die Idee hinter rein funktionalen Datenstrukturen besteht darin, neue Werte zu berechnen, anstatt sie zu ändern und sie (rekursiv) in Parametern zu übergeben, anstatt sie global zu speichern.

So eine Funktion gegeben

insert :: Ord a => Node a -> a -> Node a 

Ihr Programm wie diese Funktionen

-- Let the user enter k values that are stored in a tree structure 
addTreeItems :: Int -> Node Int -> IO (Node Int) 
addTreeItems 0 tree = return tree 
addTreeItems k tree = do 
    putStr "Enter new item: " 
    item <- readLn 
    addTreeItems (k - 1) (insert tree item) -- Recursively pass the tree 

main = do 
    tree <- addTreeItems 10 Empty 
    -- ... 

Mit monadischen Helfer aussehen könnte, dies Dinge vereinfacht werden könnte wie

(foldl insert Empty) `liftM` (sequence $ replicate k (putStr "Enter new item: " >> readLn)) 

Wenn Sie möchten, Um Werte an einer bestimmten Position zu aktualisieren, benötigen Sie erweiterte Datenstrukturen wie zipper, die sind doch noch rein funktional!

Answer 2

Dario gab eine gute direkte Antwort. Wenn Sie mehr detaillierte Informationen wünschen, gibt es Purely Functional Data Structures von Chris Okasaki, ein ganzes Buch zu diesem Thema. Ich habe es selbst gekauft, aber leider habe ich keine Zeit, mit den Ideen zu experimentieren.

Answer 3

Sie ordnen einen neuen Baumknoten zu und der alte bleibt stehen. Diese Technik erfordert einen wirklich guten Allokator, aber sie ermöglicht alle Arten von intelligenten Geräten, weil andere Teile des Programms weiterhin Zugriff auf alte Knoten haben. Dies ist ein Glücksfall für bestimmte Arten von spekulativen Algorithmen oder andere Tricks mit sogenannten "persistenten Datenstrukturen".

Schließlich ordnen Sie eine neue Wurzel für Ihren Baum und was dann? Wie Dario sagt, übergeben Sie ihn als Parameter an eine Funktion (anstatt sie in einer globalen Variablen zu speichern).

So

• Mutation eines Feldes in einer Struktur auf dem Heap zugewiesen wird Zuweisung einer neuen Struktur auf dem Heap.

• Mutation einer globalen Variablen

Manchmal auch ein Parameter einer Funktion wird vorbei macht es Sinn, zu nehmen, was eine Sammlung von globalen Variablen in C gewesen wäre und zugeteilt, sie alle in einem Objekt setzen auf dem Haufen.

---

P.S. Wenn Sie wirklich wollen, können Sie änderbare globale Variablen in Haskell haben. Es ist schließlich die beste imperative Programmiersprache der Welt (nach Wadler oder Peyton Jones, ich vergesse wen). Aber wenn Sie diese Frage stellen, wollen Sie wirklich nicht. Noch.