Haskell二叉树

Question

我有一个功课:

1)TTT为树定义数据结构,其中每个顶点具有0,1或2个子节点,每个树叶(具有0个子节点的顶点及其自身)包含自然数列表;

2)创建一个mm具有2个参数的函数 - 函数f(Integer->Integer)和TTT基础树x.结果它应该给出TTT基于树的结构树,该树是x使用f列表中每个元素的函数(引用1)定义的;

函数f可以有以下表示(a,b或c):

a :: Integer -> Integer
a x = x * x

b :: Integer -> Integer
b x = x `mod` 9

c :: Integer -> Integer
c x = x * x * x

任何人都可以帮我吗？

Answer 1

重要建议

通过学习哈斯克尔为伟大的好事,真的值得一试.这是一个很好的教程.

实践!玩!通过更改简介来扩展此分配.你能用Strings代替整数吗？你能用三个子树做一棵树吗？你能做一个分支机构也有数据吗？你能创建一个采用任何数据类型的树吗？了解Functors.他们为什么好？你能创建一个代表计算的树,用于操作的分支+和数字的叶子吗？

你玩的越多,你就越自信.成为课堂上的人,在它出现之前发现了什么.每个人都会向你寻求帮助,当你被要求解决你小组中任何人遇到的棘手问题时,你会学到更多.

问题1:树数据类型

这里有一些提示.

这个二叉树有两个子树或一个布尔叶:

data BTree = Leaf Bool | Branch BTree BTree 
  deriving (Eq,Show)

这个数据结构有三个项目,包括一个Bools 列表:

data Triple = Triple Int String [Bool]
  deriving (Eq,Show)

这个有三种不同的可能性,因为Expr出现在右侧,它有点像一棵树.

data Expr = Var Char | Lam Char Expr | Let Char Expr Expr
  deriving (Eq,Show)

现在你需要一个有三种可能性的方法,其中leaf有一个Integers列表,另外两个有一个子树或两个子树.将想法放在示例中.

问题2:在树上映射函数

我们称之为apply-a-function-anywhere-you-can-map"ping"函数.map为列表做它,并fmap为其他事情做它.

让我们定义一个函数,它将a Bool -> Bool映射到第一个例子:

mapBTree :: (Bool -> Bool) -> BTree -> BTree
mapBTree f (Leaf b) = Leaf (f b)
mapBTree f (Branch b1 b2) = Branch (mapBTree f b1) (mapBTree f b2)

另一个映射在三联上.这一次,我们必须使其适用于Bool列表中的每个s.

mapBoolTriple :: (Bool -> Bool) -> Triple -> Triple
mapBoolTriple f (Triple i xs bs) = Triple i xs (map f bs)

注意我使用的标准函数map如下:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

所以它适用于我的列表中的f每一个x,从前面开始.

我是怎么做到这一点的

不过,这不是我真正做到这一点的方式.我补充一下

{-# LANGUAGE DeriveFunctor #-}

在我的文件的顶部,这将让我写

data BinTree a = ALeaf a | ABranch (BinTree a) (BinTree a)
   deriving (Eq, Show, Functor)

然后我就能做到

fmap (*100) (ABranch (ALeaf 12) (ALeaf 34))

这会给我

ABranch (ALeaf 1200) (ALeaf 3400)

但fmap更灵活:我也可以

fmap (<20) (ABranch (ALeaf 12) (ALeaf 34))
  -- ABranch (ALeaf True) (ALeaf False)

要么

fmap show (ABranch (ALeaf 12) (ALeaf 34))
 -- ABranch (ALeaf "12") (ALeaf "34")

没有我写一行功能fmap.我认为这会给你10/10使用其他语言功能,但0/10解决问题的设置,所以不要这样做,但要记住并尽可能使用它.

更多建议

学习Haskell很开心.它有时令人兴奋,但它会极大地奖励你学习.你将能够用更传统的语言在Haskell中编写一些程序的十分之一的程序.多想想!少写!