An alternative definition for Data.List.groupBy

10/02/2010

The function groupBy from haskell’s standard library is defined in terms of span, the effect being that the supplied predicate function is used to compare the first element of a group with successive elements.

This isn’t clear from the docs, and you might try to do this and wonder at the output you got:

*Main> groupBy (< =) [3,4,5,3,2,1,4,4,1,1,2,3,4,5,4,5,6,7]
[[3,4,5,3],[2],[1,4,4,1,1,2,3,4,5,4,5,6,7]]

Read the rest of this article »

3 Comments

The Definition of Data.List.group

6/02/2010

I’ve been thinking quite a bit lately about a category of functions that are always a bit awkward to define: they involve cases where we would like to traverse a recursive data structure and do something with the data that we have passed over but which is “gone now”.
Read the rest of this article »

No Comments

Find a permutation given its Inversion Table

15/11/2009

Here is some code I whipped up in response to an interesting problem posted on reddit.com/r/coding/. It was a really interesting algorithm to work out:



import Data.List (sortBy)

-- takes an inversion list and converts it to the list of permuted
-- elements:
decode = dec [] . sortBy lowHi . zip [1..]  where
    dec as []         = as
    dec as ((a,_):is) = let is' = sortBy lowHi (decrementGT a is)
                         in dec (a:as) is'

-- decrement every inversion number by 1, for every tuple in which
-- the element is greater than `a`:
decrementGT a = map (\(a',i) -> (a', if a'>then i-1 else i) )

-- we sort by the inversion number, low to high. For elements with
-- the same inversion number, we say that the greater element tuple
-- should go before a lesser element:
lowHi (a,i) (a',i') 
    | i == i'   = if a>a' then LT else GT
    | otherwise = compare i i'

It’s not the prettiest code I’ve written, but it’s pretty straight-forward and concise. Thanks for looking!

No Comments