1

目前，梦想仍在继续，在我了解到的每个 haskell 概念中，我都更加着迷。然而，我还没有完全完成这个宝贵的@luqui 对我之前关于 catamorphism的问题的回答，我会回到它，直到它没问题。这是关于 Wikipedia 上的示例代码，处理BINARY trees 上的 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]

-- 最新的一行在“map g [y]”上并不讨好 ghc

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 中的一两行来描述（这对我来说真是太神奇了）。

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

这是总的编译错误；

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

4

2 回答 2

5

这里有一些不同的错误，所以我不确定在 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。

    为了将 an 转换a为 anr您需要将您的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约束应用于 type a。

此外，您应该使用标准功能max。

于 2011-01-20T02:39:03.420 回答
3

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

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

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

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

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

于 2011-01-20T12:53:37.977 回答