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]]
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'>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!
Here is a quick post to get me back into the swing of blogging:
I was looking through an old post on StackOverflow about clever functional code, and the best answer, given by “yairchu” was a nice version of the Burrows-Wheeler Transform, which is an algorithm for permuting a string such that it can be compressed more effectively by other algorithms. The code posted was (import Data.List assumed):
bwp :: (Ord a)=> [a] -> [a]
bwp xs = map snd $ sort $ zip (rots xs) (rrot xs)
rots xs = take (length xs) (iterate lrot xs)
lrot xs = tail xs ++ [head xs]
rrot xs = last xs : init xs
I saw I could improve/shorten this in a couple of obvious ways and came up with this:
bwp :: (Ord a) => [a] -> [a]
bwp = map snd . sort . rots
rots xs = zip (tail $ iterate lrot xs) xs
lrot (x:xs) = xs ++ [x]
Still unsatisfied and even more obsessed I came up with this final, prettiest version, before forcing myself to give it up already:
bwp :: (Ord a)=> [a] -> [a]
bwp = map snd . sort . rots
rots xs = zip (lrot xs) xs
lrot = tail . tails . cycle
Unfortunately, this last version will croak if your string happens to look like “111111″ or “cAbcAb” because sort will keep trying to compare infinites lists.
Update: I did a short post on the Move To Front transform as a follow-up to this post.
