My friend Tim had a programming problem, described at his joint.

I thought about the problem for a while, started implementing it in ruby, thought “I could implement this better in haskell”, so I did:

group_seq :: (Int -> Bool) -> [Int] -> [[Int]]
group_seq pred [] = []
group_seq pred (x:xs)
  | pred x    = let (group, rest) = span pred (x:xs)
                in group:(group_seq pred rest)
  | otherwise = ([x]):(group_seq pred xs)

Then I implemented it in ruby:

class Array             
  def group_sequential
    result = [] 
    i = 0       
    while i < length
      group = [self[i]] 
      i += 1            
      if yield self[i-1]
        while i < length && (yield self[i])
          group << self[i]              
          i += 1                        
        end                     
      end               
      result << group   
    end         

    return result
  end   
end  

And I thought, that would be much nicer if we had a enumerator interface with a “get next” and a “current value” method. Ruby doesn’t give us these toys, as far as I can see, but we can simulate them for a small dataset by doing Array.dup, then arr.shift is “move to next and return last” and “arr.first” is “current value”:

class Array
  def group_sequential
    arr = self.dup
    result = [] 
    while arr.first
      group = [arr.first]
      if yield arr.shift
        group << arr.shift while arr.first && (yield arr.first)
      end               
      result << group   
    end         

    return result
  end   
end

And that one feels pretty good to me… It feels like it’d be nicer in a language with an iterator interface of the right sort. Hey, python has one of those, more or less, let’s try that.

def group_sequential(arr, pred):
        iterator = iter(arr)
        result = []
        group = []
        value = iterator.next()
        try:    
                while True:
                        group = [value]
                        lastvalue, value = value, iterator.next()
                        try:    
                                while pred(lastvalue) and pred(value):
                                        group.append(value)
                                        value = iterator.next()
                        except:
                                pass
                        result.append(group)
        except: 
                result.append(group)
        return result

And that one feels completely dreadful! Not being able to interrogate the iterator for the current value makes things a bit awkward.

I’m not entirely happy with any of them. Wanting to go back to the drawing board, I translated the functional one fairly directly into Ruby, hoping to get beautiful code at the cost of weird performance characteristics:

class Array
  def group_sequential(&block)
    return [] if empty?
    return [self] if length == 1 
    rest = self[1..-1].group_sequential(&block)
    if (yield self.first) && (yield rest.first.first)
      rest.first.unshift(self.first)
    else        
      rest.unshift([self.first])
    end         
    rest        
  end   
end

Which is possibly the best yet, although it’s very strange-looking for ruby code. But I don’t like any of them, really.

In conclusion, I Don’t Know.

• Uncategorized