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. Learning Haskell with the help of trees (Michal Kawalec)
2. Re: Learning Haskell with the help of trees (Bob Ippolito)
3. Re: Learning Haskell with the help of trees (Michal Kawalec)
4. Re: Learning Haskell with the help of trees (Bob Ippolito)
5. Space leak while reading from a file? (Jan Snajder)
----------------------------------------------------------------------
Message: 1
Date: Sat, 10 May 2014 13:05:08 +0100
From: Michal Kawalec <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Learning Haskell with the help of trees
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Hi,
I am beginning to learn Haskell, and I decided to try to implement a
tree. Its code is available at
https://gist.github.com/anonymous/dd3eaa8bc36025d7751c
I would need some help with implementing the delete element procedure. I
have a feeling I am doing something very unhaskelly there. Also, when
deleting a node having two children, how do I run two actions (swap the
values and delete the successor)?
Also, I would be delighted if you could take a look on the style and
similar aspects, as they are best addressed at the beginning.
Thanks,
Michal
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 555 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140510/a5a955d8/attachment-0001.sig>
------------------------------
Message: 2
Date: Sat, 10 May 2014 08:27:10 -0700
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Learning Haskell with the help of
trees
Message-ID:
<cacwmpm9d8wqa0bvkf0l+lupuwf9m-xchaqqnu5e6qompcdf...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
In order to implement delete you need to have some sort of merge operation
for the cases where the node being deleted has more than one child. In this
case your tree data structure doesn't appear to be a search tree or
balanced in any way so it's much harder to generally decide how delete
should work.
On Sat, May 10, 2014 at 5:05 AM, Michal Kawalec <[email protected]> wrote:
> Hi,
>
> I am beginning to learn Haskell, and I decided to try to implement a
> tree. Its code is available at
> https://gist.github.com/anonymous/dd3eaa8bc36025d7751c
>
> I would need some help with implementing the delete element procedure. I
> have a feeling I am doing something very unhaskelly there. Also, when
> deleting a node having two children, how do I run two actions (swap the
> values and delete the successor)?
>
> Also, I would be delighted if you could take a look on the style and
> similar aspects, as they are best addressed at the beginning.
>
>
>
> Thanks,
> Michal
>
>
> _______________________________________________
> 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/20140510/5427d654/attachment-0001.html>
------------------------------
Message: 3
Date: Sat, 10 May 2014 18:51:59 +0100
From: Michal Kawalec <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Learning Haskell with the help of
trees
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On 10.05.2014 16:27, Bob Ippolito wrote:
> In order to implement delete you need to have some sort of merge
> operation for the cases where the node being deleted has more than one
> child. In this case your tree data structure doesn't appear to be a
> search tree or balanced in any way so it's much harder to generally
> decide how delete should work.
But this is a binary (albeit unbalanced, which changes nothing) tree :)
Michal
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 555 bytes
Desc: OpenPGP digital signature
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140510/67ad5457/attachment-0001.sig>
------------------------------
Message: 4
Date: Sat, 10 May 2014 11:25:47 -0700
From: Bob Ippolito <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Learning Haskell with the help of
trees
Message-ID:
<CACwMPm_xKSbVBFwOZjZxQbD=MmwyV7pbZfsJ7NjBDw28=rs...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Sure, but you still have to make some arbitrary decisions that define the
strategy for making one tree out of two. It's harder when the data
structure doesn't make that decision for you by its definition. Write that
function and then your delete is practically finished.
On Saturday, May 10, 2014, Michal Kawalec <[email protected]> wrote:
> On 10.05.2014 16:27, Bob Ippolito wrote:
> > In order to implement delete you need to have some sort of merge
> > operation for the cases where the node being deleted has more than one
> > child. In this case your tree data structure doesn't appear to be a
> > search tree or balanced in any way so it's much harder to generally
> > decide how delete should work.
>
>
>
> But this is a binary (albeit unbalanced, which changes nothing) tree :)
>
>
> Michal
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140510/23f5b362/attachment-0001.html>
------------------------------
Message: 5
Date: Sun, 11 May 2014 13:24:39 +0200
From: Jan Snajder <[email protected]>
To: beginners <[email protected]>
Subject: [Haskell-beginners] Space leak while reading from a file?
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8
Dear all,
I'm trying to implement a simple file-based database. I apparently have
a space leak, but I have no clue where it comes from.
Here's the file-based database implementation:
http://pastebin.com/QqiqcXFw
The idea to have a database table in a single textual file. One line
equals one table row. The fields within a row are whitespace separated.
The first field is the key. Because I'd like to work with large files, I
don't want to load the whole file into memory. Instead, I'd like to be
able to fetch the rows on demand, by keys. Thus I first create an index
that links keys to file seeks. I use the readerT to add the index to the
IO monad.
For testing, I use a dummy table produced as follows:
import System.IO
import Text.Printf
import Control.Monad
row = unwords [printf "field%03d" (i::Int) | i <- [1..999]]
main = do
forM_ [1..250000] $ \i ->
putStrLn $ printf "row%06d %s" (i::Int) row
This generates a 2.1G textual file, which I store on my disk.
The testing code:
import FileDB
import qualified Data.Text as T
import Text.Printf
import Control.Applicative
import Control.Monad
import Control.Monad.Trans
import System.IO
import System.Environment
main = do
(f:_) <- getArgs
t <- openTable f
runDB t $ do
ks <- getKeys
liftIO $ do
putStrLn . printf "%d keys read" $ length ks
putStrLn "Press any key to continue..."
getChar
forM_ ks $ \k -> do
Just r <- getRow k
liftIO . putStrLn $ printf "Row \"%s\" has %d fields"
(T.unpack k) (length r)
When I run the test on the 2.1GB file, the whole program consumes 10GB.
6GB seem to be allocated after the index is built (just before entering
the forM_ function). The remaining 4GB are allocated while fetching all
the rows.
I find both things difficult to explain.
6GB seems too much for the index. Each key is 9 characters (stored as
Data.Text), and I have 250K such keys in a Data.Map. Should this really
add up to 6GB?
Also, I have no idea why fetching all the rows, one by one, should
consume any additional memory. Each row is fetched and its length is
computed and printed out. I see no reason for the rows to be retained in
the memory.
Here's the memory allocation summary:
> 1,093,931,338,632 bytes allocated in the heap
> 2,225,144,704 bytes copied during GC
> 4,533,898,000 bytes maximum residency (26 sample(s))
> 3,080,926,336 bytes maximum slop
> 10004 MB total memory in use (0 MB lost due to fragmentation)
>
> Tot time (elapsed) Avg pause Max
pause
> Gen 0 2171739 colls, 0 par 45.29s 45.26s 0.0000s
0.0030s
> Gen 1 26 colls, 0 par 1.50s 1.53s 0.0589s
0.7087s
>
> INIT time 0.00s ( 0.00s elapsed)
> MUT time 279.92s (284.85s elapsed)
> GC time 46.80s ( 46.79s elapsed)
> EXIT time 0.68s ( 0.71s elapsed)
> Total time 327.40s (332.35s elapsed)
>
> %GC time 14.3% (14.1% elapsed)
>
> Alloc rate 3,908,073,170 bytes per MUT second
>
> Productivity 85.7% of total user, 84.4% of total elapsed
Btw., I don't get the "bytes allocated in the heap" figure, which is
approx. 1000 GB (?).
I'm obviously doing something wrong here. I'd be thankful for any help.
Best,
Jan
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 71, Issue 13
*****************************************
