# Recursion scheme in Haskell for repeatedly breaking datatypes into "head" and "tail" and yielding a structure of results

In Haskell, I recently found the following function useful:

listCase :: (a -> [a] -> b) -> [a] -> [b] listCase f [] = [] listCase f (x:xs) = f x xs : listCase f xs

I used it to generate sliding windows of size 3 from a list, like this:

*Main> listCase (\_ -> take 3) [1..5] [[2,3,4],[3,4,5],[4,5],[5],[]]

Is there a more general recursion scheme which captures this pattern? More specifically, that allows you to generate a some structure of results by repeatedly breaking data into a "head" and "tail"?

## Answers

This looks like a special case of a (jargon here but it can help with googling) paramorphism, a generalisation of primitive recursion to all initial algebras.

##### Reimplementing ListCase

Let's have a look at how to reimplement your function using such a combinator. First we define the notion of paramorphism: a recursion principle where not only the result of the recursive call is available but also the entire substructure this call was performed on:

The type of paraList tells me that in the (:) case, I will have access to the head, the tail and the value of the recursive call on the tail and that I need to provide a value for the base case.

module ListCase where paraList :: (a -> [a] -> b -> b) -- cons -> b -- nil -> [a] -> b -- resulting function on lists paraList c n [] = n paraList c n (x : xs) = c x xs $ paraList c n xs

We can now give an alternative definition of listCase:

listCase' :: (a -> [a] -> b) -> [a] -> [b] listCase' c = paraList (\ x xs tl -> c x xs : tl) []

##### Considering the general case

In the general case, we are interested in building a definition of paramorphism for all data structures defined as the fixpoint of a (strictly positive) functor. We use the traditional fixpoint operator:

newtype Fix f = Fix { unFix :: f (Fix f) }

This builds an inductive structure layer by layer. The layers have an f shape which maybe better grasped by recalling the definition of List using this formalism. A layer is either Nothing (we're done!) or Just (head, tail):

newtype ListF a as = ListF { unListF :: Maybe (a, as) } type List a = Fix (ListF a) nil :: List a nil = Fix $ ListF $ Nothing cons :: a -> List a -> List a cons = curry $ Fix . ListF .Just

Now that we have this general framework, we can define para generically for all Fix f where f is a functor:

para :: Functor f => (f (Fix f, b) -> b) -> Fix f -> b para alg = alg . fmap (\ rec -> (rec, para alg rec)) . unFix

Of course, ListF a is a functor. Meaning we could use para to reimplement paraList and listCase.

instance Functor (ListF a) where fmap f = ListF . fmap (fmap f) . unListF paraList' :: (a -> List a -> b -> b) -> b -> List a -> b paraList' c n = para $ maybe n (\ (a, (as, b)) -> c a as b) . unListF listCase'' :: (a -> List a -> b) -> List a -> List b listCase'' c = paraList' (\ x xs tl -> cons (c x xs) tl) nil

You can implement a simple bijection toList, fromList to test it if you want. I could not be bothered to reimplement take so it's pretty ugly:

toList :: [a] -> List a toList = foldr cons nil fromList :: List a -> [a] fromList = paraList' (\ x _ tl -> x : tl) [] *ListCase> fmap fromList . fromList . listCase'' (\ _ as -> toList $ take 3 $ fromList as). toList $ [1..5] [[2,3,4],[3,4,5],[4,5],[5],[]]

What you are asking for is a **comonad**. This may sound scarier than *monad*, but is a simpler concept (YMMV).

Comonads are Functors with additional structure:

class Functor w => Comonad w where extract :: w a -> a duplicate :: w a -> w (w a) extend :: (w a -> b) -> w a -> w b

(extendand duplicate can be defined in terms of each other) and laws similar to the monad laws:

duplicate . extract = id duplicate . fmap extract = id duplicate . duplicate = fmap duplicate . duplicate

Specifically, the signature (a -> [a] -> b) takes non-empty Lists of type a. The usual type [a] is not an instance of a comonad, but the non-empty lists are:

data NE a = T a | a :. NE a deriving Functor instance Comonad NE where extract (T x) = x extract (x :. _) = x duplicate z@(T _) = T z duplicate z@(_ :. xs) = z :. duplicate xs

The comonad laws allow only this instance for non-empty lists (actually a second one).

Your function then becomes

extend (take 3 . drop 1 . toList)

Where toList :: NE a -> [a] is obvious. This is worse than the original, but extend can be written as =>> which is simpler if applied repeatedly.

For further information, you may start at What is the Comonad typeclass in Haskell?.

### Need Your Help

### Setting Form.Owner to a form from a different thread

My application (C#, VS2008) loads information from a database (SQL Server 2008 Express) over the network. During (possibly) longish waits, I want to have a 'Loading...' dialog box appear running on a### Convert string to doubles in C

c type-conversion dynamic-programming dynamic-memory-allocation

I'm about to implement a dynamic matrix structure (that stores double values) and I got some problems with reading from a file.