fixed-list-0.1.5: A fixed length list type




A fixed length list library.

The length of a list is encoded into its type in a natural way. This allows you to do things like specify that two list parameters have the same type, which also forces them to have the same length. This can be a handy property. It's not as flexible as the standard haskell list, but the added type safety is sometimes worth it.

The entire library is Haskell98 except for the Append typeclass. (which could be easily removed if needed).

Most of your usual list functions (foldr, fmap, sum, sequence, etc..) are accessed via the Functor, Applicative, Foldable, and Traversable type classes.

The Equivalent of zipWith can be had via the Applicative instance:

 zipWith f xs ys = pure f <*> xs <*> ys

Also, sequenceA transposes a FixedList of FixedLists.

The monad instance is also interesting. return fills the list with the given element (remember that list size is dependent on the type) You can think of bind as operating like this:

 m >>= k = diagonal $ fmap k m

This takes the FixedList m and maps k accross it, (which must return a FixedList) which results in a FixedList of FixedLists the diagonal of which is returned. The actually implementation is more elegant, but works essentialy the same.

This also means that join gets the diagonal of a FixedList of FixedLists.

You can construct FixedLists like so:

 t1 :: Cons (Cons (Cons Nil)) Integer -- this is the same as FixedList3 Integer
 t1 = 1 :. 3 :. 5 :. Nil

 t2 :: FixedList3 Integer  -- type signature needed! and must be correct!
 t2 = fromFoldable' [4, 1, 0]

 t3 :: FixedList3 Integer -- type signature needed!
 t3 :: fromFoldable' [1..]

 t4 :: FixedList3 (FixedList3 Integer)
 t4 = t1 :. t2 :. t3 :. Nil

 -- get the sum of the diagonal of the transpose of t4
 test :: FixedList3 Integer
 test = sum $ join $ sequenceA $ t4

If you want to restrict a type to be a FixedList, but don't want to specify the size of the list, use the FixedList typeclass:

 myFunction :: (FixedList f) => f a -> Float

On a side note... I think that if Haskell supported infinite types my Append typeclass would only have one parameter and I wouldn't need all those nasty extensions.

I think I could also implement direct, typesafe, versions of last, init, reverse and length that don't depend on Foldable. *sigh* Maybe Haskell will one day support such things.

This library is hosted on github (click on the Contents (if you are viewing this on hackage) link above and you should see the Homepage link) so it should be very easy to forked it, patch it, and send patches back to me.


Types and Classes

data FixedList f => Cons f a Source




head :: a
tail :: f a


FixedList f => Monad (Cons f) 
FixedList f => Functor (Cons f) 
FixedList f => Applicative (Cons f) 
FixedList f => Foldable (Cons f) 
FixedList f => Traversable (Cons f) 
FixedList f => FixedList (Cons f) 
(FixedList f, FixedList c, Append f b c) => Append (Cons f) b (Cons c) 
(Eq a, Eq (f a), FixedList f) => Eq (Cons f a) 
(Fractional a, FixedList f, Eq (f a), Show (f a)) => Fractional (Cons f a) 
(Num a, FixedList f, Eq (f a), Show (f a)) => Num (Cons f a) 
(Ord a, Ord (f a), FixedList f) => Ord (Cons f a) 
(FixedList f, Show a) => Show (Cons f a) 

data Nil a Source



class (Applicative f, Traversable f, Monad f) => FixedList f Source

Just a restrictive typeclass. It makes sure :. only takes FixedLists as it's second parameter and makes sure the use of fromFoldable's in reverse, and init is safe.


class Append f g h | f g -> h, f h -> g whereSource


append :: f a -> g a -> h aSource


Append Nil a a 
(FixedList f, FixedList c, Append f b c) => Append (Cons f) b (Cons c) 

Baisc Functions that are not found in Traversable or Foldable

reverse :: FixedList t => t a -> t aSource

length :: Foldable t => t a -> IntSource

last :: Foldable t => t a -> aSource

Returns the last element of the list

init :: FixedList f => Cons f a -> f aSource

Returns all but the last element of the list

unit :: a -> Cons Nil aSource

Constructs a FixedList containing a single element. Normally I would just use pure or return for this, but you'd have to specify a type signature in that case.

subLists :: FixedList f => Cons f a -> Cons f (f a)Source

Given a list, returns a list of copies of that list but each with an element removed. for example:

 subLists (1:. 2:. 3:. Nil)



fromFoldable :: (Foldable f, Applicative g, Traversable g) => f a -> Maybe (g a)Source

Converts any Foldable to any Applicative Traversable. However, this will only do what you want if pure gives you the shape of structure you are expecting.

fromFoldable' :: (Foldable f, Applicative g, Traversable g) => f a -> g aSource

This can crash if the foldable is smaller than the new structure.

Type synonyms for larger lists