Databases
StackOverflow2013
Postsdbo
POHow do you save a tree data structure to binary file in Haskell
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow do you save a tree data structure to binary file in Haskell
    primarykey
    data
    text
    <p>I'm trying to save a simple (but quite big) Tree structure into a binary file using Haskell. The structure looks something like this:<pre> -- For simplicity assume each Node has only 4 childs data Tree = Node [Tree] | Leaf [Int] </pre> And here is how I need the data look on disk:</p> <ol> <li>Each node starts with four 32-bit offsets to it's children, then follow the childs.</li> <li>I don't care much about the leafs, let's say it's just n consecutive 32-bit numbers.</li> <li>For practival purposes I would need some node labels or some other additional data but right now I don't care about that much neither.</li> </ol> <p>It apears to me that Haskellers first choice when writing binary files is the Data.Binary.Put library. But with that I have a problem in the bullet #1. In particular, when I'm about to write a Node to a file, to write down the child offsets I need to know my current offset and the size of each child.</p> <p>This is not something that Data.Binary.Put provides so I thought this must be a perfect application of Monad transformers. But even though it sounds cool and functional, so far I have not been successfull with this approach.</p> <p>I asked two other questions that I thought would help me solve the problem <a href="https://stackoverflow.com/questions/4828902/why-wrapping-the-data-binary-put-monad-creates-a-memory-leak">here</a> and <a href="https://stackoverflow.com/questions/5019655/why-wrapping-the-data-binary-put-monad-creates-a-memory-leak-part-2">here</a>. I must say that each time I received very nice answers that helped me progress further but unfortunatelly I am still unable to solve the problem as a whole.</p> <p><a href="http://hpaste.org/44419/how_do_you_save_a_tree_data_st" rel="nofollow noreferrer">Here</a> is what I've got so far, it still leaks too much memory to be practical.</p> <p>I would love to have solution that uses such functional approach, but would be grateful for any other solution as well.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USVadim Kotov
    1. USPeter Jankuliak
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow do you save a tree data structure to binary file in Haskell
      1. USiand675
      1. VTFavorite
    2. VO
      singulars
      1. POHow do you save a tree data structure to binary file in Haskell
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow do you save a tree data structure to binary file in Haskell
      1. USnominolo
      1. VTFavorite
    1. COHow big is the tree, and how large a file would you imagine that you'd be creating? The answer to this determines whether you can use any sort of put type structure at all, or if you need something that involves a single-pass traversal but modifying already written parts of your structure...
      singulars
      1. POHow do you save a tree data structure to binary file in Haskell
      1. USsclv
    2. COBinary serialization typically needs to know the size of the data to write (e.g. lists get prefixed with length). Could you live with text serialization (probably larger files)? Failing that you could do some tricks by writing to intermediate files and stitching them together (horrible but possible). Also in your test code the input is synthetic - if your real data isn't synthetic you might have it in memory anyway so normal binary serialization wouldn't be forcing anything that isn't already in the heap.
      singulars
      1. POHow do you save a tree data structure to binary file in Haskell
      1. USstephen tetley
    3. CO@sclv, the link "what I've got so far" above points to an extract of a bigger program I've been working on for some time now. In the original program I read a binary file with similar structure, transform it (mostly so that there isn't too many children per node) and then want to save it back. The source files have something between 50MB to 200MB so I imagine the destination files would be similar in size.
      singulars
      1. POHow do you save a tree data structure to binary file in Haskell
      1. USPeter Jankuliak
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload