Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: error: Not in scope: data constructor `BinTree'
(Antoine Latter)
2. Re: error: Not in scope: data constructor `BinTree' (Kak Dod)
3. Re: Tying the knot with binary trees (David McBride)
4. Re: Tying the knot with binary trees (David McBride)
5. Re: error: Not in scope: data constructor `BinTree' (Kyle Murphy)
----------------------------------------------------------------------
Message: 1
Date: Fri, 13 Apr 2012 11:54:40 -0500
From: Antoine Latter <aslat...@gmail.com>
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: Kak Dod <kak.dod2...@yahoo.com>
Cc: "beginners@haskell.org" <beginners@haskell.org>, Kyle Murphy
<orc...@gmail.com>
Message-ID:
<cakjsnqh-fhvragndbiox0snkd0+_4sthnqsbd1c9wmerpc9...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
On Fri, Apr 13, 2012 at 11:46 AM, Kak Dod <kak.dod2...@yahoo.com> wrote:
> Thank you but
> if I change the code like this:
>
> data BinTree a = Node BinTree a BinTree a | EmptyBinTree deriving Show
>
If you look closely, Kyle made other changes to your code as well :-)
Antoine
------------------------------
Message: 2
Date: Sat, 14 Apr 2012 01:02:58 +0800 (SGT)
From: Kak Dod <kak.dod2...@yahoo.com>
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: Tom Murphy <amin...@gmail.com>
Cc: "beginners@haskell.org" <beginners@haskell.org>, Kyle Murphy
<orc...@gmail.com>
Message-ID:
<1334336578.22217.yahoomail...@web193206.mail.sg3.yahoo.com>
Content-Type: text/plain; charset="iso-8859-1"
Thanks Tom. this is what i wanted
I do not want "Node a" there, I wants only Node and Tom's solution works.
Thanks to all .
________________________________
From: Tom Murphy <amin...@gmail.com>
To: Kak Dod <kak.dod2...@yahoo.com>
Cc: Kyle Murphy <orc...@gmail.com>; "beginners@haskell.org"
<beginners@haskell.org>
Sent: Friday, 13 April 2012 4:53 PM
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor `BinTree'
"(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 <kak.dod2...@yahoo.com> 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 <orc...@gmail.com>
> To: Kak Dod <kak.dod2...@yahoo.com>
> Cc: "beginners@haskell.org" <beginners@haskell.org>
> 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" <kak.dod2...@yahoo.com> 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
>>Beginners@haskell.org
>>http://www.haskell.org/mailman/listinfo/beginners
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120414/18f76ca9/attachment-0001.htm>
------------------------------
Message: 3
Date: Fri, 13 Apr 2012 13:49:40 -0400
From: David McBride <toa...@gmail.com>
Subject: Re: [Haskell-beginners] Tying the knot with binary trees
To: Michael Schober <micha-scho...@web.de>
Cc: beginners@haskell.org
Message-ID:
<can+tr41kr3scqfennmv6owzgz15iey2houcuoodzhaxmacm...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
You are right that the problem is with your insert algorithm. When
you are inserting, what you are doing is you traverse down the correct
side of the tree, you make a new node and then you return that node,
thereby trashing the rest of the tree.
Here is the general approach of what you should do. You know you are
going left or right down the tree, and you know you are probably going
to change it, that means you have to change every node down along the
length of the tree.
insert v' Leaf = mkRoot v'
insert v' n@(Node v l r f) = case compare v v' of
EQ -> n
GT -> (Node v (insert v' l) r f)
LT -> (Node v l (insert v' r) f)
The only problem with this is that the parent node is not getting set
with this algorithm. The problem is that Leaves do not know their
parents, so one solution is to change your data type to this:
data BinTree a =
Leaf { lfather :: BinTree a } |
Node { value :: a
, left :: BinTree a
, right :: BinTree a
, father :: BinTree a
}
then insert would become
insert v' (Leaf parent) = let result = Node v' (Leaf result) (Leaf
result) parent
insert v' n = ...
Otherwise you'll have to pass the parent down along the tree as you
modify it as such:
insert v' Leaf = mkRoot v'
insert v' n@(Node v l r f) = case compare v v' of
EQ -> n
GT -> (Node v (insert' v' l n) r f)
LT -> (Node v l (insert' v' r n) f)
insert' v' Leaf parent = Node v' Leaf Leaf parent
insert' v' n@(Node v l r f) parent = case compare v v' of
EQ -> n
GT -> let result = Node v (insert' v' l result) r parent in result
LT -> let result = Node v l (insert' v' r result) parent in result
You require a base case because the first node has no parent to insert with.
On Fri, Apr 13, 2012 at 12:16 PM, Michael Schober <micha-scho...@web.de> wrote:
> 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
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 4
Date: Fri, 13 Apr 2012 13:52:05 -0400
From: David McBride <toa...@gmail.com>
Subject: Re: [Haskell-beginners] Tying the knot with binary trees
To: Michael Schober <micha-scho...@web.de>
Cc: beginners@haskell.org
Message-ID:
<CAN+Tr406n1yiBYyQuDnYJkMGnsP3xOoW6r7eHieZEMx=az8...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Sorry this snippet should have been:
then insert would become:
insert v' (Leaf parent) = let result = Node v' (Leaf result) (Leaf
result) parent in result
insert v' n = ...
I did not test that code, but it should work.
On Fri, Apr 13, 2012 at 1:49 PM, David McBride <toa...@gmail.com> wrote:
> You are right that the problem is with your insert algorithm. ?When
> you are inserting, what you are doing is you traverse down the correct
> side of the tree, you make a new node and then you return that node,
> thereby trashing the rest of the tree.
>
> Here is the general approach of what you should do. ?You know you are
> going left or right down the tree, and you know you are probably going
> to change it, that means you have to change every node down along the
> length of the tree.
>
> insert v' Leaf = mkRoot v'
> insert v' n@(Node v l r f) = case compare v v' of
> ?EQ -> n
> ?GT -> (Node v (insert v' l) r f)
> ?LT -> (Node v l (insert v' r) f)
>
> The only problem with this is that the parent node is not getting set
> with this algorithm. ?The problem is that Leaves do not know their
> parents, so one solution is to change your data type to this:
>
> data BinTree a =
> ?Leaf { lfather :: BinTree a } |
> ?Node { value :: a
> ? ? ? ? ?, left :: BinTree a
> ? ? ? ? ?, right :: BinTree a
> ? ? ? ? ?, father :: BinTree a
> ?}
>
> then insert would become
> insert v' (Leaf parent) = let result = Node v' (Leaf result) (Leaf
> result) parent
> insert v' n = ...
>
> Otherwise you'll have to pass the parent down along the tree as you
> modify it as such:
>
> insert v' Leaf = mkRoot v'
> insert v' n@(Node v l r f) = case compare v v' of
> ?EQ -> n
> ?GT -> (Node v (insert' v' l n) r f)
> ?LT -> (Node v l (insert' v' r n) f)
>
> insert' v' Leaf parent = Node v' Leaf Leaf parent
> insert' v' n@(Node v l r f) parent = case compare v v' of
> ?EQ -> n
> ?GT -> let result = Node v (insert' v' l result) r parent in result
> ?LT -> let result = Node v l (insert' v' r result) parent in result
>
> You require a base case because the first node has no parent to insert with.
>
> On Fri, Apr 13, 2012 at 12:16 PM, Michael Schober <micha-scho...@web.de>
> wrote:
>> 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
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners@haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 5
Date: Fri, 13 Apr 2012 14:32:02 -0400
From: Kyle Murphy <orc...@gmail.com>
Subject: Re: [Haskell-beginners] error: Not in scope: data constructor
`BinTree'
To: Kak Dod <kak.dod2...@yahoo.com>
Cc: "beginners@haskell.org" <beginners@haskell.org>
Message-ID:
<CA+y6Jcx8vwMdW=wm3cgiysqph-kzudgoqxzhpweogcslbj0...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
If you don't include "Node a" then there isn't any point in having the a
parameter on BinTree as it's never used unless you add another constructor
that uses it. I based the modification on the usage in your example where
you're trying to store a value of 3. Without that parameter the code
becomes:
b1 = Node EmptyBinTree EmptyBinTree
I haven't tried it, but that will also likely complain it can't deduce "a"
from the usage.
-R. Kyle Murphy
Sent from my phone.
On Apr 13, 2012 1:03 PM, "Kak Dod" <kak.dod2...@yahoo.com> wrote:
> Thanks Tom. this is what i wanted
> I do not want "Node a" there, I wants only Node and Tom's solution works.
> Thanks to all .
>
> ------------------------------
> *From:* Tom Murphy <amin...@gmail.com>
> *To:* Kak Dod <kak.dod2...@yahoo.com>
> *Cc:* Kyle Murphy <orc...@gmail.com>; "beginners@haskell.org" <
> beginners@haskell.org>
> *Sent:* Friday, 13 April 2012 4:53 PM
> *Subject:* Re: [Haskell-beginners] error: Not in scope: data constructor
> `BinTree'
>
> "(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 <kak.dod2...@yahoo.com> 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 <orc...@gmail.com>
> > To: Kak Dod <kak.dod2...@yahoo.com>
> > Cc: "beginners@haskell.org" <beginners@haskell.org>
> > 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" <kak.dod2...@yahoo.com> 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
> >>Beginners@haskell.org
> >>http://www.haskell.org/mailman/listinfo/beginners
> >>
> >>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120413/74418cca/attachment.htm>
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 46, Issue 18
*****************************************
