haskell折叠玫瑰树路径 [英] haskell fold rose tree paths

问题描述

 数据树a =节点a [Tree a]派生（Show ）
  

，并且该树有一些节点

  t =节点1 [节点2 [节点3 []]，节点4 []，节点5 [节点6 []]] 
  

以下函数将 collect 树中的路径。

  paths：Tree a  - > [b]路径（节点n ns）=地图（（n）n。concat。路径）
路径（节点n []）= [[n]] 
路径
  

如此：

  *主>路径t 
 [[1,2,3]，[1,4]，[1,5,6]] 
  

但是现在我们怎么能 fold 这些路径？显然我们可以做到这一点。在找到路径后会折叠。

  wastefullFold ::（a  - > b  - > b） - > b  - >树a  - > [b] 
 wastefullFold f z（Node n ns）= map（foldr f z）$ paths（Node n ns）
 
 * main> wastefullFold（+）0 t 
 [6,5,12] 
  

离我最近一些是：

  foldTreePaths ::（a  - > [b]  - > [b]） - > [b]  - >树a  - > [b]] 
 foldTreePaths fz（Node n []）= [fnz] 
 foldTreePaths fz（Node n ns）= map（fn.c concat。foldTreePaths fz）ns 
 
 * Main> foldTreePaths（:) [] a 
 [1,2,3]，[1,4]，[1,5,6]] 
 
 * Main> foldTreePaths（（:)。（+ 1））[] a 
 [[2,3,4]，[2,5]，[2,6,7]] 
  

但我觉得应该有比下面更干净的东西

  *主> foldTreePaths（\ node base  - > [node + sum base]）[0] a 
 [[6]，[5]，[12]] 
  pre> 
 
 
基本上我不知道如何使用以下签名来写 foldTreePaths ：
 
 
 
  foldTreePaths ::（a  - > b  - > b） - > b  - >树a  - > [b]  
解决方案
我认为这很容易理解：
 
 $ b 
  foldRose fz（Node x []）= [fxz] 
 foldRose fz（Node x ns）= [fxy | n<  -  ns，y<  -  foldRose f z n] 
 
> foldRose（:) [] t 
 [[1,2,3]，[1,4]，[1,5,6]] 
> foldRose（+）0 t 
 [6,5,12] 
  
 
let us say we have a tree...
data Tree a = Node a [Tree a] deriving (Show)
and that tree has some nodes
t = Node 1 [Node 2 [Node 3 []], Node 4 [], Node 5 [Node 6 []]]
the following function will collect the paths in a tree.
paths :: Tree a -> [[a]]
paths (Node n []) = [[n]]
paths (Node n ns) = map ((:) n . concat . paths) ns
like so:
*Main> paths t
[[1,2,3],[1,4],[1,5,6]]
But now how could we fold these paths? Obviously we could do this. Which folds after finding the paths.
wastefullFold :: (a -> b -> b) -> b -> Tree a -> [b]
wastefullFold f z (Node n ns) = map (foldr f z) $ paths (Node n ns)

*main> wastefullFold (+) 0 t
[6,5,12]
The closest I can some is:
foldTreePaths :: (a -> [b] -> [b]) -> [b] -> Tree a -> [[b]]
foldTreePaths f z (Node n []) = [f n z]
foldTreePaths f z (Node n ns) = map (f n . concat . foldTreePaths f z) ns

*Main> foldTreePaths (:) [] a
[1,2,3],[1,4],[1,5,6]]

*Main> foldTreePaths ((:) . (+ 1)) [] a
[[2,3,4],[2,5],[2,6,7]]
but I feel like there should be something cleaner than this below
*Main> foldTreePaths (\node base -> [node + sum base]) [0] a
[[6],[5],[12]]
Basically I do not know how to write foldTreePaths with the following signature:

foldTreePaths :: (a -> b -> b) -> b -> Tree a -> [b]
解决方案
I think this is pretty easy with comprehensions:
foldRose f z (Node x []) = [f x z]
foldRose f z (Node x ns) = [f x y | n <- ns, y <- foldRose f z n]

> foldRose (:) [] t
[[1,2,3],[1,4],[1,5,6]]
> foldRose (+) 0 t
[6,5,12]


                        
这篇关于haskell折叠玫瑰树路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！