初始实现非二叉树的Catamorphism与复合设计模式

Question

目前,梦想还在继续,在每个haskell概念中我都知道我更有吸引力.然而,我还没有完全实现这个珍贵的@ luqui对我之前关于catamorphism的问题的回答,我会回来直到它没问题.这是关于维基百科上的这个示例代码,处理BINARY树上的catamorphism.

尽管如此,我曾尝试推行了catamorphism 非二进制树,但我面对一些麻烦:

data Composition a = Leaf a
                   | Composite [Composition a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a ?  r
                                                 , composite :: [r] ?  r }

foldComposition :: CompositionAlgebra a r ?  Composition a ?  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y] 

- 最新的一行不会请"g [y]"

maxOfPair :: a ?  a ?  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

maxInList :: [a] ?  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = ?x ?  1 + maxInList x }

sumTree :: (Num a) ? CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = (+) } 

- 对于ghc来说,这个最直接的sumTree也是错误的

我看到>和+,就像C++运算符>和+.所以我不明白ghc对我很生气而没有给予它实现opertor>/+的objets.

其次,我必须承认我对=>(不同于 - > ???)和@的感觉完全朦胧,这似乎就像是模式匹配的指南.

你会如何更正此代码？

还有一个最新的问题,我也在尝试这样做,因为复合模式恰好是C++中最重要的.显然我看到它几乎可以在Haskell的一两行中描述(这对我来说真的很神奇).

但是你怎么会有人表达组合的Leaf和Composite构造函数可能有某种相同的接口这一事实？(我知道这不是好词,因为数据不可变,但我希望你能猜到 - 理解我的关注/目标)

这是总编译错误;

src\Main.hs:27:79:
    Couldn't match expected type `[r]'
           against inferred type `Composition a'
    In the expression: y
    In the second argument of `map', namely `[y]'
    In the expression: map g [y]

src\Main.hs:30:20:
    Could not deduce (Ord a) from the context ()
      arising from a use of `>' at src\Main.hs:30:20-24
    Possible fix:
      add (Ord a) to the context of the type signature for `maxOfPair'
    In the expression: (x > y)
    In the expression: if (x > y) then (x) else (y)
    In the definition of `maxOfPair':
        maxOfPair x y = if (x > y) then (x) else (y)

src\Main.hs:41:0:
    Occurs check: cannot construct the infinite type: a = [a] -> [a]
    When generalising the type(s) for `sumTree'

编辑 所以这是非二元catamorphism的最终版本

data Composant a = Leaf a
                 | Composite [Composant a]

data CompositionAlgebra a r = CompositionAlgebra { leaf      :: a ?  r
                                             , composite :: [r] ?  r }

foldComposition :: CompositionAlgebra a r ?  Composant a ?  r
foldComposition a@(CompositionAlgebra {leaf = f}) (Leaf x) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) =  g(map(foldComposition a) ys)

maxOfPair :: Ord a ? a ?  a ?  a
maxOfPair x y = if( x > y) 
                then (x) 
                else (y)

maxInList :: Ord a => [a] ?  a
maxInList (x:xs) = maxOfPair x (maxInList xs)

treeDepth :: CompositionAlgebra a Integer
treeDepth = CompositionAlgebra { leaf = const 1, composite = ?x ?  1 + maxInList x }

addList :: Num a ? [a] ? a
addList (x:xs) = x + addList xs 

sumTree :: (Num a) ? CompositionAlgebra a a
sumTree = CompositionAlgebra { leaf = id, composite = addList } 

并且根据下面的有效答案:我要求的等同于C++接口契约的haskell似乎是类型类约束.

因此,设计模式Composite将通过在构造组合a时应用类型类约束来实现.也许应该定义一个新的专业数据.但是我应该在做之前学习类型类:-)

Answer 1

这里有一些不同的错误,所以我不确定在SO上处理它的最佳方法,但是到底是什么.

将来,尝试包含更多GHC提供的错误.

在:

foldComposition :: CompositionAlgebra a r ?  Composition a ?  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite [y]) =  map g [y]

该函数foldCompose有两个我可以看到的错误,其中只有一个会被类型检查器捕获.

1. 你是模式匹配(Composite [y]),只匹配一个元素的列表.你可能想要(Composite ys),它绑定ys到整个列表.

2. map g [y]不会传递类型检查器,因为你已经定义g为列出一个列表r,但是你给它一个列表a.

   要将a转换a为a,r您需要将其应用于CompositionAlgebra:g (map (foldComposition a) ys)

所以我写这个:

foldComposition :: CompositionAlgebra a r ?  Composition a ?  r
foldComposition a@(CompositionAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldComposition a@(CompositionAlgebra {composite = g}) (Composite ys) = g (map (foldComposition a) ys)

对于您的下一个错误:

maxOfPair :: a ?  a ?  a
maxOfPair x y = if( x > y) -- this doesnt please ghc either, Ordering trouble
                then (x) 
                else (y)

在Haskell中,类型变量(如此a处)所有由其寂寞可以由调用者在调用者选择时根据任何类型填充.

这意味着在您的类型签名中,您声称该函数maxPair适用于每种输入类型.GHC(以自己的方式)抱怨操作员>不适用于所有类型,因此拒绝编译您的程序.

您需要使用类型类来解决此问题.在Haskell中,类型类允许调用者选择要使用的类型,但是有一些约束.我建议在类型类上阅读Haskell 教程.

正确的类型签名是:

maxOfPair :: Ord a => a ?  a ?  a

这将Ord约束应用于类型a.

此外,您应该使用标准功能max.