模式匹配类型变量中的值构造函数/ Haskell中的某种灵活函数多态

Question

假设我将二叉树的代数数据类型定义为:

data Tree a = Empty | Node a (Tree a) (Tree a)

为了构建树,我现在想要定义一个函数,(-<)这样我就可以创建这样的树:

1-<(2,3)      1-<(2-<(3,4),5)      1-<(Empty,2-<(4,5))
  1                 1                        1
 / \               / \                        \
2   3             2   5                        2
                 / \                          / \
                3   4                        4   5

这似乎不可能!我的理由是它必须有类型签名a -> (a, a) -> Tree a).那么我认为这也许可以解释型的东西a无论是作为Tree b一些其他类型的b,或者,如果失败,直率地a.以同样的方式我试图定义

f :: a -> Int
f (Just _) = 1
f _ = 0

这将是一个函数,它告诉我一个值是否是类型Maybe a并由是否构造Just.但这不起作用 - ghc然后想要类型签名Maybe a -> Int.

除非我不知道Haskell中的任何特殊功能,否则我想要的是不可能的.我现在的问题是:

• 是吗？或者我会错过什么？
• 什么是我想要的好近似？(我想寻求娴熟,所以例如写作(Right 2 -<(Right 3, Left (Right 4 -<(Right 1, Right 5)))不是解决方案.)

PS我真的不知道如何标题这个问题.

Answer 1

你可以创建三个不同的运算符:

(-<) :: a -> (a, a) -> Tree a
p -< (l, r) = Node p (Node l Empty Empty) (Node r Empty Empty)

(-<\) :: a -> (Tree a, a) -> Tree a
p -<\ (lt, r) = Node p lt (Node r Empty Empty)

(-</) :: a -> (a, Tree a) -> Tree a
p -</ (l, rt) = Node p (Node l Empty Empty) rt

然后你的树可以表达为

1-<(2,3)
1-<\(2-<(3,4),5)

和

1-<\(Empty,2-<(4,5))

Answer 2

你寻找的函数不能a -> (a, a) -> Tree a)在Haskell中有类型; 它根本就不是很好的打字.原因是那些as可以是任何类型,因此您不能在任何需要任何特定类型属性的操作中使用它们的值(例如检查它们是否为值Empty或Node值).

当你记得你可以把树放在树里时,你所要求的功能也是模棱两可的定义,所以这些as 的可能性实际上是可能的Tree b.例如,如果我试图Empty -< (Empty, Empty)制作一个Tree (Tree t)(对某些人来说t),这应该返回Node Empty Empty Empty我将其解释(Empty, Empty)为一对树​​的位置,或者Node (Node Empty Empty) (Node Empty Empty)我将其解释(Empty, Empty)为需要转换为叶节点的一对"裸值" ？(或者其他一种排列？)

您可以设计一种语言,以便可以解决这种歧义,但Haskell通过使值a完全不透明(如)完全不透明来避免这个问题.除了将其传递给另一个接受完全任意类型的函数之外,你基本上不能用这样的值做任何事情.这似乎是有限的,但这实际上是Haskell类型如何工作的关键部分,并负责许多安全保证,使许多通用库代码工作.

所以你需要的是每个职位都期待一个a或一个Tree a; 它是不可能接受"任何东西",看看它是否是一个Tree a.一种方法是使用涵盖所有可能性的一系列功能,如Lee的回答.如果有两个以上的职位,那就不那么有趣了!另一种可能性是仅接受树并使用将"裸值"转换为单个树¹的投影函数.例如

data Tree a = Empty | Node a (Tree a) (Tree a)
    deriving (Show, Eq, Ord)

(-<) :: a -> (Tree a, Tree a) -> Tree a
x -< (l, r) = Node x l r

t :: a -> Tree a
t x = Node x Empty Empty

然后,您通过使用t"标记"需要转换为树的所有内容来有效地解决上面提到的歧义,而没有标记的所有内容必须已经是正确类型的树.

您的示例将被写为:

*Main> 1 -< (t 2, t 3)
Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)
*Main> 1 -< (2 -< (t 3, t 4), t 5)
Node 1 (Node 2 (Node 3 Empty Empty) (Node 4 Empty Empty)) (Node 5 Empty Empty)
*Main> 1 -< (Empty, 2 -< (t 4, t 5))
Node 1 Empty (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty))

¹这基本上是return你写成Treemonad时要编写的函数,但是return通过简洁的树表达式来填充所有这些函数有点长,而且看起来与树木制作无关,所以我认为更好/更短的名称在这里有用(t不一定很好,但它很短,而且我没有感受到非常灵感).