[Haskell-cafe] Re: Heterogeneous Data Structures - Nested Pairs and functional references

[Alexander Solla]

On Feb 24, 2010, at 10:15 AM, Heinrich Apfelmus wrote:

> Namely, let's assume we are already given a "magic" type  
> constructor  |-
> (so magic that it's not even legal Haskell syntax) with the property  
> that
>
>    A |- B
>
> somehow denotes an expression of type  B  with free variables of  
> type  A
> . In other words, the result of type  B  is somehow allowed to  
> depend on
> values of type  A .


In the context of this post, when I say "functor", I don't mean a  
Functor instance.  I mean the mathematical object which maps between  
categories.

As you noted, functions satisfy your "magic".  A function from a type  
A to B is a functor from A to B from a different point of view.  (One  
is "in" some kind of algebra in A and B, and the other is in the  
category of small categories).  But you lose something important by  
using functions.

Consider the parallel type specification of (my) Views with types,  
guided by your example code:

concat_views :: a -> v -> v -> (a, (v, v)) -- v's are meant to be the  
result of calling a *_view function.
nest_views     :: a -> v -> v -> v -> (a, (v, v, v))
page_view     :: a -> v -> v -> v -> v -> (a, [v])
text_view        :: String -> v -> (String, v)

As you can see from the types, these are functions that take values  
and "wrap them up".  These functions trivially induce functors of the  
form View a :: v -> (a, [v])  (let's call them lists for the purposes  
of "form" since there can be any number of v's).

What are we gaining?  What are we losing?  My  Functor-based  
implementation had a uniform interface to all the View's innards,  
which we have lost.  And if we want to turn these functions into an  
algebra, we need to define a fair amount of plumbing.  If you take the  
time to do that, you'll see that the implementation encodes a  
traversal for each of result types.  An fmap equivalent for this  
implementation.

In short, before you can do anything with your construct, you will  
need to normalize the return result.  You can do that by reifying them:

 > data View view = EmptyView | TextView String | ConcatViews (View  
view) (View view) | ...

or by doing algebra on things of the form (a, [v]).  Notice, also,  
that the View view data constructors are (basically) functions of the  
form [View] -> (a, [View]) or a -> (a, [View]) for some a.  (The  
tricky bit is the "some a" part.  Consider why EmptyView and (TextView  
String) is a (View view) no matter what type view is).  The parallel  
for EmptyView is:

 > empty_view :: a -> v -> (a, v)
 > empty_view a v = (a, ()) --?  I guess that works.  Dummy arguments  
for empty things.  Ikky.

My example code had some problems, but I really think it's a superior  
solution for the problem of making reusable renderable fragments.   
Indeed, this post described how I refactored your approach into mine,  
when I wrote my View code in the first place.  Then again, I also got  
tired of wrestling with Data.Foldable and moved on to using a plain  
initial algebra and Uniplate.