致力于将一些方案代码转换为 haskell 以进行一些练习，我在创建自定义二叉搜索树时遇到了一些问题。node x l r返回一个 lambda，该 lambda 获取该树的相应值。但是，在创建let t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)时，我收到以下错误：
[1 of 1] Compiling Main ( binTree.hs, binTree.o )
binTree.hs:29:18: error:
• No instance for (Eq ((a1 -> a0 -> t0) -> a1 -> a0 -> t0))
arising from a use of ‘node’
(maybe you haven't applied a function to enough arguments?)
• In the expression: node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
In an equation for ‘t1’:
t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
In the expression:
do { let t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0);
print $ size t1 }
binTree.hs:29:23: error:
• No instance for (Num (a1 -> a0 -> t0))
arising from the literal ‘5’
(maybe you haven't applied a function to enough arguments?)
• In the first argument of ‘node’, namely ‘5’
In the expression: node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
In an equation for ‘t1’:
t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
binTree.hs:29:26: error:
• Ambiguous type variable ‘a1’ arising from a use of ‘node’
prevents the constraint ‘(Eq a1)’ from being solved.
Relevant bindings include
t1 :: ((a1 -> a0 -> t0) -> a1 -> a0 -> t0) -> a1 -> a0 -> t0
(bound at binTree.hs:29:13)
Probable fix: use a type annotation to specify what ‘a1’ should be.
These potential instances exist:
instance Eq Ordering -- Defined in ‘GHC.Classes’
instance Eq Integer
-- Defined in ‘integer-gmp-1.0.0.1:GHC.Integer.Type’
instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Base’
...plus 22 others
...plus three instances involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the second argument of ‘node’, namely ‘(node 3 0 0)’
In the expression: node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
In an equation for ‘t1’:
t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
binTree.hs:29:31: error:
• No instance for (Num (a0 -> t0)) arising from the literal ‘3’
(maybe you haven't applied a function to enough arguments?)
• In the first argument of ‘node’, namely ‘3’
In the second argument of ‘node’, namely ‘(node 3 0 0)’
In the expression: node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
binTree.hs:29:47: error:
• Ambiguous type variable ‘a0’ arising from a use of ‘node’
prevents the constraint ‘(Eq a0)’ from being solved.
Relevant bindings include
t1 :: ((a1 -> a0 -> t0) -> a1 -> a0 -> t0) -> a1 -> a0 -> t0
(bound at binTree.hs:29:13)
Probable fix: use a type annotation to specify what ‘a0’ should be.
These potential instances exist:
instance Eq Ordering -- Defined in ‘GHC.Classes’
instance Eq Integer
-- Defined in ‘integer-gmp-1.0.0.1:GHC.Integer.Type’
instance Eq a => Eq (Maybe a) -- Defined in ‘GHC.Base’
...plus 22 others
...plus three instances involving out-of-scope types
(use -fprint-potential-instances to see them all)
• In the second argument of ‘node’, namely ‘(node 7 0 0)’
In the third argument of ‘node’, namely ‘(node 8 (node 7 0 0) 0)’
In the expression: node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
binTree.hs:29:52: error:
• Ambiguous type variable ‘t0’ arising from the literal ‘7’
prevents the constraint ‘(Num t0)’ from being solved.
Relevant bindings include
t1 :: ((a1 -> a0 -> t0) -> a1 -> a0 -> t0) -> a1 -> a0 -> t0
(bound at binTree.hs:29:13)
Probable fix: use a type annotation to specify what ‘t0’ should be.
These potential instances exist:
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Double -- Defined in ‘GHC.Float’
instance Num Float -- Defined in ‘GHC.Float’
...plus two others
(use -fprint-potential-instances to see them all)
• In the first argument of ‘node’, namely ‘7’
In the second argument of ‘node’, namely ‘(node 7 0 0)’
In the third argument of ‘node’, namely ‘(node 8 (node 7 0 0) 0)’
binTree.hs:30:17: error:
• No instance for (Num ((a1 -> a0 -> t0) -> a1 -> a0 -> t0))
arising from a use of ‘size’
(maybe you haven't applied a function to enough arguments?)
• In the second argument of ‘($)’, namely ‘size t1’
In a stmt of a 'do' block: print $ size t1
In the expression:
do { let t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0);
print $ size t1 }
{-# LANGUAGE FlexibleContexts #-}
node x l r = s ->
if s == 0
then x
else if s == 1
then l
else if s == 2
then r
else error "invalid value"
--search x t = do
-- not (null t) && ((x == (datr t)) || ((x < (datr t)) && (search x (left t))) || ((x > (datr t)) && (search x (right t))))
multiply tree = do
if tree == 0
then 1
else ($ datr tree) * (multiply ($ left tree)) * (multiply ($ right tree))
datr t = t 0
left t = t 1
right t = t 2
size t = do
if t == 0
then 0
else 1 + (size ($ left t)) + (size ($ right t))
main :: IO ()
main = do
let t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0)
print $ size t1
原始工作方案代码：
(define (node x l r) ; x is data, l is left, r is right
(lambda (s)
(cond ((= s 0) x)
((= s 1) l)
((= s 2) r)
(#t 'error))))
(define (search x t) ; assuming a binary search tree
(and (not (null? t))
(or (= x (data t))
(and (< x (data t)) (search x (left t)))
(and (> x (data t)) (search x (right t))))))
(define (multiply tree)
(if (null? tree) 1 (* (data tree) (multiply (left tree)) (multiply (right tree)))))
;----------------------------------------------------------------------------------------;
(define (howmany tree expr)
(if (null? tree) 0
(if (expr (data tree)) (+ 1 (howmany (left tree) expr) (howmany (right tree) expr))
(+ (howmany (left tree) expr) (howmany (right tree) expr)))))
;----------------------------------------------------------------------------------------;
(define (data t) (t 0))
(define (left t) (t 1))
(define (right t) (t 2))
(define (size t) (if (null? t) 0 (+ 1 (size (left t)) (size (right t)))))
(define t1 (node 5 (node 3 '() '()) (node 8 (node 7 '() '()) '())))
(display (multiply t1))
(display "n")
请注意，在方案中，符号node表示二叉树节点的构造函数，其中第一个值是节点数据，然后是左侧子树，然后是右侧子树。 同样，datr、left和right是允许您访问树字段的投影函数。
Haskell有数据声明的语法。 在这样的树的情况下，它看起来像这样：
data Tree
= Node { datr :: Integer, left :: Tree, right :: Tree }
| Empty
从这里你可以定义乘法模式匹配与树的节点(Node)或空树(Empty)：
multiply :: Tree -> Integer
multiply Empty = 1
multiply (Node x l r) = x * (multiply l) * (multiply r)
第一行是类型签名。 Haskell是静态类型的，我们鼓励你显式提供类型。 不这样做会使代码和任何错误消息更难阅读。
当树为空时，第二行与情况匹配，非常类似于测试用例null?方案。 然后在第三行中，我们进入子树的递归调用。
multiple显示的是惯用的Haskell代码。 更直接的翻译是：
multiply t =
if t == Empty
then 1
else datr t * left t * right t
虽然功能正常，但不鼓励使用此类代码 - 相等测试比模式匹配具有更多的限制和机制。datr、left和right的函数是部分的，因此如果将它们应用于诸如Empty之类的值，它们将失败(即，如果前面的逻辑不持有您想要的不变量);模式匹配没有这种失败情况。
我将保留其余函数作为练习。