Monad instance of a number-parameterised vector?

Question

Statically sized vectors in Haskell are shown in Oleg Kiselyov's Number-parameterized types and can also be found in the Data.Param.FSVec type from the parameterized-data module on Hackage:

data Nat s => FSVec s a

FSVec is not an instance of the Monad type class.

The monad instance for lists, can be used to remove or duplicate elements:

Prelude> [1,2,3] >>= \i -> case i of 1 -> [1,1]; 2 -> []; _ -> [i]
[1,1,3]

Whether similar to the list version or not, is it possible to construct a monad from a fixed length vector?

Edward Kmett Edward Kmett · Accepted Answer · 2011-04-27T12:43:05

Yes it is possible, if not natural.

The monad has to 'diagonalize' the result in order to satisfy the monad laws.

That is to say, you can look at a vector as a tabulated function from [0..n-1] -> a and then adapt the monad instance for functions.

The resulting join operation takes a square matrix in the form of a vector of vectors and returns its diagonal.

Given

tabulate :: Pos n => (forall m. (Nat m, m :<: n) => m -> a) -> FSVec n a

then

instance Pos n => Monad (FSVec n) where
     return = copy (toNum undefined)
     v >>= f = tabulate (\i -> f (v ! i) ! i)

Sadly uses of this monad are somewhat limited.

I have a half-dozen variations on the theme in my streams package and Jeremy Gibbons wrote a blog post on this monad.

Equivalently, you can view a FSVec n as a representable functor with its representation being natural numbers bounded by n, then use the definitions of bindRep and pureRep in my representable-functors package to get the definition automatically.

Monad instance of a number-parameterised vector?

3 Answers