[Haskell-cafe] Reinvention

[Andrew Coppin]

I seem to be forever writing code that looks like this:

decode :: String -> (SKI,String)
decode (c:cs) = case c of
  'S' -> (S,cs)
  'K' -> (K,cs)
  'I' -> (I,cs)
  '*' -> let (e0,cs0) = decode cs; (e1,cs1) = decode cs1 in (e0 :@: e1, cs1)

In other words, lots and lots of functions with signatures like

  foo :: [Foo] -> (Bar,[Foo])

that likes to call itself recursively, or that gets called from 
somewhere else.

Is there a Better Way(tm) to do this? It looks like such a common idiom 
that you'd expect to see "something" in the libraries somewhere.

(I remember being puzzled that there was no library function for 
creating a Cartesian product of two lists. Puzzled until I realised that 
the monadic nature of lists make it utterly trivial to do this by hand 
anyway! So it's not always obvious to know what you're looking for...)