On Thu, 23 Dec 2010, C K Kashyap wrote:
Here's my attempt to convert a list of integers to a list of range tuples -
Given [1,2,3,6,8,9,10], I need [(1,3),(6,6),8,10)]
That's an interesting problem!
My first attempt:
List.unfoldr (\xs -> case xs of [] -> Nothing; y:ys -> case span (uncurry (==)) $
zip xs [y..] of (matching, remainder) -> Just ((y, fst $ last matching), map fst
remainder)) [1,2,3,6,8,9,10]
[(1,3),(6,6),(8,10)]
However, the use of 'last' will course a memory leak for long ranges, and
the (map fst remainder) reconstructs the remainder of the list, and thus
needs linear time instead of constant one.
Here is my second attempt, developed in GHCi and variable names that
should be improved ...
List.unfoldr (\xs -> case xs of [] -> Nothing; y:ys -> case dropWhile (\(a,b,t) -> case
t of [] -> False; h:_ -> a==h) $ zip3 [y+1..] xs (List.tails ys) of ~((_, end, remainder):_)
-> Just ((y, end), remainder)) [1,2,3,6,8,9,10]
Using zip3 I have bundled all information that I need after 'dropWhile' in
order to proceed: The end of the current range and the remaining numbers.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
