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)
at

8 comments:

  1. Christophe Poucet14 May, 2008 19:00

    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'?

    ReplyDelete
  2. kowey14 May, 2008 19:03

    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...

    ReplyDelete
  3. kowey14 May, 2008 19:04

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

    ReplyDelete
  4. Christophe Poucet14 May, 2008 19:11

    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?

    ReplyDelete
  5. kowey14 May, 2008 19:18

    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.

    ReplyDelete
  6. kowey14 May, 2008 19:19

    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

    ReplyDelete
  7. BMeph16 May, 2008 19:54

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

    ReplyDelete
  8. kowey16 May, 2008 23:23

    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 :-)

    ReplyDelete