Haskell snippet – getPrefixMap

Here's a little snippet I worked on yesterday, while preparing my talk for the London Perl Workshop.
It takes a list of tuples ("string", whatever) and maps all the prefixes of the string
("string", "strin", "stri", etc.) to the whatever.

I was quite impressed at how easily this came together.  The functional composition (pipelines connected with ".") is coming a bit more easily, but the heavy lifting is all done really by the "inits" function from Data.List.

Some of this is made "prettier" (but harder to understand) by various features.  "uncurry" changes a function that takes a tuple (a,b) into one that takes 2 arguments "a b".  The (flip (,) r) is actually harder to read than the equivalent lambda, (\s -> (s,r)).  (Annoyingly, you can't section the comma operator to do "(,r)" because tuples are "special"…)

import Data.Listimport qualified Data.Map as M

-- can contain duplicates!getPrefixes :: [([a], t)] -> [([a], t)]getPrefixes = concatMap (uncurry gps)    where gps s r = map (flip (,) r)  -- make a tuple (s',r)                     . reverse        -- shortest prefixes last                     . tail           -- ignore the empty prefix ""                     . inits          -- get all the prefixes                     $ s

getPrefixMap :: (Ord a) => [([a], t)] -> M.Map [a] tgetPrefixMap = M.fromList . getPrefixes

-- without the type, we'd have to write like so (because of the -- monomorphism restriction)-- > getPrefixMap xs = M.fromList $ getPrefixes xs

Update: after Joao's comments below, I got the version

 > getPrefixes :: [([a], t)] -> [([a], t)] > getPrefixes = concatMap gps >    where gps (s, r) = let ss = tail . inits $ s >                           rs = repeat       $ r >                       in zip ss rs

Joao meanwhile mentioned the cross product, which I didn't immediately get the point of.

 > infix 1 >< > (><) f g a = (f a, g a)

As you can see, this applies the remaining parameter "a" to two functions.  So it's useful in this case to curry the "(s,r)" parameter.  doserj pointed out that this is spelt (&&&) so that we just need to:> import Control.Arrow> getPrefixes = concatMap $ uncurry zip . >                         (tail . inits . fst &&& repeat . snd)

As often happens in Haskell you could argue whether this is actually any clearer, but it's cute!