Блог

Я начну с того, что я новичок в Haskell, поэтому я еще не узнал о таких вещах, как монады.

В Haskell я пытаюсь создать тип дерева, листья которого имеют числа, а функции — ветви, чтобы все дерево могло действовать как калькулятор.

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

 data Tree3 = Leaf3 Int | Node3 Char Tree3 Tree3 deriving (Show)
-- I would like to replace this ^  Char somehow with a function.

evaluate :: Tree3 -> Int
evaluate (Leaf3 x) = x
evaluate (Node3 c m n) | c == ' '    = evaluate m   evaluate n
                       | c == '-'    = evaluate m - evaluate n
                       | c == '/'    = evaluate m `div` evaluate n
                       | c == '*'    = evaluate m * evaluate n
  

Итак, мой вопрос в том, могу ли я ввести функцию в структуру данных (и каков будет тип?)

Извините за, возможно, запутанный вопрос, но спасибо за любой совет!

Я бы рекомендовал написать ваше дерево как:

 data Tree = Leaf Int | Node (Int -> Int -> Int) Tree Tree
  

Обратите внимание, что вы не сможете вывести Eq or Show , поскольку Int -> Int не реализует ни один из этих классов типов (и это невозможно непрактично это делать).

Затем вы можете написать свою evaluate функцию как

 evaluate :: Tree -> Int
evaluate (Leaf x) = x
evaluate (Node f l r) = f (evaluate l) (evaluate r)
  

что намного проще!

Вы можете создать дерево для представления выражения типа (1 2) * (3 * 4) в виде

 expr :: Tree
expr = Node (*) (Node ( ) (Leaf 1) (Leaf 2)) (Node (*) (Leaf 3) (Leaf 4))
  

Другим способом, который упростил бы печать вашего дерева, было бы использование почти того же определения, которое у вас есть:

 data Tree = Leaf Int | Node String Tree Tree
--                          ^ String instead of Char
  

Затем, если вы Data.Map импортировали, вы можете создать карту функций для поиска, но это немного усложняет вашу evaluate функцию, поскольку вы вводите вероятность того, что вашей функции не будет на вашей карте. К счастью, в Haskell есть несколько действительно удобных инструментов для элегантной обработки этого!

 import qualified Data.Map as Map

type Tree = Leaf Int | Node String Tree Tree deriving (Eq, Show)

type FuncMap = Map.Map String (Int -> Int -> Int)

evaluate :: FuncMap -> Tree -> Maybe Tree
evaluate funcs (Leaf x) = return x
evaluate funcs (Node funcName left right) = do
    -- Use qualified import since there's a Prelude.lookup
    f <- Map.lookup funcName funcs
    l <- evaluate funcs left
    r <- evaluate funcs right
    return $ f l r
  

Это автоматически приведет к Nothing , если вы попробуете что-то вроде

 evaluate (Map.fromList [(" ", ( ))]) (Node "blah" (Leaf 1) (Leaf 2))
  

поскольку функции "blah" нет в вашем FuncMap . Обратите внимание, что нам не пришлось выполнять какую-либо явную обработку ошибок любого рода благодаря Maybe экземпляру monad! Если какой-либо из поисковых запросов к карте функций возвращает результат Nothing , возвращается все вычисление Nothing без необходимости думать об этом.