理解合并堆应用树折叠进行堆排序
understanding merge heap applying tree fold for heap sort
请帮助我理解下面的代码。我明白了
map heapify
适用于输出
map heapify [34,25,28]
[Node 34 [],Node 25 [],Node 28 []]
现在我该如何一步步理解这个表达式呢
merge_heaps = treefold merge_heap Nil
通过单独执行 merge_heap 进行了尝试。
merge_heap Nil . map heapify [34,25,28]
错误
<interactive>:13:18: error:
* Couldn't match expected type `a -> Heap a1'
with actual type `[Heap Integer]'
如何解释左折叠树结构以生成最大堆。击中。我应该如何进一步一步步理解。
如何将我对命令式语言中的堆排序的理解映射到某种功能意义上的维基百科。如何对不平衡的树折叠结构进行堆排序。
-- treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f))
treefold f zero [] = zero
treefold f zero [x] = x
treefold f zero (a:b:l) = treefold f zero (f a b : pairfold l)
where
pairfold (x:y:rest) = f x y : pairfold rest
pairfold l = l -- here l will have fewer than 2 elements
data Heap a = Nil | Node a [Heap a] deriving Show
heapify x = Node x []
heapsort :: Ord a => [a] -> [a]
heapsort = flatten_heap . merge_heaps . map heapify
where
merge_heaps :: Ord a => [Heap a] -> Heap a
merge_heaps = treefold merge_heap Nil
flatten_heap Nil = []
flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)
merge_heap :: Ord a => []
merge_heap heap Nil = heap
merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b)
| a < b = Node a (node_b: heaps_a)
| otherwise = Node b (node_a: heaps_b)
您遇到的具体错误,
<interactive>:13:18: error:
* Couldn't match expected type `a -> Heap a1'
with actual type `[Heap Integer]'
是因为您的测试表达式 merge_heap Nil . map heapify [34,25,28]
是 haskell 语法对 heapsort
定义(部分)的错误扩展。
您想将函数 merge_heaps . map heapify
应用到 [34,25,28]
。您不能仅通过连接字符串来做到这一点。在 Haskell 中,空格的函数应用总是比任何二元运算符具有更高的优先级。
您的代码被解析为 merge_heaps . (map heapify [34,25,28])
,这是一个类型错误,因为带括号的子表达式不是函数。你想要像 (merge_heaps . map heapify) [34,25,28]
或 merge_heaps (map heapify [34,25,28])
甚至 merge_heaps . map heapify $ [34,25,28]
这样的东西。也许现在不是最后一个。当您仍在学习语法和类型时,可能会感到困惑。
我认为 merge_heaps (map heapify [34,25,28])
是最简单的 - 它删除了所有运算符。暂时坚持下去。
请帮助我理解下面的代码。我明白了
map heapify
适用于输出
map heapify [34,25,28]
[Node 34 [],Node 25 [],Node 28 []]
现在我该如何一步步理解这个表达式呢
merge_heaps = treefold merge_heap Nil
通过单独执行 merge_heap 进行了尝试。
merge_heap Nil . map heapify [34,25,28]
错误
<interactive>:13:18: error:
* Couldn't match expected type `a -> Heap a1'
with actual type `[Heap Integer]'
如何解释左折叠树结构以生成最大堆。击中。我应该如何进一步一步步理解。
如何将我对命令式语言中的堆排序的理解映射到某种功能意义上的维基百科。如何对不平衡的树折叠结构进行堆排序。
-- treefold (*) z [a,b,c,d,e,f] = (((a*b)*(c*d))*(e*f))
treefold f zero [] = zero
treefold f zero [x] = x
treefold f zero (a:b:l) = treefold f zero (f a b : pairfold l)
where
pairfold (x:y:rest) = f x y : pairfold rest
pairfold l = l -- here l will have fewer than 2 elements
data Heap a = Nil | Node a [Heap a] deriving Show
heapify x = Node x []
heapsort :: Ord a => [a] -> [a]
heapsort = flatten_heap . merge_heaps . map heapify
where
merge_heaps :: Ord a => [Heap a] -> Heap a
merge_heaps = treefold merge_heap Nil
flatten_heap Nil = []
flatten_heap (Node x heaps) = x:flatten_heap (merge_heaps heaps)
merge_heap :: Ord a => []
merge_heap heap Nil = heap
merge_heap node_a@(Node a heaps_a) node_b@(Node b heaps_b)
| a < b = Node a (node_b: heaps_a)
| otherwise = Node b (node_a: heaps_b)
您遇到的具体错误,
<interactive>:13:18: error:
* Couldn't match expected type `a -> Heap a1'
with actual type `[Heap Integer]'
是因为您的测试表达式 merge_heap Nil . map heapify [34,25,28]
是 haskell 语法对 heapsort
定义(部分)的错误扩展。
您想将函数 merge_heaps . map heapify
应用到 [34,25,28]
。您不能仅通过连接字符串来做到这一点。在 Haskell 中,空格的函数应用总是比任何二元运算符具有更高的优先级。
您的代码被解析为 merge_heaps . (map heapify [34,25,28])
,这是一个类型错误,因为带括号的子表达式不是函数。你想要像 (merge_heaps . map heapify) [34,25,28]
或 merge_heaps (map heapify [34,25,28])
甚至 merge_heaps . map heapify $ [34,25,28]
这样的东西。也许现在不是最后一个。当您仍在学习语法和类型时,可能会感到困惑。
我认为 merge_heaps (map heapify [34,25,28])
是最简单的 - 它删除了所有运算符。暂时坚持下去。