Life by Comonads: 2

{-# LANGUAGE DeriveFunctor #-}

In the last post we developed an intuition about comonads which we will now put to use.
So comonads allow us calculate values that are the focus within some context.
The extend function allows us to uniformly apply this computation across all values in the comonad as though they had the focus.

One example of a context dependent calculation is Pascals triangle. A value at the next level is the sum of itself and an adjacent value.

List Zipper

Before we go any further we're going to develop another interesting comonadic structure, a zipper over a stream. The zipper has as its focus some element and extends infintely in both directions. Thus our zipper consists of a stream that extends infinitely in the left direction, the current focus and a list that extends infinitely in the right direction.

import Control.Comonad

data LZip a = LZip [a] a [a] deriving (Eq, Ord, Show, Functor)

We want to be able to move around in the structure; we develop two utility functions,

shiftL :: LZip a -> LZip a

shiftL (LZip l a r) = LZip (tail l) (head l) (a:r)

This moves the focus to the left pushing the current value to the left.

shiftR :: LZip a -> LZip a

shiftR (LZip l a r) = LZip (a:l) (head r) (tail r)

This moves the focus to the right pushing the current value to the left.

So this zipper has an element it focuses on, and has a context (its position in the stream).
The comonadic instance is:

instance Comonad LZip where

   extract (LZip _ a _) = a

Extract gives us the current focus in the zipper.

Duplicate has to give us a LZip (LZip a). That structure gives us a stream of parallel streams.
After duplicate the structure that we obtain is such that, the stream that is focused on as we move to the right is the original stream shifted to the right and vice versa for the left.

   duplicate z@(LZip l v r)

       = LZip left z right

         where

           left = tail $ iterate shiftL z

           right = tail $ iterate shiftR z

Pascals Triangle

If we represent one layer of Pascals triangle as an infinite stream focused on some relevant location, the step function to compute the value at the cell for next layer in the triangle is the sum of itself and its left/right neighbor:

addLeft :: LZip Int -> Int

addLeft z = extract z + extract (shiftL z)

Now the triangle is a 2D object which we can represent by parallel layers. Duplicate allows us to create these parallel layers. Now the step function to create the next layer in the triangle is simply:

nextLayer :: LZip (LZip Int) -> LZip Int

nextLayer = extend addLeft . extract . shiftL

Finally, the triangle itself consists of the initial value to kick start the process while the successive layers are the result of extending using 'nextLayer'.

pTri :: LZip (LZip Int)

pTri = LZip (repeat all0s) gen right

    where 

      (_:right) = map nextLayer $ iterate shiftR pTri

      all0s = LZip (repeat 0) 0 (1:repeat 0)

      gen = LZip (repeat 0) 1 (repeat 0)

And that's all there is to it. The next we would want to do is crop an area of interest. For a one dimensional zipper we have:

crop :: Int -> LZip a -> [a]

crop n z = (reverse $ map extract left) ++ (focus:map extract right)

    where 

      left = take n (tail $ iterate shiftL z)

      right = take n (tail $ iterate shiftR z)

      focus = extract z

Extending this to the two dimensional case is simple, we crop along the second dimesion, and along each of the firsts thus generated:

crop2D :: Int -> LZip (LZip Int) -> [[Int]]

crop2D n = map (crop n) . crop n

And that's it, Pascals triangle using comonads. The takeaway is that comonads allow us to use a context around a value to determine a result as opposed to monads which focus on creating context from some values. 

Life by Comonads: 1

Intro

Why did the chicken cross the Mobius Strip? 

 - To get to the same side

Prepping the Intuition

Comonads are the categorical duals are monads. So it pretty much means we have to reverse the notions that persist related to monads.

Well, from a computational perspective, monads allow us to:

• Execute actions using  some input, producing an output wrapped in a context. Functions of the form a -> m b. 
• Allow us to use the results of previous computations as inputs to further actions that produce some more context and subsequently resolve the nested contexts into a single context (>>=), in a sensible manner; for a sequence of actions the order in which we resolve the contexts is irrelevant a.k.a. the monad laws.

Thus in some sense the opposite of the above intuitions gives: 

• Comonads allow us to consume values wrapped in a context producing some output, values for the form (w a -> b). 
• Duplicate a context and extract a value from the inner context such that using extract on the inner context yeilds the original comonadic value:   A function of the form = (w a -> b) -> w a -> w b
• We invert the 'm' to get a 'w' for type-constructor variables

Comonad Instances

Looking at the source we see that (e,) and ((->) m) are instances of the Comonad class. 

Now that's the writer and the reader monads except the Monoid constraint is required of the 'reader' comonad.

Let's go ahead and implement them:

instance Comonad (e,) where
  extract (_, a) = a
  duplicate (e, a) = (e, (e, a))
  extend (e, a) f = (e, f (e, a))

The (e,) comonad carries around an e with it. When extracting a value we simply ignore the environment. 

Duplicate, duplicates the environment. But thats exactly what the reader monad does, but in a somewhat opposite sense. That oppositeness is clarified on reversing the arrows for the respective functions.

return' :: a -> r -> a
return' :: a -> r -> a
return' :: r -> a -> a
return' :: (r, a) -> a
extract :: (r, a) -> a

(>>=)' :: m a -> (a -> m b) -> m b
(>>=)' :: w b -> (w b -> a) -> w a
extend :: w b -> (w b -> a) -> w a

While this probably shouldn't be surprising, one has to admire the magnificent machinery of category theory. Something as innocent as looking the other way has divine repercussions. 

Armed with that knowledge we're going in to Monoid m => ((->) m), expecting a Writer monad like behavior. 

instance Monoid m => Comonad ((->) m) where
  extract f = f mempty
  duplicate m f = \w -> \w' -> f (w <> w')
  extend m f = \w -> f (\w' -> m (w <> w'))

