树上的haskell折叠操作
data Tree a = Tree a [Tree a]
请注意,我们不允许空树,并且叶子是具有空子树列表的树。树上的haskell折叠操作
treeFold :: (a -> [b] -> b) -> Tree a -> b
treeFold f (Tree x s) = f x (map (treeFold f) s)
鉴于上述信息,我不明白是怎么树折叠功能 通过递归地施加折叠操作的子树,然后在根和结果应用的功能标签返回结果从子树返回。
我也不明白树折叠函数只有一个参数而不是2,当它作为参数传递给map函数,它仍然编译和正常运行。
例如,树大小函数下面,计数树的节点。
treeSize :: Tree a -> Int
treeSize = treeFold (\x ys -> 1 + sum ys)
所以运行的TreeSize树其中tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]]
给出了树的大小为4
在树尺寸功能以上,树折叠功能也被传递一个参数,而不是两个。另外,传递给树折叠函数的x在任何地方都没有被使用,所以你为什么需要它。删除它会导致程序无法编译,并提供以下错误消息。
Couldn't match type `a' with `[[Int] -> Int]'
`a' is a rigid type variable bound by
the type signature for treeSize :: Tree a -> Int
at treeFold.hs:15:1
In the first argument of `sum', namely `ys'
In the second argument of `(+)', namely `sum ys'
In the expression: 1 + sum ys
任何帮助将不胜感激。
第一个问题有点棘手,因为这是递归的东西......正如老师所说:“要理解递归,你必须学习,递归如何工作”。 :-P 一个小建议:尝试通过应用treeFold
与一棵树或一棵树与一棵树内,并由您自己(在纸上或其他)评估它。我认为,那么你可以感觉到发生了什么......(当然,使用一个简单的函数作为treeFold的参数;就像你的treeSize使用的那样)。
treeFold
仅得到一个在地图的身体参数,因为map
需要从a->b
功能,并treeFold
有型(a -> [b] -> b) -> Tree a -> b.
,所以如果你将它传递2个参数,将传递给map
只有一个值,这导致失败。 (+)需要两个参数,如果你写map (+1) [1,2,3]
,你会得到[2,3,4]
,因为(+1)应用于列表中的每个元素(和(+1)显然需要多一个参数,您treeFold f
以上)
你的榜样的TreeSize: 这是不对的,当你说,它只得到一个参数你可以写
treeSize t = treeFold (\x ys -> 1 + sum ys) t
,而不是你定义上面 的x不是。因为用于计数是没用的。但是,treeFold
n eeds有一个函数,它有两个参数,所以你给它的x。这是唯一的原因。您可以传递任何其他值。
我已经试过通过treeFold与一棵树,但仍然没有得到它。 如果你有一个名为** add **的函数,它添加了两个数字,那么你会写成'add x y = x + y'。当你将map添加为第一个参数时,如'map(add 5)[1,2,3]',它返回[6,7,8]。但是,你只是通过一个参数来添加。它从哪里得到另一个论据? 所以x和y是传递给treeFold的两个参数。 – Ishan 2013-04-26 03:13:34
@Ishan:如果你把它写成map(\ x - > add 5 x)[1,2,3]''也许会更清楚。但是'\ x - >通过[eta reduction](http://www.haskell.org/haskellwiki/Eta_conversion)添加5 x'与'add 5'相同。 – hammar 2013-04-26 03:22:58
未使用变
首先,明确标记变量为未使用的是_
替换变量的方式。所以,你真的想:
treeFold (\_ ys -> 1 + sum ys)
,因为你写你有一个编译器错误:
treeFold (\ys -> 1 + sum ys)
...这是不一样的东西。
褶皱
其次,我会用手上的例子树评估treeSize
所以你可以看到,有没有神奇的事情:
treeSize (Tree 1 [Tree 2 [], Tree 3 []])
-- Inline definition of 'treeSize'
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []])
-- Evaluate treeFold
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []])
-- Apply the anonymous function
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []])
-- Apply the 'map' function
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 [])
, treeFold (\_ ys -> 1 + sum ys) (Tree 3 [])
]
-- Apply both 'treeFold' functions
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) [])
, (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) [])
]
-- Apply the anonymous functions
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [])
, 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [])
]
-- map f [] = []
= 1 + sum [ 1 + sum []
, 1 + sum []
]
-- sum [] = 0
= 1 + sum [1 + 0, 1 + 0]
= 1 + sum [1, 1]
-- Apply 'sum'
= 1 + 2
= 3
然而,有一个简单的方法来记住如何treeFold
作品。它所做的就是用您提供的函数替换每个Tree
构造函数。
所以,如果您有:
Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]]
...你申请treeFold f
到,它会评估为:
f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]]
treeSum
只是特殊情况下f = (\_ ys -> 1 + sum ys)
:
1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]]
= 7
Currying
最后一点是如何在Haskell中进行咖啡的工作。当你定义像函数:
foo x y = x + y
...的编译器实际上是desugars两个嵌套函数:
foo = \x -> (\y -> x + y)
这就是为什么你可以部分应用功能,在Haskell只是一个参数。当你写foo 1
,将其转换为:
foo 1
= (\x -> (\y -> x + y)) 1
= \y -> 1 + y
换句话说,它返回一个参数的一个新功能。
在Haskell中,所有函数只需要一个参数,我们通过返回新函数来模拟多个参数的函数。这种技术被称为“咖喱”。
如果你喜欢更传统的主流语言的多参数的方法,你可以通过让函数接受一个元组参数模拟它:
f (x, y) = x + y
然而,这不是真正地道的Haskell,并赢得了”不会给你任何性能改善。
[为什么函数式编程很重要](http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf)。 – 2013-04-26 23:34:12