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

В соответствии с названием.

У меня есть следующий код, который создает двоичное дерево поиска, но если я хочу, чтобы он был создан и динамически изменен с использованием пользовательского ввода, как бы это сделать, если я не могу изменить значение переменной в 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)

Спасибо заранее!

Ответы

Ответ 1

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

Итак, заданная функция

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

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

Ответ 2

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

Ответ 3

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

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

Итак,

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

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

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

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