初学者实施非二进制树的血统与复合设计模式的实施

Question

目前，梦想仍在继续，在每个Haskell概念上，我学到的我更受诱惑。然而，我还没有完全满足这种珍贵的 @luqui答案的工作 我以前的关于语态性的问题, ，我要回到它，直到还可以。这是关于Wikipedia上的此示例代码的 二元树的命令.

尽管如此，我还是尝试实施CATAMORTISM 非二进制 树木，但我遇到了一些麻烦：

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在“地图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>/+的情况下对我生气。

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

您将如何更正此代码？

还有一个最新的问题，我也在尝试这样做，因为对C ++的综合模式恰好是最重要的。显然，我看到它几乎只能在Haskell中的一/两行中描述（这对我来说真是太神奇了）。

但是，您将如何表达一个事实，即构图的叶子和复合构造子可能具有某种相同的界面？ （我知道这不是一个好词，因为数据不是可变的，但我希望您能理解我的关注/目标）

这是总编译误差；

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 } 

根据下面的有效答案：我要要求的Haskell等效于C ++界面合同似乎是类型类别的约束。

因此，设计模式复合材料将通过在构造组合物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中，TypeClasses让呼叫者选择要使用的类型，但有一些约束。我建议阅读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 -> [a] -> Bool. 。但是编译器会抱怨，因为您写了 x == y, ，而不是每个 a 这 == 功能是定义的，仅适用于 a 在 EQ类型类. 。因此，您需要指定类似的内容：“对于eq中的所有a”。为此，您需要 =>. 。因此，正确的签名 elem 是 elem :: Eq a => a -> [a] -> Bool.

这 @ 使您有可能同时为整个结构提供一个名称和模式匹配。例如，如果您有模式 a@(x:xs) 然后您将该功能称为 [1,2,3,4], ， 然后 a 是 [1,2,3,4], x是 1 和 xs 是 [2,3,4].