anaMap and accumMapL

There has been a very long thread recently on Haskell-Cafe -
- 'about Haskell code written to be "too smart"':
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058475.html

As the thread was running the idea of partitions (aka takeList) seemed like an unfold to me, though I couldn't work out a nice formulation. Here is the best 'natural' unfold I could get. It's messier than a usual anamorphism because the state has to be doubled - the state is both the list of lengths and the remaining stream:

anapart :: [Int] -> [a] -> [[a]]
anapart = (unfoldr phi .) . (,) where
  phi ([],_)    = Nothing
  phi (i:is,xs) = let (l,r) = splitAt i xs in Just (l,(is,r))

Prompted by the suggesting that mapAccumL was the natural way to do it, Claus Reinke noted that that the arguments to mapAccumL were the wrong way round:
http://www.haskell.org/pipermail/haskell-cafe/2009-March/058689.html


Here is a version accumMapL which puts the state second in the result tuple - which is the way unfoldr (anamorphism) does it:

accumMapL :: (a -> st -> (b, st)) -> st -> [a] -> ([b], st)
accumMapL _ s []        =  ([],s)
accumMapL f s (x:xs)    =  (y:ys,s'')
                           where (y, s')  = f x s
                                 (ys,s'') = accumMapL f s' xs

Since mapAccumL (accumMapL) is like a fusion of map and foldl, it made me wonder what a a combination of map and unfoldr would give me as I was still keen on my anamorphism, maybe anaMap isn't the best name, but I think this function is the analogue:

-- anaMap is to unfoldr, what accumMapL is to foldl
-- Note - we can signal exhaustion early by the Maybe type.               

anaMap  :: (a -> st -> Maybe (b,st)) -> st -> [a] -> ([b],st)
anaMap f s []     = ([],s)    
anaMap f s (x:xs) = case (f x s) of
    Nothing       -> ([],s)
    Just (a,st)   -> (a:as,st') where (as,st') = anaMap f st xs

And here is takeList:

takeListAM :: [Int] -> [t] -> [[t]]
takeListAM ns xs = fst $ anaMap fn xs ns where
  fn _    [] = Nothing
  fn i    ys = Just $ splitAt i ys

Finally here's the GHC transcript, it passes the Hartman test:

*Main> main
[[1,2,3],[4,5,6,7,8,9,10]]
[[1,2,3],[4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20,21],[22,23,24,25,26,27,28,29,30,31,32,33,34
,35,36]]
1000000
*Main> null $ takeListAM [1] undefined
*** Exception: Prelude.undefined
*Main> takeListAM [0] []
[]
*Main>

By the way, I do like the 'specs' (aka glasses) combinator to compose a binary function and a ternary one. The function anapart above, used the double composition idiom which now seems very common - here's the line in question:

anapart = (unfoldr phi .) . (,) where
  ...

Here is is with 'specs':

anapart = unfoldr phi `oo` (,) where
  ...

Specs has a nod to ML which uses letter o for function composition, plus the '2 o's' seem like a nice visual pun to suggest doubling going on in the composition:

oo :: (c -> d) -> (a -> b -> c) -> a -> b -> d
oo f g = (f .) . g

Of course higher arities can also be accommodated:

ooo :: (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e
ooo f g = ((f .) .) . g

etc.