Haskell树与函数分支

Question

我首先要说的是，我对Haskell非常陌生，所以我还没有学习像monad这样的东西。

在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

所以我的问题是我可以在数据结构中有一个函数的输入(以及类型是什么?)

对不起，可能令人困惑的问题，但感谢任何建议!

Answer 1

我建议你这样写:

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

请注意，您将无法派生Eq或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实例，我们不需要进行任何类型的显式错误处理!如果对函数map的任何一次查找都返回Nothing，则整个计算都返回Nothing，而我们不必考虑它。