haskell，数据树函数，字符串输出？

Question

我创建了一个数据类型树和一个数据类型 Op，现在我想创建一个函数来生成一个带有操作的字符串：

首先是我的代码：

data Op = Add | Sub | Mult | Div
  deriving(Eq,Show)
data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)
  deriving(Eq,Show)

我的树

tree = Node (Node (Node (Leaf 20) Add (Leaf 20)) Sub (Leaf 2)) Mult (Node (Leaf 33) Div (Leaf 3))

--                 Node _   Mult   _
--                     /            \
--                    /              \
--                   /                \
--                  /                  \
--                 /                    \
--                /                      \
--             Node _ Sub _              Node _ Div _ 
--                 /     \                     /     \
--                /       \                   /       \
--               /      Leaf 2            Leaf 33    Leaf 3
--              /           
--             /             
--          Node _ Add _                 
--              /       \
--             /         \
--            /           \
--         Leaf 20      Leaf 30

最后的输出应该类似于这个字符串 "(((20+30)-2)*(33 <code>div 3))".

Answer 1

treeToStr :: (Show a, Show b) => Tree a b -> String
treeToStr (Leaf a) = show a
treeToStr (Node a n b) = "(" ++ treeToStr a ++ show n ++ treeToStr b ++ ")"

只需要提供运算符的转换即可输出符号，而不需要Show的隐式实现。为此，您可能想要为 Op 手动实例化 Show 或引入新的 class，或者专门化您的 treeToStr.

data Op = Add | Sub | Mult | Div
  deriving Eq

-- Be careful about giving non-standard implementations of classes like show, in Haskell there are always laws and rules to follow: Show should output what Read would accept for example.
instance Show Op where
   show Add = ...
   ...

或

data Op = ... deriving Eq
data Tree = ... deriving Eq

class Stringifiable c where
   toStr :: c -> String

instance Stringifiable Op where
   toStr Add = ...

instance (Show a, Stringifiable b) => Stringifiable (Tree a b) where
  toStr (Leaf a) = show a
  toStr (Node a n b) = "(" ++ toStr a ++ toStr n ++ toStr b ++ ")"

-- You can then stringify your tree:
toStr tree

或者干脆

opTreeToStr :: Show a => Tree a Op -> String
opTreeToStr (Leaf a) = show a
opTreeToStr (Node a n b) = "(" ++ toStr a ++ opToStr n ++ toStr b ++ ")"

opToStr :: Op -> String
opToStr Add = "+"
...

-- Stringify tree, assuming it has the correct type Tree a Op:
opTreeToStr tree

haskell，数据树函数，字符串输出？

haskell, data tree functions, string output?

tree

haskell

types

pattern-matching