Hobby-hacking Eric

2008-05-13

recurring problem (boring text file merging)

I keep solving variations of this problem at work, whether I'm trying to merge some log files together, or identify token offsets with bits of parse tree. I had better jot it down so that I don't forget there may be something more general hidden behind all this.

mergeFoo :: [a] -> [(Int,Int,b)] -> [Either a ([a],b)]




I'm not necessarily looking for a solution -- I could just boil one out from my previous solutions -- but I am at least officially and publicly reminding myself that I shouldn't keep solving the same thing over and over again (unless I'm engaged in some kind of lateral thinking exercise, which is a different story)


8 comments:

Christophe Poucet said...

Hello,

Out of curiousity, what is the 'Either a' part of the result? I get the (Int, Int, b). You're basically selecting a subrange of the list, right? But what is the 'Either a'?

kowey said...

Oh, that's the bits that aren't pointed to by anything. Come to think of it, maybe a better formulation is [(a, Maybe b)] with singleton list + Nothing...

kowey said...

Err, [([a], Maybe b)]

Christophe Poucet said...

Hmm,

See by changing the type you completely changed the interface. A priori, with the original type I thought you'd get one list element per (Int, Int, b) element. Now from your explanation I gather that is no longer the case. That does leave me some questions, however.

What if you have two (Int, Int, b)'s pointing to overlapping ranges?

kowey said...

Oh no! I hadn't thought of that. I think the thing to do there is just error and blow up (i.e. assume there are no overlaps).

We're basically zipping two lists together, except that the second part of the zip isn't really a list but something that points to parts of the list... wait, maybe that made no sense. I think I'm being over-visual here.

kowey said...

The basic picture is to think of it as taking the original list and "annotating" it. It's sort of a cross between a zip and a groupBy

BlackMeph said...

Okay, I put a "Publish" order on my module, on Google DOcuments - it's available at:http://docs.google.com/Doc?id=ddgstkpp_187c8vxh4d2

kowey said...

Haha, thank-you! I'm a little too brain dead to look at this right now, but next time I encounter this problem, I'll think of you :-)