Если вы не можете изменить значение переменной в Haskell, как вы создаете структуры данных? - PullRequest
Новая
       14

Если вы не можете изменить значение переменной в Haskell, как вы создаете структуры данных?

12 голосов
/ 26 ноября 2009

Согласно названию.

У меня есть следующий код, который создает двоичное дерево поиска, но если я хочу, чтобы оно создавалось и изменялось динамически с пользовательским вводом, как мне это сделать, если я не могу изменить значение переменной в haskell?!? 

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)

Заранее спасибо!

Ответы [ 3 ]

12 голосов
/ 26 ноября 2009

Идея, лежащая в основе чисто функциональных структур данных, состоит в том, чтобы вычислять новые значения вместо их изменения и передавать их (рекурсивно) в параметрах вместо их глобального хранения.

Итак, с учетом функции 

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

ваша программа может выглядеть так 

-- 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
    -- ...

Используя монадические вспомогательные функции, это можно упростить до таких вещей, как 

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

Если вы хотите обновить значения в определенной позиции, вам понадобятся более сложные структуры данных, такие как застежка-молния , которые, тем не менее, все еще чисто функциональны!

6 голосов
/ 26 ноября 2009

Дарио дал хороший прямой ответ. Если вам нужна более подробная информация, есть Чисто функциональные структуры данных Криса Окасаки, целая книга на эту тему. Я купил его сам, но, к сожалению, у меня нет времени экспериментировать с идеями.

2 голосов
/ 27 ноября 2009

Вы выделяете новый узел дерева, а старый остается. Этот метод требует действительно хорошего распределителя, но он включает все виды отличных устройств, потому что другие части программы все еще имеют доступ к старым узлам. Это находка для некоторых видов спекулятивных алгоритмов или других уловок, связанных с так называемыми «постоянными структурами данных».

В конце концов вы выделяете новый корень для своего дерева, и что тогда? Как говорит Дарио, вы передаете его в качестве параметра функции (вместо того, чтобы хранить его в глобальной переменной).

So

  • Мутация поля в структуре, выделенной в куче, становится выделением новой структуры в куче.

  • Мутация глобальной переменной становится передачей параметра в функцию

Иногда также имеет смысл взять то, что было бы набором глобальных переменных в C, и поместить их все в объект, расположенный в куче.

P.S. Если вы действительно хотите, вы можете иметь изменяемые глобальные переменные в Haskell. В конце концов, это самый лучший в мире императивный язык программирования (по словам Уодлера или Пейтона Джонса, я забыл кого). Но если вы задаете этот вопрос, вы действительно не хотите. Тем не менее.

...