Listable
Listable is a module which contains the Listable class. The Listable class allows a user to create instances of types which can be treated as lists. Given a minimal description:
- takeL :: Integer -> m -> m
- dropL :: Integer -> m -> m
- cons :: m -> m -> m
- (+++) :: m -> m -> m
- unit :: m
one gets the following functions for free:
- filterL :: (m -> Bool) -> m -> m
- (!!!) :: m -> Integer -> m
- lengthL :: m -> Integer
- reverseL :: m -> m
- headL :: m -> m
- tailL :: m -> m
Notice below that each of the Free functions are defined in terms of the required ones.
By indenting these definitions, placing them under the class banner, the haskell compiler expects the function definitions to be self-contained and defined purely in terms of the Listable class and standard functions given by Prelude. Additionally, Listable demands that its instances be comparable via the Equality class, Eq. Without being able to compare two values, there is no way to identify when a base case, unit, is reached. lengthL and reverseL rely upon this in their recursion.
class Eq m => Listable m where
takeL :: Integer -> m -> m
dropL :: Integer -> m -> m
cons :: m -> m -> m
(+++) :: m -> m -> m
unit :: m
(!!!) :: m -> Integer -> m
lengthL :: m -> Integer
reverseL :: m -> m
headL :: m -> m
tailL :: m -> m
headL = takeL 1
tailL = dropL 1
(!!!) ls n = headL.dropL n $ ls
lengthL ls | unit == ls = 0
| otherwise = 1 + (lengthL.dropL 1) ls
reverseL ns = ff ns unit
where
ff ns accum | ns == unit = accum
| otherwise = ff (tailL ns) $ headL ns `cons` accum
filterL b ns = f b ns unit
where
f b js accum | js == unit = accum
| (b.headL) js = f b (tailL js) $ headL js +++ accum
| otherwise = f b (tailL js) accum
Now for some instances. Since [a] is essentially the defacto model of our class, it seems most obvious to begin with this instance. Above, the Listable type of cons is slightly different than one usually expects for (:).
Here, cons is constrained as: cons :: m -> m -> m
where (:) is usually constrained as: (:) :: a -> [a] -> [a].
This difference will ultimately have an impact on how a Listable cons behaves.
instance Eq a => Listable [a] where
dropL = drop.fromIntegral
takeL = take.fromIntegral
cons [n] ns = n : ns -- wrap the left argument with [].
(+++) = (++)
unit = []
[2] `cons` dropL 3 [1..9]
Next, something less trivial. We can in fact treat numbers of type Integer as Listable as well. Best of all, all one needs to do is write instances for the necessary functions: takeL, dropL, cons, (+++) and unit.
instance Listable Integer where
(+++) ns ms = ns * 10^lengthL ms + ms
dropL n zs = div zs (10^n)
takeL n zs = mod zs (10^n)
cons n ns = ns * 10 + n
unit = 0
2 `cons` dropL 3 987654321
It is probably worth mentioning that the Listable behavior of [a] and of Integer are noticeably different. Listable treats an Integer type as a list whose order is opposite to the order of a Listable [a]. This choice is arbitrary in that the Integer instance could likely have been written so that the two types have the same direction, though I am not entirely sure how to do it purely arithmetically. Additionally note, that since zero is defined as the monoidal unit, it behaves more similarly to [] than it does to the actual number 0.
[takeL 1 1000002 == reverseL 20, lengthL 0 == lengthL 1]
Jonathan Zingale 