Listable

 

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.

In [1]:
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.

In [2]:
instance Eq a => Listable [a] where
  dropL = drop.fromIntegral
  takeL = take.fromIntegral
  cons [n] ns = n : ns -- wrap the left argument with [].
  (+++) = (++)
  unit = []
In [3]:
[2] `cons` dropL 3 [1..9]
[2,4,5,6,7,8,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.

In [19]:
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
In [20]:
2 `cons` dropL 3 987654321
9876542

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.

In [37]:
[takeL 1 1000002 == reverseL 20, lengthL 0 == lengthL 1]
[True,False]

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s