Sure enough, we see the same sort've writing behavior but with more emphasis on viewing the result than accumulating. 

Conclusion

So that's pretty cool, reading and writing are duals of each other and in some sense opposite notions which is made formal by their representation as mathematical objects. I always find it fascinating to see mathematics - a pure and exact - describe something I thought was really vague, though granted in the projection we loose some nuances of the concepts.

So while that's helped my understanding of the duality between monads and commands, comonads haven't distinguished themselves apart from being interesting theoretical specimen. They simply appear to be the other side of the same strip. 

Next up, we move on to a real Life algorithm.

Recursion Schemes: Excursion 2

Unfolding:

We're required to implement embed in order to use Unfoldable.
embed puts our base functor into the recursive type.


For a list for example we have:

embed :: Base [a] [a] -> [a]
embed (Cons a l) = a:l
embed Nil = []

And this allows us to infinitely unfold our base functor into the recursive type with an anamorphism.

ana :: Unfoldable t => (a -> Base t a) -> a -> t
ana f = m where m = embed . fmap m . f

The anamorphism is the inverse of the catamorphism. In a catamorphism, we project onto the base functor, then fold the values encased in the functor and then fold the outer. In an anamorphism we unfold once, then use the values inside the functor as seeds for the next unfolds, and then inject it into a recursive type.

The generalized anamorphism is a bit more fun:
gana :: (Unfoldable t, Monad m) => (forall b. m (Base t b) -> Base t (m b))
             -> (a -> Base t (m a)) -> a -> t
