# 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"?

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).

```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

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).

```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?.