非二叉树的变形与复合设计模式的初学者实现

Question

目前，梦想仍在继续，对于我学到的每个 Haskell 概念，我都更加着迷。 然而，我还没有完全完成@luqui对我之前关于变形论的问题的回答，我会回来解决这个问题，直到一切正常为止。这是关于维基百科上的示例代码，处理二叉树上的变形。

尽管如此，我已经尝试对 NON BINARY 树实现变形，但我遇到了一些麻烦：

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] 

-- 最新的一行不让 ghc 对“map 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 = (+) } 

-- 并且这个最新的 sumTree 也是错误的ghc

我明白了>和 +，就像 C++ 运算符 >和+。所以我不明白 ghc 在我没有给它实现操作符 >/+ 或不实现的对象的情况下对我生气。

其次，我必须承认我对 => 的感觉完全模糊。 （与 -> ??? 不同）和 @ 似乎是模式匹配的指南。

您将如何更正此代码？

还有一个最新的问题， 我也在尝试这样做，因为复合模式恰好是 C++ 中对我来说最重要的。显然，我发现它几乎可以用 Haskell 中的一两行来描述（这对我来说真的很神奇）。

但是，haskell 的人会如何表达这样一个事实：Leaf 和 Composition 的 Composite 构造函数可能具有某种相同的 Interface？ （我知道这不是一个好词，因为数据不可变，但我希望你能猜测并理解我的担忧/目标）

这是总的编译错误；

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'

编辑 所以这是非二进制变形的最终版本

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 将通过在构造 Composition a 时应用类型类约束来实现。也许应该定义一个新的专门数据。但在这样做之前我应该​​学习类型类:-)

Answer 1

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

将来，尝试包含更多 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 转换为 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。

Answer 2

其次我必须承认我完全
朦朦胧胧的感觉=> （不同的
从 -> ???) 和 @ 似乎是
就像模式匹配指南一样。

考虑 elem 函数，它测试列表是否包含某个值。您可以将其定义为

elem _ [] = False
elem x (y:ys) | x == y = True
              | otherwise = elem x ys

哪个签名有此功能？看起来像 elem :: a -> [一]->布尔。但是编译器会抱怨，因为你写了 x == y，并且不是为每个 a 定义了 == 函数，只为那些 < code>a 位于 Eq 类型类。因此，您需要指定类似“对于 Eq 中的所有 a ...”之类的内容。为此，您需要 =>。因此 elem 的正确签名是 elem :: Eq a =>一个-> [一]->布尔。

@ 使您可以为整个结构命名并同时对其进行模式匹配。例如，如果您有模式 a@(x:xs) 并且使用 [1,2,3,4] 调用该函数，则 a 是 [1,2,3,4]，x 是 1，xs 是 [2,3,4]。