用于泛型Haskell树的通用foldr和foldl？ [英] Generalized foldr and foldl for using with generic Haskell trees?

问题描述

$ b <$ p

$ p> data（Eq a，Show a）=>树a = Void |节点a [Tree a]
派生（Eq，Show）

treefoldr ::（Eq a，Show a）=>
（a - > b - > c） - > c - > （c - > b - > b） - > b - >树a - > c

treefoldl ::（等式a，显示a）=>
（b - > a - > c） - > c - > （c - > b - > b） - > b - >树a - > c


即使我能理解在Haskell中foldr和foldl函数的工作方式，我也不太确定

编辑：我试过类似的东西（甚至不编译）：

  treefoldr _ g1 _ _ Void = g1 
 treefoldr f1 g1 f2 g2（Node a ts）= f1 a（foldr f2 g2 ts）
  

编辑2 ：另一个尝试...

  treefoldr _ z1 _ _ Void = z1 
 treefoldr f z1 g z2（Node a ts）= 
fa（foldr g z2 （\ x  - > treefoldr f z1 g z2 x）ts））
 
 treefoldl _ z1 _ _ Void = z1 
 treefoldl f z1 g z2（Node a ts）= 
f（foldl g z2（map（\ x  - > treefoldl f z1 g z2 x）ts））a 
  

treefoldr 正在工作，但是 treefoldl not：

 无法匹配预期的c类型推断类型`b'
`c'是一个刚性类型变量，由
绑定在trees.hs：47：42处的`treefoldl'的类型签名
`b'是一个刚性类型变量由
绑定在trees.hs：47：32处的`treefoldl'的类型签名
在`foldl'的第一个参数中，即`g'
在`f'的第一个参数中， ，即
`（foldl g z2（map（\ x  - > treefoldl f z1 g z2 x）ts））'
在表达式中：
f（map1（\ x  - > treefoldl f z1 g z2 x）ts））a 
  

解决方案

完整的错误信息：

 无法匹配预期类型'c'与推断类型`Tree a'
`c'是一个刚性类型变量被
绑定在`treefoldr'的类型签名在so.hs：5：14 
期望类型：[c] 
推断类型：[Tree a] 
在'fold'的第三个参数，即'ts'
在'f1'的第二个参数中，即'（foldr f2 g2 ts）'
  

这意味着

• ts 的类型为 [Tree a]


• 您正在使用它作为 foldr 的第三个参数。 code>


• foldr 期望其第三个参数的类型为 [c]
  

所以你需要处理 ts 到类型为 [c] ，并将结果传递给 foldr 而不是 ts 本身。 地图功能应该是一个好地方开始。

How can I write generalized foldr and foldl function for generic Haskell trees, given this definition?

data (Eq a, Show a) => Tree a = Void | Node a [Tree a]
    deriving (Eq, Show)

treefoldr :: (Eq a, Show a) => 
   (a -> b -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c

treefoldl :: (Eq a, Show a) =>
   (b -> a -> c) -> c -> (c -> b -> b) -> b -> Tree a -> c

Even if I can understand how foldr and foldl functions work in Haskell, I'm not quite sure how to write this generalized function for trees.

EDIT: I tried something like this (not even compiling):

treefoldr  _ g1 _ _    Void       = g1
treefoldr f1 g1 f2 g2 (Node a ts) = f1 a (foldr f2 g2 ts)

EDIT 2: another try...

treefoldr _ z1 _ _   Void      = z1
treefoldr f z1 g z2 (Node a ts) =
   f a (foldr g z2 (map (\x -> treefoldr f z1 g z2 x) ts))

treefoldl _ z1 _ _   Void      = z1
treefoldl f z1 g z2 (Node a ts) =
   f (foldl g z2 (map (\x -> treefoldl f z1 g z2 x) ts)) a

treefoldr is working, however treefoldl not:

Couldn't match expected type `c' against inferred type `b'
      `c' is a rigid type variable bound by
          the type signature for `treefoldl' at trees.hs:47:42
      `b' is a rigid type variable bound by
          the type signature for `treefoldl' at trees.hs:47:32
    In the first argument of `foldl', namely `g'
    In the first argument of `f', namely
        `(foldl g z2 (map (\ x -> treefoldl f z1 g z2 x) ts))'
    In the expression:
        f (foldl g z2 (map (\ x -> treefoldl f z1 g z2 x) ts)) a

解决方案

The error message in full:

Couldn't match expected type `c' against inferred type `Tree a'
  `c' is a rigid type variable bound by
      the type signature for `treefoldr' at so.hs:5:14
  Expected type: [c]
  Inferred type: [Tree a]
In the third argument of `foldr', namely `ts'
In the second argument of `f1', namely `(foldr f2 g2 ts)'

That means that

• ts is of type [Tree a]
• you are using it as the third argument to foldr
• foldr expects its third argument to be of type [c]
• [c] and [Tree a] are different types, hence this is an error

So you need to process ts into something of type [c] and pass that result to foldr instead of ts itself. The map function would be a good place to start.

这篇关于用于泛型Haskell树的通用foldr和foldl？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！