[Haskell-cafe] Re: Heterogeneous Data Structures - Nested Pairs
and functional references
Alexander Solla
ajs at 2piix.com
Thu Feb 25 13:14:14 EST 2010
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.
More information about the Haskell-Cafe
mailing list