While playing around with generalized functional references I encountered the following list-like data type:
data FunList a b = Done b | More a (FunList a (a -> b))
This is a non-regular data type, meaning that inside the FunList a b there is a FunList a not-b. So, what does a value of this type look like? Well, it can be
We either have just b, or an a and a function a->b, or two as (i.e. a2) and a function a2->b, or a3 and a3->b, etc.
A FunList a b is therefore a list of as together with a function that takes exactly that number of as to give you a b. Extracting the single represented b value is easy:
getB :: FunList a b -> b getB (Done b) = b getB (More a z) = getB z a
As is getting to the list of as:
getAs :: FunList a b -> [a] getAs (Done _) =  getAs (More a z) = a : getAs z
But then things quickly get much trickier. Since a FunList a b holds exactly one b, we might ask how much access we have to it. First of, FunList a is a Functor, so the b value can be changed:
instance Functor (FunList a) where fmap f (Done b) = Done (f b) fmap f (More a z) = More a (fmap (f .) z)
The above case for More looks a bit strange, but remember that the data type is non-regular, so we recurse with a different function f. In this case instead of having type b -> c as the outer f does, we need something with type (a -> b) -> (a -> c).
The Applicative instance is even stranger. There is a flip there, where the heck did that come from?
instance Applicative (FunList a) where pure = Done Done b <*> c = fmap b c -- follows from Applicative laws More a z <*> c = More a (flip <$> z <*> c) -- flip??
Aside from manipulating the b value we can also do more list like things to the list of as, such as zipping:
zipFun :: FunList a b -> FunList c d -> FunList (a,c) (b,d) zipFun (Done b) d = Done (b,getB d) zipFun b (Done d) = Done (getB b,d) zipFun (More a b) (More c d) = More (a,c) (applyPair <$> zipFun b d) where applyPair (f,g) (x,y) = (f x,g y)
Surprisingly, the applicative operator defined above can be used as a kind of append, just look at the type:
(<*>) :: FunList a (b -> c) -> FunList a b -> FunList a c
it takes two 'lists' and combines them into one. It is indeed true that getAs a ++ getAs b == getAs (a <*> b).
This is as far as I got, so I will end this post with a couple of challenges: