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

# Best How To :

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],[]]
```