Working on converting over some scheme code to haskell for some practice and I have a bit of an issue with creating a custom Binary Search Tree.
node x l r returns a lambda that gets you the corresponding value of that tree. However, when creating let t1 = node 5 (node 3 0 0) (node 8 (node 7 0 0) 0) I get the following errors:
[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
Original working scheme code:
(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")
($ foo bar)syntax means?0or a subtreenode x l rwhich is a function. Since they must be of the same type, Haskell is trying to use0as a function, and this will create issues. The idiomatic solution is to use algebraic types (data). If you really want to stick to Church encodings, you will instead need to use polymorphic types, but this is more advanced.