-3

我有一个作业：

1) 为树定义一个数据结构TTT，其中每个顶点有 0、1 或 2 个孩子，每个树叶（有 0 个孩子的顶点和自身）包含一个自然数列表；

2）创建一个mm具有 2 个参数的函数 - functionf(Integer->Integer)和TTTbased tree x。结果，它应该给出基于对列表中每个元素使用函数TTT的树（参考 1）定义）；xf

函数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

有人可以帮我吗？

4

2 回答 2

22

重要建议

通过Learn You a Haskell for Great Good真的很值得。这是一个很好的教程。

实践！玩！通过更改摘要来扩展此任务。你可以为字符串而不是整数做吗？你能用三个子树做一棵树吗？你能做一个分支也有数据的地方吗？你能制作一棵采用任何数据类型的树吗？了解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)

现在你需要一个具有三种可能性的叶子，其中叶子有一个整数列表，而另外两个有一个子树，或者两个子树。将示例中的想法放在一起。

问题 2：在树上映射一个函数

我们将此称为 apply-a-function-everywhere-you-can"map"ping 函数。map为列表fmap做，为其他事情做。

让我们定义一个接受 aBool -> 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 编写一些程序，其长度仅为传统语言程序长度的十分之一。多想！少写！

于 2012-11-05T22:27:26.997 回答
0

当它按预期工作时，我已经走到了这一步，除了我在叶子中有一个整数而不是 Ingeter 列表。我现在的问题是我应该在这段代码中更改什么以便叶子只能包含整数列表？到目前为止，我尝试像这样修改树定义：

data TTT a = ALeaf [Integer] | ABranch (TTT a) (TTT a)

并修改数据：

testTree1 = ABranch (ALeaf [1,2,3]) (ALeaf [4,5,6])

但在这种情况下，整数列表保持不变。

下面是叶中有一个整数的稳定代码，它可以工作。

{-# LANGUAGE DeriveFunctor #-}

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

-- Function "mm"
mm f t = let
   in fmap (f) t

-- Function "tt_a"
tt_a = mm a testTree1

-- Function "tt_b"
tt_b = mm b testTree1

-- Function "tt_c"
tt_c = mm c testTree1

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

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

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

-- TTT type tree`s for tests
testTree1 = ABranch (ALeaf 1) (ALeaf 2)
testTree2 = ABranch (ALeaf 11) (ALeaf 12)
于 2012-11-07T21:20:31.603 回答