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. Re: Tying the knot with binary trees (Michael Schober)
2. Re: Tying the knot with binary trees (Ozgur Akgun)
3. Re: Tying the knot with binary trees (Markus L?ll)
4. Design of Webmachine in Haskell (Petar Radosevic)
5. cabal update behaviour (Hector)
6. Re: Design of Webmachine in Haskell (Michael Snoyman)
----------------------------------------------------------------------
Message: 1
Date: Sat, 14 Apr 2012 14:04:37 +0200
From: Michael Schober <[email protected]>
Subject: Re: [Haskell-beginners] Tying the knot with binary trees
To: David McBride <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"; Format="flowed"
Hi again,
thanks for your comments. I've tried your code, but unfortunately that
doesn't seem to do the trick.
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 = ...
I was reluctant to this version at first, but I gave it a try. You can
find it attached in the alt-linked-tree.hs (I hope it's okay to attach
code in files, but the code grew beyond snippetery and this way it's
probably more comfortable to test it).
Unfortunately, this doesn't work as well. The actual insert code in this
version looks like this:
-- inserts an element into a binary search tree
insert :: Ord a => a -> BinTree a -> BinTree a
insert v' (Leaf parent) =
let result = Node v' (Leaf result) (Leaf result) parent
in result
insert v' n@(Node v l r p) =
case compare v' v of
EQ -> n
LT -> let inserted = insert v' l
result = Node v inserted r p
in result
GT -> let inserted = insert v' r
result = Node v l inserted p
in result
I think the problem here is, that I don't modify the parent, but I
cannot seem to wrap my head around it today.
>> 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.
This looks pretty much like my code from the beginning, but it doesn't
work as well. However, in the meantime I played around with some
complexer trees to come across a deficit pattern, but it's really
strange. It seems to me as if random subtrees are missing. Sometimes
there are siblings as expected, sometimes even children of these
siblings, but there never seems to be a working tree.
I have an intuition that it could be the case that I have to modify the
parent as well in the recursive case, but I don't know how yet.
Anyway, I'll let it go for the weekend and return to doubly linked lists
for now. Maybe implementing more features for those will help me get a
better intuition for these kind of problems.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: alt-linked-tree.hs
Type: text/x-haskell
Size: 3101 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120414/dfbe8d78/attachment-0002.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: linked-tree.hs
Type: text/x-haskell
Size: 4526 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120414/dfbe8d78/attachment-0003.hs>
------------------------------
Message: 2
Date: Sat, 14 Apr 2012 13:25:00 +0100
From: Ozgur Akgun <[email protected]>
Subject: Re: [Haskell-beginners] Tying the knot with binary trees
To: Michael Schober <[email protected]>
Cc: [email protected]
Message-ID:
<calzazpdsd8jhvyheraz3vbsg6ow4usx24epsrwyl9n9nh7j...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Michael,
I had some code lying around, experimenting on tying-the-knot in the
context of trees.
I've just pushed it to github, hoping it can be helpful to you. The data
type is slightly different to yours but the ideas should apply.
https://github.com/ozgurakgun/knot-tree/blob/master/KnotBinTree.hs
HTH,
Ozgur
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120414/bd40803e/attachment-0001.htm>
------------------------------
Message: 3
Date: Sat, 14 Apr 2012 19:31:30 +0300
From: Markus L?ll <[email protected]>
Subject: Re: [Haskell-beginners] Tying the knot with binary trees
To: Michael Schober <[email protected]>, [email protected]
Message-ID:
<caldaiua2vavdkxeqptzxie9ft4tivwfjcto+6fhuffdpnzp...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Hi Michael
When you have a tree with nodes pointing back to their parents then
you essentially have a graph. If you plan to change that graph, then
you have to rebuild *the entire structure*, and there's no going
around that. (And you cant use any of the nodes you pattern match,
only the numbers.)
They say that for this or similar reasons you have to use a zipper,
but I know nothing more about them than this :-)
On Sat, Apr 14, 2012 at 3:04 PM, Michael Schober <[email protected]> wrote:
> Hi again,
>
> thanks for your comments. I've tried your code, but unfortunately that
> doesn't seem to do the trick.
>
>
> 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 = ...
>
>
> I was reluctant to this version at first, but I gave it a try. You can find
> it attached in the alt-linked-tree.hs (I hope it's okay to attach code in
> files, but the code grew beyond snippetery and this way it's probably more
> comfortable to test it).
>
> Unfortunately, this doesn't work as well. The actual insert code in this
> version looks like this:
>
> -- inserts an element into a binary search tree
>
> insert :: Ord a => a -> BinTree a -> BinTree a
> insert v' (Leaf parent) =
> ?let result = Node v' (Leaf result) (Leaf result) parent
> ?in result
> insert v' n@(Node v l r p) =
> ?case compare v' v of
> ? ?EQ -> n
> ? ?LT -> let inserted = insert v' l
> ? ? ? ? ? ? ?result = Node v inserted r p
> ? ? ? ? ?in result
> ? ?GT -> let inserted = insert v' r
> ? ? ? ? ? ? ?result = Node v l inserted p
> ? ? ? ? ?in result
>
> I think the problem here is, that I don't modify the parent, but I cannot
> seem to wrap my head around it today.
>
>
>>> 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.
>
>
> This looks pretty much like my code from the beginning, but it doesn't work
> as well. However, in the meantime I played around with some complexer trees
> to come across a deficit pattern, but it's really strange. It seems to me as
> if random subtrees are missing. Sometimes there are siblings as expected,
> sometimes even children of these siblings, but there never seems to be a
> working tree.
>
> I have an intuition that it could be the case that I have to modify the
> parent as well in the recursive case, but I don't know how yet.
>
> Anyway, I'll let it go for the weekend and return to doubly linked lists for
> now. Maybe implementing more features for those will help me get a better
> intuition for these kind of problems.
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
--
Markus L?ll
------------------------------
Message: 4
Date: Sat, 14 Apr 2012 18:38:06 +0200
From: Petar Radosevic <[email protected]>
Subject: [Haskell-beginners] Design of Webmachine in Haskell
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain
Hi,
I would love to create a port of Webmachine [1] in Haskell so I can
learn the language and in the meanwhile create something useful. The
problem is, I don't know how I would design such a system in Haskell.
Simply put, webmachine is a library in Erlang which let's you create a
REST API by binding resources to URI's. The resources have sane
defaults, defined with functions, like `resource_exists`,
`service_available` and `is_authorized`. You can override these
functions per resource to create your own API. Webmachine will then
create the appropriate response when a request comes in.
I have been thinking how to implement such a system in Haskell, and I
have come up with the following. First of, use WAI with Warp to handle
the `Request` -> `Response` cycle. That was easy to come up with, but
I'm still struggling with the following question: What would a
`Resource` be in Haskell? I need something that lets me define sane
defaults which I can override per resource. Should I have a `Resource`
typeclass which defines all the default functions? Or is there a better
way to accomplish this?
I hope the above was a bit clear, would appreciate any insights!
[1]: http://wiki.basho.com/Webmachine-Resource.html
--
Petar Radosevic | @wunki
------------------------------
Message: 5
Date: Sat, 14 Apr 2012 22:12:05 -0400
From: Hector <[email protected]>
Subject: [Haskell-beginners] cabal update behaviour
To: [email protected]
Message-ID:
<CAMT6h=-8-7eMBP11ga7_VhED=thijhxk5zu3m_cfiacrefg...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi all,
these are the steps I followed to get Haskell installed in my machine[1]:
https://gist.github.com/2389324
The installation completed successfully, and gave me these instructions:
Now do "cabal update" to initialize the package list
But when I do, I get this message:
Note: there is a new version of cabal-install available.
To upgrade, run: cabal install cabal-install
Which I do, but after another "cabal update" I'm given the same
message, meaning that cabal-install was not actually updated.
Any ideas on why this is happening?
Best,
--
?H?ctor
[1] Specs for my machine:
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 10.04.4 LTS
Release: 10.04
Codename: lucid
$ uname -a
Linux 2.6.32-33-generic #70-Ubuntu SMP x86_64 GNU/Linux
------------------------------
Message: 6
Date: Sun, 15 Apr 2012 06:10:07 +0300
From: Michael Snoyman <[email protected]>
Subject: Re: [Haskell-beginners] Design of Webmachine in Haskell
To: Petar Radosevic <[email protected]>
Cc: [email protected]
Message-ID:
<caka2jgktkbxmz4fg0nl8v4bndbjst4msn9nnvjbfvh3clr5...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
On Sat, Apr 14, 2012 at 7:38 PM, Petar Radosevic <[email protected]> wrote:
> Hi,
>
> I would love to create a port of Webmachine [1] in Haskell so I can
> learn the language and in the meanwhile create something useful. The
> problem is, I don't know how I would design such a system in Haskell.
>
> Simply put, webmachine is a library in Erlang which let's you create a
> REST API by binding resources to URI's. The resources have sane
> defaults, defined with functions, like `resource_exists`,
> `service_available` and `is_authorized`. You can override these
> functions per resource to create your own API. Webmachine will then
> create the appropriate response when a request comes in.
>
> I have been thinking how to implement such a system in Haskell, and I
> have come up with the following. First of, use WAI with Warp to handle
> the `Request` -> `Response` cycle. That was easy to come up with, but
> I'm still struggling with the following question: What would a
> `Resource` be in Haskell? I need something that lets me define sane
> defaults which I can override per resource. Should I have a `Resource`
> typeclass which defines all the default functions? Or is there a better
> way to accomplish this?
>
> I hope the above was a bit clear, would appreciate any insights!
>
> [1]: http://wiki.basho.com/Webmachine-Resource.html
> --
> Petar Radosevic | @wunki
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
Hi Petar,
When I was at QCon, I heard a talk from Steve Vinoski on Webmachine,
and I was surprised to hear how close webmachine was to Haskell
already, The concept is basically sticking a state monad on top of
WAI. My guess is you would want to use a record type for a Resource,
not a typeclass, to make it easier to swap out behaviors. But
honestly, I haven't given this any thought since I saw the
presentation 6 months ago.
Michael
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 46, Issue 20
*****************************************
