[Haskell-cafe] Re: Polymorphic lists...

[oleg at pobox.com]

[Moving to Haskell-cafe from

http://www.haskell.org/pipermail/glasgow-haskell-users/2004-March/006390.html
http://www.haskell.org/pipermail/glasgow-haskell-users/2004-March/006393.html

I hope y'all don't mind the move: the discussion of polymorphic lists is
of general interest and is not limited to GHC. Besides, they serve
coffee in here, albeit virtually. However, they charge for it
virtually, too.]

Keean Schupke wrote:

> The list indexed by integers cannot determine the type of the
> return value through induction on the class... in other words 
> it cannot determine the return type of the lookup function
> until runtime: you can see this in the class instance for 'tke'
>
> > instance (TH a (a,b), TH W b) => TH W (a,b) where
> >     tke (W 0) th@(h,t) f = f h th
> >     tke (W n) (h,t) f = tke (W$ n-1) t f
>
> On the other hand indexing by natural numbers allows the compiler
> to know the return type (and avoid the use of existentials)
> because it is determined at compile time... you can see this because
> the recursion termination is done by the type signatures in the instance
> not the pattern guards of the function.
>
> instance Relation r => RIndex Zero (a `RCons` r) a where
>    rIndex Zero (x `RCons` _) = x
> instance RIndex Idx r b => RIndex Idx (a `RCons` r) b where
>    rIndex (Suc n) (_ `RCons` xs) = rIndex n xs

I concur wholeheartedly. I have expressed the same sentiment:
	http://www.haskell.org/pipermail/haskell/2003-August/012493.html
	http://www.haskell.org/pipermail/haskell/2003-June/011939.html

The reason the previous message implemented indexing by true Int is
because Ralf Laemmel specifically asked for it (plus it is much
harder to do).

Keean Schupke wrote:
> It looks like most of this stuff has been done before... but I don't think
> there is any of it in the ghc libraries. I needed this code for a real
> application, and could not find anything suitable so I rolled my own.
>
> What do people think - is there a case for getting this stuff in the libs,
> should we write a functional pearl? does anyone have any comments about
> the code I posted, or how it could be improved?

It is indeed a very good question.

Just for the sake of it, here's a little bit simplified version of
your example. Labels are done differently.

> {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances #-}
> module Foo where

> data Z = Z
> data S a = S a
>
> class Nat a where n2n:: a-> Int
> instance Nat Z where n2n _ = 0
> instance (Nat a) => Nat (S a) where n2n _ = 1 + n2n (undefined::a)
>
> -- keyed access
> class (Nat n) => MLookup n a r  where
>    mLookup :: r -> n -> a
> instance MLookup Z a (a,r) where
>    mLookup r _ = fst r
> instance MLookup n a r => MLookup (S n) a (a,r) where
>    mLookup (_,xs) _ = mLookup xs (undefined::n)
> instance MLookup n a r => MLookup n a (b,r) where
>    mLookup (_,xs) n = mLookup xs n
>
> -- Positional access
> class (Nat n) => MIndex n a r | n r -> a where
>     midx:: r -> n -> a
> instance MIndex Z a (a,r) where midx (x,_) _ = x
> instance (MIndex n a r) => MIndex (S n) a (b,r) where
>     midx (_,xs) _ = midx xs (undefined::n)

The example now reads

> newtype Name a = Name a deriving Show
> newtype Size a = Size a deriving Show
> newtype Weight a = Weight a deriving Show
>
> infixr 5 &+
> (&+) = (,)
> test = (Name "Box") &+ (Size (3::Int)) &+ (Weight (1.1::Float))
>        &+ (Name "AnotherBox") &+ (Size (42::Int)) &+ (Weight (24.09::Float))
>        &+ ()

Note that at run-time, (Name "Box") is the same as "Box". Name is a
compile-time-only label that incurs no run-time overhead. So, the
essence is the same -- a polymorphic associative list where keys are
ephemeral (have no run-time representation). "mLookup r n" finds the
n-th association in this list of a type a. In the present
representation, labels and values are specified together. There is
no need for a type declaration for test. The compiler will figure it
out.

The name and the size of the first box

*Foo> mLookup test Z::(Name String)
Name "Box"
*Foo> mLookup test Z::(Size Int)
Size 3

and of the second one

*Foo> mLookup test (S Z)::(Name String)
Name "AnotherBox"
*Foo> mLookup test (S Z)::(Size Int)
Size 42

We can also access the element of the array by their absolute
position:

*Foo> midx test Z
Name "Box"
*Foo> midx test (S Z)
Size 3
*Foo> midx test (S (S (S Z)))
Name "AnotherBox"

Decimal types for indices (rather than unary, as above)
would make for a nicer interface.

We can easily write a right fold

> class MFoldr a r  where
>    mfoldr :: (a -> b -> b) -> b -> r -> b
> instance (MFoldr a r) => MFoldr a (a,r) where
>    mfoldr f z r = f (fst r) $ mfoldr f z (snd r)
> instance MFoldr a () where
>    mfoldr f z r = z
> instance MFoldr a r => MFoldr a (b,r) where
>    mfoldr f z r = mfoldr f z (snd r)

and find out how many names are in our list

*Foo> mfoldr (\ (Name (a::String)) n -> n + 1) 0 test
2

and the total sizes of our boxes

*Foo> mfoldr (\ (Size s) a -> a + s) (0::Int) test
45

Incidentally, this polymorphic array may be a model of an extensible
record with row polymorphism and even polymorphic labels. Yet another
record proposal.