[Haskell-cafe] Re: Polymorphic lists...
oleg at pobox.com
oleg at pobox.com
Wed Mar 10 23:05:26 EST 2004
[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.
More information about the Haskell-Cafe
mailing list