Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Tying the knot with binary trees (Michael Schober)
2. error: Not in scope: data constructor `BinTree' (Kak Dod)
3. Re: error: Not in scope: data constructor `BinTree' (Kyle Murphy)
4. Re: error: Not in scope: data constructor `BinTree' (Kak Dod)
5. Re: error: Not in scope: data constructor `BinTree' (Tom Murphy)
----------------------------------------------------------------------
Message: 1
Date: Fri, 13 Apr 2012 18:16:43 +0200
From: Michael Schober <[email protected]>
Subject: [Haskell-beginners] Tying the knot with binary trees
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hi folk,
as an exercise I'm trying to write a binary tree whose nodes also
include a reference to its parent. I've got the data structure I want to
use and some helper functions, but there seems to be a bug in insert or
find or both (although I assume it's in insert).
Here's what I got so far:
data BinTree a = Leaf
| Node { value :: a
, left :: BinTree a
, right :: BinTree a
, father :: BinTree a
}
instance Show a => Show (BinTree a) where
show Leaf = "[]"
show (Node v l r _) = "(Node " ++ show v
++ " " ++ show l ++ " " ++ show r ++ ")"
mkRoot :: a -> BinTree a
mkRoot value = let root = Node value Leaf Leaf root
in root
member :: Ord a => a -> BinTree a -> Bool
member v Leaf = False
member v (Node v' l r _) =
if v == v' then True
else if v <= v' then member v l
else member v r
find :: Ord a => a -> BinTree a -> Maybe (BinTree a)
find v Leaf = Nothing
find v n@(Node v' l r _) =
if v == v' then Just n
else if v <= v' then find v l
else find v r
insert :: Ord a => a -> BinTree a -> BinTree a
insert v' Leaf = mkRoot v'
insert v' n@(Node v l r f) = insert' v' n f
where
insert' :: Ord a => a -> BinTree a -> BinTree a -> BinTree a
insert' v' Leaf f' = Node v' Leaf Leaf f'
insert' v' n@(Node v l r f) f' =
if v' == v then n
else if v' <= v
then let inserted = insert' v' l result
result = Node v inserted r f
in result
else let inserted = insert' v' r result
result = Node v l inserted f
in result
I thought this should do the trick, but here's what I get in ghci:
*Main> find 3 (insert 7 (insert 3 (insert 5 Leaf))) >>= return . parent
Just (Node 5 (Node 3 [] []) [])
I'm expecting to see
Just (Node 5 (Node 3 [] []) (Node 7 [] []))
Inserting into an empty tree (i.e. a leaf) works fine, as does mkRoot.
Also, it seems as inserting an existing value works fine as well - but
obviously I couldn't test that one exhaustingly so far.
I'm grateful for any pointers towards a solution.
Best regards,
Michael
P.S.: For those unfamiliar with this problem, here is a list of URLs of
what I read of the subject:
[1]
http://www.haskell.org/haskellwiki/Tying_the_Knot#Migrated_from_the_old_wiki
[2]
http://debasishg.blogspot.de/2009/02/learning-haskell-solving-josephus.html
[3] http://blog.sigfpe.com/2006/12/tying-knots-generically.html
------------------------------
Message: 2
Date: Sat, 14 Apr 2012 00:23:04 +0800 (SGT)
From: Kak Dod <[email protected]>
Subject: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="utf-8"
if i compile the following code I get "bintree.hs:3:13: Not in scope: data
constructor `BinTree'"
data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
b1 = (Node (BinTree 3) EmptyBinTree)
please help
-kak
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120414/d99aa5e7/attachment-0001.htm>
------------------------------
Message: 3
Date: Fri, 13 Apr 2012 12:38:50 -0400
From: Kyle Murphy <[email protected]>
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: Kak Dod <[email protected]>
Cc: "[email protected]" <[email protected]>
Message-ID:
<CA+y6Jcztm1mYPtvRhvGWjnSp161u_VNY=aavsvp98p5-9cz...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Your constructor is called Node, not BinTree.
data BinTree a = Node a (BinTree a) (BinTree a) | EmptyNode
b1 = Node 3 EmptyNode EmptyNode
-R. Kyle Murphy
Sent from my phone.
On Apr 13, 2012 12:24 PM, "Kak Dod" <[email protected]> wrote:
> if i compile the following code I get "bintree.hs:3:13: Not in scope: data
> constructor `BinTree'"
>
> data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
>
> b1 = (Node (BinTree 3) EmptyBinTree)
>
> please help
>
> -kak
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120413/5aa1efcf/attachment-0001.htm>
------------------------------
Message: 4
Date: Sat, 14 Apr 2012 00:46:56 +0800 (SGT)
From: Kak Dod <[email protected]>
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: Kyle Murphy <[email protected]>
Cc: "[email protected]" <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Thank you but
if I change the code like this:
data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
b1 = Node 3 EmptyBinTreeEmptyBinTree
Then I am get this error:
bintree.hs:1:23:
??? `BinTree' is not applied to enough type arguments
??? Expected kind `?', but `BinTree' has kind `k0 -> *'
??? In the type `BinTree'
??? In the definition of data constructor `Node'
??? In the data type declaration for `BinTree'
Failed, modules loaded: none.
________________________________
From: Kyle Murphy <[email protected]>
To: Kak Dod <[email protected]>
Cc: "[email protected]" <[email protected]>
Sent: Friday, 13 April 2012 4:38 PM
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor `BinTree'
Your constructor is called Node, not BinTree.
data BinTree a = Node a (BinTree a) (BinTree a) | EmptyNode
b1 = Node 3 EmptyNode EmptyNode
-R. Kyle Murphy
Sent from my phone.
On Apr 13, 2012 12:24 PM, "Kak Dod" <[email protected]> wrote:
if i compile the following code I get "bintree.hs:3:13: Not in scope: data
constructor `BinTree'"
>
>
>
>data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
>
>b1 = (Node (BinTree 3) EmptyBinTree)
>
>
>
>please help
>
>
>-kak
>
>
>_______________________________________________
>Beginners mailing list
>[email protected]
>http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120414/88430b63/attachment-0001.htm>
------------------------------
Message: 5
Date: Fri, 13 Apr 2012 12:53:44 -0400
From: Tom Murphy <[email protected]>
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: Kak Dod <[email protected]>
Cc: "[email protected]" <[email protected]>, Kyle Murphy
<[email protected]>
Message-ID:
<cao9q0txtmaafszw20woq7ctsfq-dffgqjrqqm+d_p935eir...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
"(BinTree a)" needs to be in parentheses to pattern-match properly.
data BinTree a = Node (BinTree a) (BinTree) a | EmptyBinTree
deriving Show
On 4/13/12, Kak Dod <[email protected]> wrote:
> Thank you but
>
> if I change the code like this:
>
> data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
>
> b1 = Node 3 EmptyBinTreeEmptyBinTree
>
> Then I am get this error:
>
> bintree.hs:1:23:
> ??? `BinTree' is not applied to enough type arguments
> ??? Expected kind `?', but `BinTree' has kind `k0 -> *'
> ??? In the type `BinTree'
> ??? In the definition of data constructor `Node'
> ??? In the data type declaration for `BinTree'
> Failed, modules loaded: none.
>
>
>
>
> ________________________________
> From: Kyle Murphy <[email protected]>
> To: Kak Dod <[email protected]>
> Cc: "[email protected]" <[email protected]>
> Sent: Friday, 13 April 2012 4:38 PM
> Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
> `BinTree'
>
>
> Your constructor is called Node, not BinTree.
> data BinTree a = Node a (BinTree a) (BinTree a) | EmptyNode
> b1 = Node 3 EmptyNode EmptyNode
> -R. Kyle Murphy
> Sent from my phone.
> On Apr 13, 2012 12:24 PM, "Kak Dod" <[email protected]> wrote:
>
> if i compile the following code I get "bintree.hs:3:13: Not in scope: data
> constructor `BinTree'"
>>
>>
>>
>>data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
>>
>>b1 = (Node (BinTree 3) EmptyBinTree)
>>
>>
>>
>>please help
>>
>>
>>-kak
>>
>>
>>_______________________________________________
>>Beginners mailing list
>>[email protected]
>>http://www.haskell.org/mailman/listinfo/beginners
>>
>>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 46, Issue 17
*****************************************
