Re: Polymorphic lists...
Hi Kean,
looks cool.
I get your point about static typing.
I guess that adding a fold operator would make your implementation more
complete.
Oleg has also encountered some of your operations (as you probably know):
http://www.haskell.org/pipermail/haskell/2003-August/012355.html
(Oleg also prefers the term polymorphic lists --- sigh, and he considers
indexing
by types rather than naturals. In fact, he mentions that values can be
retrieved by either type or index, while only the former is discussed
in detail, if I am right. To me it seems, he would also need to end up
using dependant-type encoding of naturals, say data Zero ... and data Succ
..., for look-up. If I am still right, then his operator type_index is
underspecified
because it returns a plain Int, but Int could be replaced by dependant-type
Naturals. Really just guessing. Oleg?)
Minor point: the code I posted combines existential types and type-safe
cast. It does *not* employ the type Dynamic. (You might say that dynamics
and this combination are somewhat equivalent.)
Ralf
MR K P SCHUPKE wrote:
Didn't know If I should post it straight away... its quite long and I dont do
attachments (well not If I can help it. I am aware Dynamic can model heterogenious
lists
(thanks for correct terminology) - but I need static typing. Thats the clever thing
about
this code - the list is heterogenious but statically typed.
So... for your perusal - and If its not up to being included in the libraries I would
value any comments/code review for my own edification.
The module is called Relation as I am modelling Relational Algebra... but if anyone
can
think of a better name...
First some examples:
putStrLn $ show (rIndex two rel1) -- show the third item in rel1
putStrLn $ show (rHead r)
putStrLn $ show (rTail r)
putStrLn $ show (rLast r)
putStrLn $ show (rInit r)
putStrLn $ show (r `rEnqueue` TEST3) -- insert the string into the last (not head)
position
putStrLn $ show ((3 :: Int) `RCons` r) -- insert the Int into the head of the list
r = toTuple (( 1.1 :: Double) `RCons` (fromTuple (hello,1,World)))
And the code:
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-undecidable-instances #-}
{-# OPTIONS -fallow-overlapping-instances #-}
module Lib.DBC.Relation where
--
-- (c) 2004 Keean Schupke, All Rights Reserved.
--
data Zero = Zero deriving Show
data Suc n = Suc n deriving Show
class Nat n
instance Nat Zero
instance Nat n = Nat (Suc n)
zero :: Zero
zero = Zero
one :: Suc Zero
one = Suc zero
two :: Suc (Suc Zero)
two = Suc one
three :: Suc (Suc (Suc Zero))
three = Suc two
four :: Suc (Suc (Suc (Suc Zero)))
four = Suc three
five :: Suc (Suc (Suc (Suc (Suc Zero
five = Suc four
--
infixr 1 `RCons`
data RNil = RNil deriving Show
data RCons a r = a `RCons` r deriving Show
--
class Relation r where
rHead :: a `RCons` r - a
rTail :: a `RCons` r - r
rIsEmpty :: r - Bool
instance Relation RNil where
rHead (x `RCons` _) = x
rTail (_ `RCons` _) = RNil
rIsEmpty RNil = True
instance Relation r = Relation (a `RCons` r) where
rHead (x `RCons` _) = x
rTail (_ `RCons` xs) = xs
rIsEmpty (_ `RCons` _) = False
class RLast r a | r - a where
rLast :: r - a
instance RLast (a `RCons` RNil) a where
rLast (x `RCons` RNil) = x
instance RLast r b = RLast (a `RCons` r) b where
rLast (_ `RCons` xs) = rLast xs
class RInit r1 r2 | r1 - r2 where
rInit :: r1 - r2
instance RInit (a `RCons` RNil) RNil where
rInit (_ `RCons` RNil) = RNil
instance RInit (b `RCons` r1) r2 = RInit (a `RCons` b `RCons` r1) (a `RCons` r2) where
rInit (x `RCons` xs) = x `RCons` rInit xs
class REnqueue r1 r2 a | r1 a - r2 where
rEnqueue :: r1 - a - r2
instance REnqueue RNil (a `RCons` RNil) a where
rEnqueue RNil y = y `RCons` RNil
instance REnqueue r1 r2 b = REnqueue (a `RCons` r1) (a `RCons` r2) b where
rEnqueue (x `RCons` xs) y = x `RCons` rEnqueue xs y
class (Nat n,Relation r) = RIndex n r a | n r - a where
rIndex :: n - r - a
instance Relation r = RIndex Zero (a `RCons` r) a where
rIndex Zero (x `RCons` _) = x
instance RIndex n r b = RIndex (Suc n) (a `RCons` r) b where
rIndex (Suc n) (_ `RCons` xs) = rIndex n xs
infixl 2 `rProduct`
class (Relation r1,Relation r2,Relation r3) = RProduct r1 r2 r3 | r1 r2 - r3 where
rProduct :: r1 - r2 - r3
instance RProduct RNil RNil RNil where
rProduct RNil RNil = RNil
instance Relation r = RProduct RNil r r where
rProduct RNil r = r
instance RProduct r1 r2 r3 = RProduct (a `RCons` r1) r2 (a `RCons` r3) where
rProduct (x `RCons` xs) y = x `RCons` (xs `rProduct` y)
--
class Relation r = RTuple t r | t - r , r - t where
fromTuple :: t - r
Re: Polymorphic lists...
I did not know about Oleg's posting, as I originally said, I based my implementation on a paper by Conor McBride. Oleg is addressing the question of type safe casting, rather than generic storage, so his code is a bit different. Infact his class: class TypeSeq t s where type_index:: t - s - Int fetch:: t - s - t alter:: t - s - s instance (PList Cons t r) = TypeSeq t (Cons t r) where type_index _ _ = 0 fetch _ (Cons v _) = v alter newv (Cons v r) = Cons newv r instance (PList Cons t' r', TypeSeq t r') = TypeSeq t (Cons t' r') where type_index v s = 1 + (type_index v $ cdr s) fetch v s = fetch v $ cdr s alter newv (Cons v' r') = Cons v' $ alter newv r' This stores unique types in a list that can be indexed by their types. Actually last night (before I read this code) I came up with something similar: data MNil = MNil deriving (Show,Data,Typeable) data MCons l a r = MCons l a r deriving (Show,Data,Typeable) class MLookup l r a | l r - a where mLookup :: r - l - a instance MLookup l (MCons l a r) a where mLookup (MCons _ x _) _ = x instance MLookup l r b = MLookup l (MCons m a r) b where mLookup (MCons _ _ xs) l = mLookup xs l This is indexed by a unique type, but stores a second independant type. The allows a kind of static finite map, which is pretty cool! Here's an example: data TmId = TmId data TmVal = TmVal data TmFloat = TmFloat data TmName = TmName testMap :: MCons TmId Int (MCons TmVal String (MCons TmFloat Float (MCons TmName String MNil))) testMap = MCons TmId 1 $ MCons TmVal Hello $ MCons TmFloat 1.2 $ MCons TmName World MNil main :: IO () main = do putStrLn $ show $ testMap `mLookup` TmId putStrLn $ show $ testMap `mLookup` TmVal putStrLn $ show $ testMap `mLookup` TmFloat putStrLn $ show $ testMap `mLookup` TmName Index types don't need to be unique, the first match from the head of the list will be returned. No match will result in a compile time error. Regards, Keean Schupke. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Polymorphic lists...
I have written a first attempt at a fold function for the heterogenious list: class RFold i r where rFold :: (forall a . a - i - i) - i - r - i instance RFold i RNil where rFold f i RNil = i instance RFold i r = RFold i (a `RCons` r) where rFold f i (x `RCons` xs) = f x (rFold f i xs) This works providing the folded 'op' has the type: forall a . a - i - i which means it does not work for functions like show :: forall a . Show a = a - i - i as the types are different. I have not figured out a way to make it accept a constraint like Show for example. Here is an example: length = rFold (\_ - (+1)) 0 relation The use of such a function seems limited, if constraints like Show cannot be used, as most useful applications of fold would require some kind of class membership for example: string = rFold shows relation This fails to compile because shows has type: shows :: forall a . Show a = a - i - i but fold expects op :: forall a . a - i - i Regards, Keean Schupke. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Polymorphic lists...
I have written a first attempt at a fold function for the heterogenious list: class RFold i r where rFold :: (forall a . a - i - i) - i - r - i instance RFold i RNil where rFold f i RNil = i instance RFold i r = RFold i (a `RCons` r) where rFold f i (x `RCons` xs) = f x (rFold f i xs) This works providing the folded 'op' has the type: forall a . a - i - i which means it does not work for functions like show :: forall a . Show a = a - i - i as the types are different. I have not figured out a way to make it accept a constraint like Show for example. Here is an example: length = rFold (\_ - (+1)) 0 relation The use of such a function seems limited, if constraints like Show cannot be used, as most useful applications of fold would require some kind of class membership for example: string = rFold shows relation This fails to compile because shows has type: shows :: forall a . Show a = a - i - i but fold expects op :: forall a . a - i - i Regards, Keean Schupke. ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Polymorphic lists...
Though I haven't tried it, the explicit 'Sat' dictionary representation
would probably work here, something like:
data ShowD a = ShowD { showD :: a - String }
-- our explicit dictionary for show, would need one of
-- these for each class we care about
-- the satisfaction class:
class Sat t where dict :: t
-- an instance for show:
instance Show a = Sat (ShowD a) where dict = ShowD { showD = show }
instance Sat (ShowD a) = Show a where show = showD dict
manually generating datatypes and instances is tedious, but could easily
be automated. you should be able to use this to write:
satFold :: forall c b . Sat c b =
(forall a . Sat (c a) = a - i - i) -
b - r - b
or something similar. probably worth a shot.
On Tue, 9 Mar 2004, MR K P SCHUPKE wrote:
I have written a first attempt at a fold function for the heterogenious list:
class RFold i r where
rFold :: (forall a . a - i - i) - i - r - i
instance RFold i RNil where
rFold f i RNil = i
instance RFold i r = RFold i (a `RCons` r) where
rFold f i (x `RCons` xs) = f x (rFold f i xs)
This works providing the folded 'op' has the type: forall a . a - i - i
which means it does not work for functions like show :: forall a . Show a = a - i
- i
as the types are different. I have not figured out a way to make it accept a
constraint
like Show for example. Here is an example:
length = rFold (\_ - (+1)) 0 relation
The use of such a function seems limited, if constraints like Show cannot be used, as
most useful applications of fold would require some kind of class membership for
example:
string = rFold shows relation
This fails to compile because shows has type:
shows :: forall a . Show a = a - i - i
but fold expects
op :: forall a . a - i - i
Regards,
Keean Schupke.
___
Glasgow-haskell-users mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
--
Hal Daume III | [EMAIL PROTECTED]
Arrest this man, he talks in maths. | www.isi.edu/~hdaume
___
Glasgow-haskell-users mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: -static
On Tue, Mar 09, 2004 at 01:04:59AM +0100, Wolfgang Thaller wrote: So I assume this is on powerpc-linux? Yup, sorry (and the others are all Linux too). Thanks Ian ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
confused by core
Hi,
If I have this Foo.hs:
---
module Foo (foo) where
import Word (Word8)
import Control.Monad.ST (ST)
import Data.Array.ST (STUArray, writeArray)
foo :: STUArray s Int Word8 - [Word8] - Int - ST s ()
foo arr ps i = writeArray arr i w
where i' = 4 * i
w = ps !! i'
---
and I compile with (GHC 6.2 and a reasonably recent CVS)
ghc -O -funbox-strict-fields -Wall -c Foo.hs -ddump-simpl
then part of the output is:
let {
n :: GHC.Prim.Int#
Str: DmdType
n = GHC.Prim.*# 4 ww3
} in
case GHC.Prim.# n 0 of wild1 {
Is this really a lazy let, or is there some magic going on that means it
is actually done strictly as it's an Int#? Like how ISTR Int#s always
appear to have strictness L (these inconsitencies make things much more
difficult as a user IMO, incidentally).
Thanks
Ian
___
Glasgow-haskell-users mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Polymorphic lists...
Ok... After playing with these types, I could not get it to work with
the satFold
below. However it did inspire me to try something else, and this seems
to work
quite well.
First redefine the RFold function to use RFoldFn class as its operator.
Then create
instances of RFoldFn to do what you like. The clever bit is the use of
an abstract
data-type to select which instance to use.
class RFold t i r where
rFold :: t - i - r - i
instance RFold t i RNil where
rFold _ i RNil = i
instance (RFoldFn t a i,RFold t i r) = RFold t i (a `RCons` r) where
rFold t i (x `RCons` xs) = rFoldFn t x (rFold t i xs)
class RFoldFn t a i where
rFoldFn :: t - a - i - i
Here's some examples:
data ShowFn = ShowFn
instance Show a = RFoldFn ShowFn a String where
rFoldFn ShowFn x y = shows x y
putStrLn $ show $ rFold ShowFn r
data SumFn = SumFn
instance Num i = RFoldFn SumFn a i where
rFoldFn SumFn _ s = 1 + s
putStrLn $ show $ rFold SumFn 0 r
I think this is pretty neat, and the mechanism fits in well with how the
rest
of the module works...
Regards,
Keean Schupke.
Hal Daume III wrote:
Though I haven't tried it, the explicit 'Sat' dictionary representation
would probably work here, something like:
data ShowD a = ShowD { showD :: a - String }
-- our explicit dictionary for show, would need one of
-- these for each class we care about
-- the satisfaction class:
class Sat t where dict :: t
-- an instance for show:
instance Show a = Sat (ShowD a) where dict = ShowD { showD = show }
instance Sat (ShowD a) = Show a where show = showD dict
manually generating datatypes and instances is tedious, but could easily
be automated. you should be able to use this to write:
satFold :: forall c b . Sat c b =
(forall a . Sat (c a) = a - i - i) -
b - r - b
or something similar. probably worth a shot.
___
Glasgow-haskell-users mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: -static
On 09.03.2004, at 15:53, Ian Lynagh wrote: On Tue, Mar 09, 2004 at 01:04:59AM +0100, Wolfgang Thaller wrote: So I assume this is on powerpc-linux? Yup, sorry (and the others are all Linux too). Ah yes, that -static flag was lurking there from the old AIX port. It's definitely OK to remove it. I've just done so in the CVS HEAD. According to the source, alpha, hppa and mips also pass the -static flag to the linker. I've done nothing about that yet, as I have no idea why they do so. Cheers, Wolfgang ___ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
