CODEWITHSUNDEEP
haskell
user3277633
user3277633

Reputation: 1923

Doing computation on tuples within a list in Haskell

Given 

data Allocation = 
    Alloc [(Var, Register)]
    deriving (Eq, Show)

instance Ord Allocation where
     Alloc a < Alloc b = .......

I want to see if one Allocation is better than another Allocation if Alloc a has fewer distinct registers than Alloc b.

I have a few methods/strategies that I think I can use, but not sure how to string them together.

snd can take the register out from the (Var, Register) tuple.
nub can remove the duplicates within a list
length for the length of the list
intersect to find the intersection between two lists

Attempt to extract the registers from (Var, Register) tuple for both Alloc a and Alloc b. Maybe find the intersection of the two lists, remove them from both lists, and compare the length of the remaining. If length a is greater than length b, a is the better one. Otherwise, it's b.

Am I overthinking this, or am I somehow on the right track?

Edit: Below is my attempt

helper :: Allocation -> [Register]
     helper (Alloc a) = nub (map snd a)

instance Ord Allocation where
    Alloc a < Alloc b = length (helper a - (helper a `intersect` helper b)) < length (helper b - (helper a `intersect` helper b))

So my helper works, but now the question is how do I delete a list from a list so that a will delete everything that is the intersection of a and b and b will do the same.

Upvotes: 0

Views: 143

Answers (1)

icktoofay
icktoofay

Reputation: 129119

There’s a good chance I’m misunderstanding, but I think you might be overcomplicating it. Each allocation is a list of pairs of variables and registers, and the number of distinct registers used by an allocation is independent of the allocation it’s being compared with. As such, I’m not sure I understand why you’re doing an intersection.

If I’m understanding what you’re trying to do correctly, the most concise way to define the Ord instance would be like this:

instance Ord Allocation where
  compare = comparing (length . nub . map snd . assignments)
    where assignments (Allocation a) = a

Here, we, for each operand of compare:

  • Extract the assignments from the allocation.
  • Extract the registers from each assignment.
  • Remove the duplicate registers.
  • See how many registers are left.

Then we compare those two numbers, determining which is better that way. If you aren’t allowed to use comparing, you could just inline its relatively-short definition.

Upvotes: 1

Related Questions