Constructing a value for this type follows similarly from the anamorphism except the monad now gives us a bit more trouble. We want something of the form Base t(Base t(Base t ....

We proceed using the same structure as before, first unfurling one layer to get Base t (m a).
Now we need to recursively unfold the inner layers. So we're going to need a function f that does that.
f will eventually need to inject the base functor into the recursive type, so we're going to need a value
Base t t. What the monad does is provide us with an additional little algebra over the 'a'. So our function that collapses the base functor must evaluate the monad and then fold that into the recursive type. So f must have type : Base t (m a) -> Base t t. In order to evaluate the monad we have been provided with a distributive law, that pushes the monad inside the functor.

m : Base t (m a) -> Base t t
m x = fmap (embed . m . fmap join . f . fmap g) x

We first unfurl the inner 'a' one more time to obtain a Base t (m (Base t (m a)). Now we distribute the monad across our base functor to obtain Base t(Base t( m (m a)). We can now evaluate the monad using join to get Base t(Base t(m a)). Now the inner functor is in the exact form we need to unfurl it further using m. Finally we can embed this fixed form of our base functor into our recursive type, and we are done.

gunfold' :: (Unfoldable t, Monad m, Functor m) =>
          (forall b. m (Base t b) -> Base t (m b))
          -> (a -> Base t (m a)) -> a -> t
gunfold' f g a = embed $ m (g a)
    where
      m x = fmap (embed . m . fmap join . f . fmap g) x

Recursion Schemes Excursions

I thought I'd document my excursion into recursion schemes.
For ever and always, recursive patterns have and will pop up, but I had to squash the combinators to fit. I thought I'd finally cut a swathe through the higher dimensional morph-ine like haze recursion schemes induces.

So, to be terse:
Recursion schemes maps our recursive type into its base functor using a type family 'Base'.
In order to use harness the power of its combinators we need to create instances of the classes Foldable and Unfoldable.
An instance of Foldable implies that we can 'project' our recursive type onto the base functor.
An instance of Unfoldable implies we can embed our base functor into the recursive type.
Instances of both mean that the recursive type and the base functor are isomorphic. The base-functor should always be <= the recursive type.

So onto the first of them:
A catamorphism is a fold, it builds up a tower of applications of f and then collapses them from the inside - a right fold. The projection allows us to talk in terms of the base functor which we know how to reach inside of and twiddle around in. The 'fmap m' folds the inner part and provides the folded version to our algebra which simply performs a single step of the fold.

cata :: Foldable t => (Base t a -> a) -> t -> a
cata f = m where m = f . fmap m . project


Next post, para-morphisms.

TopSort

Our story today begins with the rather unmotivated type

eval :: Functor f => f (f a -> a) -> f a

Lets construct a value of the type,

eval f = xs where xs = fmap ($ xs) f

Plugging the list functor in, we have:

eval :: [[a] -> a] -> [a]

It becomes a little clearer from looking at the function that what we're doing is creating a list where each value in the list is a function of the list itself. The base case would be the constant function.

Creating a value of the argument to eval we have something like:

arg = [\list -> list !! 1, const 3, \list -> list !! 0 + list !! 1 + list !! 5, const 2, const 5, const 4]

If we eval arg , it provides arg as the argument to each index in arg . If the graph isn't acyclic we're going to <<loop>>; this is very reminiscent of a spreadsheet.

Thus eval provides a method of traversal of a directed acyclic graph when the functor is a list. Among the many algorithms related to graph traversal I'm going to pick topological sort.

So each element in the list has a list of dependencies.

type AdjList = [[[Int]] -> [Int]]

topSort :: AdjList -> [Int]

topSort a = map fst res

    where 

     indices = [0..]

     res = sortBy comparator $ zip indices (eval a)

      comparator x y = compare (length (snd x)) (length (snd y))

We evaluate the dependencies and tag them with their indices. Then we sort them by the number of dependencies. The algorithm works because for any two nodes u and v, if there is a directed path from u to v, the number of dependencies associated with u is strictly greater than that of v.

What remains is to construct sample adjacency lists for which we will need to construct a list of dependencies:

ref = flip (!!)

deps l = foldl f (const []) l

   where

      f g e = (++) <$> g <*> fmap (e:) (ref e)

adj1 = [deps [1, 2, 3], const [], deps [1, 3], const []]

Full code at https://github.com/joshcc3/HaskellExperiments/blob/master/interestingTypes/Loeb.hs

Iteration: functional style

for(int i = 0; i < a.length; i++){

a[i] = f(a[i], constant_info); // where f is a pure function

}



for(int i = 0; i < a.length; i++) {

accum = g(a[i], accum); // where g is a pure function

}



while(x >= 0 && s < a.length) {

ans *= h(a[x], accum); 

x = a[x];

}

In the first example, we have a function purely in terms of the i'th element of a. It cannot affect anything else about a and it doesn't have any other information about a.

In the second example, we ease up and give ourselves access to an accumulated value that could possibly summarize the previous part of the array.

In the final one we let all hell loose and allow the value to determine where we go next. We're no longer accumulating in a fixed direction from left to right. We're allowing the value at our location to determine where we jump to next.

The above are three general ways of iteration. Now imagine if we had specific loop constructs that tackled each of the above cases. Aside from the clutter, this would actually make stuff more clear. Using these constructs would guarantee that any effect on our array was localized, or that an update to our accumulator is restricted to the correct values. I mean if all we wanted to do was simply modify the individual characters of a string (say by applying a shift cipher) having access to the entire array seems a bit overkill right. It's easy to imagine messing up and referencing some other part of the array in the update. So we could implement something like,

forIndividual (new Function <Dest_Type, Source_Type> ( Source_Type valueAtInd) {

  public Dest_Type apply(Source_Type valueAtInd){

    return some_jiggery_pokery(valueAtInd);

}



});



forAccumulate (new Function <Dest_Type, Tuple<Dest_Type, Source_Type>> (){

  public Dest_Type apply(Source_Type valueAtInd, Dest_Type accum){

    return accumulate_stuff(valueAtInd, accum);

  }



});





forJumpAround (new Function <Tuple <Source_Type, Dest_Type>, Source_Type> (){

  public Tuple<Dest_Type, Source_Type> apply(Source_Type stream){

    return new Tuple(process_element_in_stream(stream), next_in_stream(stream));

  }



});

That looks particularly ugly. It's because the idea of an update is not first class in Java, reifying it results in the above. However the idea behind these elaborate schemes is to protect the programmer from himself. 

Restrict the user by giving him the minimal amount of information necessary to perform the task

Separate the update from the manner of iteration.

Moving to a functional language where an update can be reified to a function, transcribing the above to Haskell we get:

map ~ forIndividual

map :: (a -> b) -> [a] -> [b]



foldl ~ forAccumulate

foldl :: (a -> b -> a) -> [a] -> b -> [b]



unfoldr ~ forJumpAround

unfoldr :: (a -> Maybe(b, a)) -> a -> [b]

We can abstract these even further, where we generalize the container we iterate over.

Why I like Haskell

I would say I'm comfortable with a few languages, Java, C++, C and Haskell. The reason I prefer Haskell to the others is for the following reasons.

To me, Haskell is a better software product. The interface offered by the language is much cleaner. For example, using some of the abstractions in C and C++ correctly requires an understanding of their implementation. For Haskell, the only properties we care about are those needed to define the abstraction (mostly)

The language constructs in imperative languages seem less powerful. For example control flow structures like if statements, loops and exceptions are hard-coded into the language, supported by syntax. In a functional language, we can create these control flow structures using functions and manipulate them as first class values.

The abstractions commonly used in functional programming are very powerful. Although they aren't a property of it, the Functor, Monoid, Applicative and Monad abstractions are extremely powerful and general. They provide a framework to manipulate data very rigorously. Using this framework ensures correctness for achieving the particular task. 

Speaking of abstractions, types are of course absolutely awesome. They provide the best abstraction yet. Some types perfectly describe their implementation counterpart and much more succinctly. In fact parametricity will guarantee certain theorems hold which is very nice to have and nigh impossible in real-world Java and C++ systems.

Lets say we wanted to implement a function that removes duplicates.

removeDups :: Ord a => [a] -> [a]

removeDups = snd . foldl step (S.empty, [])
where
step (t, acc) a = if S.member a t
then (t, acc)
else (S.insert a t, acc ++ [a])


public static List<A> removeDups(List<A> inp){
HashSet<A> s = new HashSet<A>();
List<A> ans = new List<A>();
for(A a : inp){
if(!s.contains(a)){
s.append(a);
s.put(a);
}
}
}

The difference over here is that using the model for iteration through the 'iterate' function we separate out the logic for a single step allowing us to observe and preserve our invariants with greater clarity. The invariant here is that after processing the first i characters, the set contains entries of all distinct characters upto that point and the list is a subsequence of the original having the first occurrence of all distinct characters upto the ith index.  We don't have to worry about the edge cases of the string. The logic for collapsing a structure by accumulating the values through a left-right traversal has already been implemented.

In the real world though interfacing with the low level components is essential for performant code, which breaks the nice abstractions. Thats not really reflected over here though.