Haskell树与功能分支

Question

我首先要说的是我对Haskell很新,所以我还没有学过像Monads这样的东西.

在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.请注意,由于Maybemonad实例,我们不必进行任何类型的显式错误处理!如果函数映射的任何查找返回Nothing,则整个计算返回,Nothing而我们不必考虑它.