June 2003 - Haskell - Haskell.org

Re: Typesafe MRef with a regular monad
by oleg＠pobox.com 11 Jun '03

11 Jun '03

> update :: (Typable b) => FM k -> Key k a -> b -> (FM ...) I didn't know constraints on values are allowed... Given below is the implementation of the required interface, in Haskell98 module TypedFM where data FM k -- Abstract; finite map indexed bykeys of type k data Key k a -- Abstract; a key of type k, indexing a value of type a empty :: FM k insert :: Ord k => FM k -> k -> a -> (FM k, Key k a) lookup :: Ord k => FM k -> Key k a -> Maybe a update :: Ord k => FM k -> Key k a -> a -> FM k Implementation: import Monad data U = LBool Bool | LChar Char | LInt Int | LL [U] -- Lists of any kind | LA (U->U) -- monomorophic functions of any kind class UNIV a where inj:: a -> U prj:: U -> Maybe a instance UNIV Bool where inj = LBool prj (LBool a) = Just a prj _ = Nothing instance UNIV Char where inj = LChar prj (LChar a) = Just a prj _ = Nothing instance UNIV Int where inj = LInt prj (LInt a) = Just a prj _ = Nothing instance (UNIV a) => UNIV [a] where inj = LL . map inj prj (LL as) = foldr f (Just []) as where f e (Just s) = case prj e of Just x -> Just $ x:s _ -> Nothing f _ _ = Nothing prj _ = Nothing instance (UNIV a,UNIV b) => UNIV (a->b) where inj f = LA $ \ua -> let (Just x) = prj ua in inj $ f x prj (LA f) = Just $ \x -> let Just y = prj$f$inj x in y prj _ = Nothing data FM k = FM [U] data Key k a = Key Int a empty = FM [] insert (FM l) _ a = (FM $(inj a):l, Key (length l) a) lookp:: (UNIV a) => FM k -> Key k a -> Maybe a lookp (FM l) (Key i a) = prj $ (reverse l)!!i update:: (UNIV a) => FM k -> Key k a -> a -> FM k update (FM l) (Key i _) a = FM $ reverse (lb ++ ((inj a):(tail lafter))) where (lb,lafter) = splitAt i (reverse l) test1 = do let heap = empty let (heap1,xref) = insert heap () 'a' let (heap2,yref) = insert heap1 () [(1::Int),2,3] let (heap3,zref) = insert heap2 () "abcd" putStrLn "\nAfter allocations" -- print heap3 putStr "x is "; print $ lookp heap3 xref putStr "y is "; print $ lookp heap3 yref putStr "z is "; print $ lookp heap3 zref let heap31 = update heap3 xref 'z' let heap32 = update heap31 yref [] let heap33 = update heap32 zref "new string" putStrLn "\nAfter updates" putStr "x is "; print $ lookp heap33 xref putStr "y is "; print $ lookp heap33 yref putStr "z is "; print $ lookp heap33 zref putStrLn "\nFunctional values" let (heap4,gref) = insert heap33 () (\x->x+(1::Int)) putStr "g 1 is "; print $ liftM2 ($) (lookp heap4 gref) $ Just (1::Int) return ()

3 3

LOOPS
by Filip 11 Jun '03

11 Jun '03

I have a stupid question :) Is there something like "while" loop in GHC ?? Thanks very much :)

3 2

LOOPS
by Filip 11 Jun '03

11 Jun '03

I have a stupid question :) Is there something like "while" loop in GHC ?? Thanks very much :)

1 0

Call for organizers: The 5th Advanced Functional Programming School, 2004
by Johan Jeuring 11 Jun '03

11 Jun '03

Call for organizers: The Advanced Functional Programming School, 2004 http://www.cs.uu.nl/~johanj/afp/ We solicit plans for organizing the next Advanced Functional Programming School. Since 1995 there have been four Schools on Advanced Functional Programming in * 2002, LNCS 2638, Oxford, UK * 1998, LNCS 1608, Braga, Portugal * 1996, LNCS 1129, Olympia, WA, USA * 1995, LNCS 925, Baastad, Sweden ------------------------------------------------------------------------ The goals of this series of schools are: * Bring computer scientists, in particular young researchers and programmers, up to date with the latest afp techniques. * Bridge the gap between results presented at programming conferences and material from introductory textbooks on functional programming. * Use afp techniques in "programming in the real world". The approach we take to achieve these goals in the schools is * In depth lectures about afp techniques, taught by experts in the field. * Lectures are accompanied by practical problems to be solved by the students at the school. The problems guide the students' learning to a great extent. This implies that there has to be a lab at the school site. * Group work is stimulated, especially because the practical problems will typically be too large for a single person. Functional programming is interpreted broadly, to encompass languages that are strict and lazy, pure and impure, typed and untyped, sequential and concurrent. ------------------------------------------------------------------------ The lecture notes of the Advanced Functional Programming schools are published after the school, see LNCS 925, 1129, 1608, and 2638. The organizers are responsible for publishing the lecture notes. Please submit a proposal for organizing the next advanced functional programming school. Your proposal should include: - the approximate dates - the name of the organizers (preferably more than one) - a programme: lecturers (a mix of young and bright, and old and wise lecturers is preferred) and topics (keep in mind that applications of functional programming are very important for the school). - a location (remember you need around 25 computers) - a budget, including an estimation of the registration and hotel costs per participant. The programme, location and budget don't have to be completely fixed when you submit your proposal, but there should be sufficient information to review your proposal. Your proposal will be reviewed by the steering committee of the Advanced Functional Programming Schools, consisting of Pedro Henriques Graham Hutton Johan Jeuring Erik Meijer Greg Morrisett Chris Okasaki Simon Peyton Jones Tim Sheard Doaitse Swierstra Phil Wadler Submit your proposal to johanj(a)cs.uu.nl on or before September 1, 2003 Notification October 1, 2003 -- Johan Jeuring

1 0

Re: Typesafe MRef with a regular monad
by Koen Claessen 11 Jun '03

11 Jun '03

Someone asked me: | I don't recall the message you are referring to, and I | can't find it in the archive. Can you point me at it? Sorry, I meant: http://www.haskell.org/pipermail/haskell/2001-September/007922.html /K :-)

1 0

Functor instance for arbitrary polymorphic types
by Graham Klyne 10 Jun '03

10 Jun '03

I've been running into a problem where I'd like to modify a container type based on a body of existing code to be a Functor. A difficulty seems to be that parts of the container type are based on a type constructor where the underlying type 'a' over which "fmap :: (a->b) -> t a -> t b" would operate is not the only or last parameter to the type constructor expression. If I could easily go change the underlying data types used, I could declare a Functor by rearranging the constructor parameters, but in my application that would be a lot of code reworking that I'd rather avoid, and I'm not sure that the change wouldn't raise a conflict somewhere else. In a sense, what I seem to want is a type-expression equivalent of 'flip'. My question, then, is: am I overlooking anything here? Is there a way to declare a Functor without changing the underlying type and class definitions? (I do think I could do something with generics, but they don't seem to be beyond being very experimental at this time.) Below are two blocks of code: 1. a distillation from my current application, including a partial exploration of using generics, and 2. a reworking of the underlying type to demonstrate (to myself, at least) how changing the type makes it possible to declare a Functor instance. In each case, the type that I wish to be an instance of Functor is 'EntryT'. (Test cases all run under Hugs, though I did use GHCi to debug the kinds.) #g -- 1. Functor definition for EntryT not achieved [[ -- spike-functorkind.hs -- Can an arbitrary polymorphic type constructor be used -- as a basis for a functor? -- Suppose I have some general structure that associates types -- with some structure of those types: class Trans a b c where trans :: (b -> b2) -> a b c -> a b2 c dummy :: a b c -> c b -- provides kind information about c -- and a data structure that maintains a value of the base type -- and the constructed type: data EntryT b c = ET b (c b) type EntryTPair b = EntryT b Pair instance (Show b) => Show (EntryTPair b) where show (ET b1 b2) = "ET "++show b1++" "++show b2 -- An instance of Trans might be a pair: data Pair b = P b b deriving Show instance Functor Pair where fmap f (P k1 k2) = P (f k1) (f k2) instance Trans EntryT k Pair where trans f (ET kv (P k1 k2)) = ET (f kv) (P (f k1) (f k2)) -- tests f a = (a,a) p1 = P "a1" "b1" e1 = ET "1" p1 test1a = fmap f p1 test1b = trans f e1 -- Is there any way to declare EntryTPair to be an instance of -- Functor without re-writing the definition of class T or type Pair -- and their associated methods? -- As far as I can tell, I cannot because the kind of EntryT is wrong -- to be used in a Functor instance declaration. ---------------------------------------------------------------- -- On the other hand, it seems that something approaching the -- desired effect could be achieved using generics [1]: -- -- [1] http://research.microsoft.com/Users/simonpj/papers/hmap/ -- http://www.cs.vu.nl/Strafunski/gmap/ -- class Typeable a where cast :: (Typeable a, Typeable b) => a -> Maybe b class Term a where gmapT :: (forall b. Term b => b -> b) -> a -> a everywhere :: Term a => (forall b. Term b => b -> b) -> a -> a everywhere f t = f (gmapT (everywhere f) t) instance (Trans EntryT k Pair, Term k) => Term (EntryT k Pair) where gmapT f e = trans f e -- then use: -- test2 = everywhere f e1 -- except this doesn't quite work because it requires -- f :: a->a -- rather than -- f :: a1->a2 -- so try something like: -- g :: String -> String -- g a = a ++ a -- test2 = everywhere (MkT g) e1 ]] 2. Functor definition for EntryT achieved by rearranging type constructor expression: [[ -- spike-functorkind1.hs -- -- Can an arbitrary polymorphic type constructor be used -- as a basis for a functor? -- -- This is spike-functorkind.hs with the parameters to -- Trans re-arranged, to demonstrate that doing so does -- make a Functor definition possible -- Suppose I have some general structure that associates types -- with some structure of those types: class Trans a b c where trans :: (c -> c2) -> a b c -> a b c2 dummy :: a b c -> b c -- provides kind information about b -- and a data structure that maintains a value of the base type -- and the constructed type: data EntryT b c = ET c (b c) type EntryTPair c = EntryT Pair c instance (Show c) => Show (EntryTPair c) where show (ET c1 c2) = "ET "++show c1++" "++show c2 -- An instance of Trans might be a pair: data Pair b = P b b deriving Show instance Functor Pair where fmap f (P k1 k2) = P (f k1) (f k2) instance Trans EntryT Pair k where trans f (ET kv (P k1 k2)) = ET (f kv) (P (f k1) (f k2)) instance Functor (EntryT Pair) where fmap f = trans f -- tests f a = (a,a) p1 = P "a1" "b1" e1 = ET "1" p1 test1a = fmap f p1 test1b = trans f e1 test1c = fmap f e1 ]] ------------------- Graham Klyne <GK(a)NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E

1 0

CFP: Soft-2003 - WS on Soft Constraints
by Stefano Bistarelli 10 Jun '03

10 Jun '03

============================================================================ ======= 5th International Workshop on Soft Constraints Held in conjunction with 9th International Conference on Principles and Practice of Constraint Programming, CP2003 Actons Hotel, Kinsale, County Cork, Ireland. 29 September - 3 October, 2003 http://www.sci.unich.it/~bista/organizing/soft-2003/ ============================================================================ ======== Call for Paper ============================================================================ ======== Soft-constraints augment the classical CSP framework by allowing the user to express preferences among potential solutions. Given a well-defined mechanism to express and combine preferences, the goal is to find the "best" solution. Therefore, solving soft constraints becomes an optimization task, harder than the satisfaction tasks in classical CSP. Sometimes optimization becomes multi-objective, making the solving process even more complex. The interest of the community on soft constraints has increased in the last years. Several theoretical frameworks have been developed to allow soft constraints in problem modeling. For these frameworks, new algorithms have been built. The main motivation for this line of research is the existence of many real problems involving preferences among potential solutions, which demand an effective solving method. Also in this edition, we want to enlarge the workshop scope by encouraging submissions from domains where soft constraints have specific semantics such as propositional logic formulae (i.e. MAX-SAT), probability distributions (i.e. probabilistic reasoning) or uncertainty. Workshop topics include (but are not limited to): 1. theoretical frameworks for soft constraints 2. problem modeling with soft constraints 3. solving algorithms for soft constraints 4. interlacing satisfaction and optimization techniques 5. multi-objective optimization and soft constraints 6. constraint languages including soft constraints 7. combining/integrating soft constraint frameworks and algorithms into the Constraint Programming framework 8. comparative studies 9. real-life applications Delivery & Submissions This workshop is intended to build on the experience and success of the CP99, CP2000, CP2001 and CP2002 workshops on the same subject, and its aim is to provide a forum where researchers currently working in this area can discuss their most recent ideas and developments and think together about the most promising new directions. Therefore we encourage the presentation of work in progress or on specialized aspects of soft constraints. Papers that bridge the gap between theory and practice are especially welcome. Prospective attendees can Submit a paper, which can be up to 15 pages in length. We encourage authors to submit papers electronically in postscript or pdf format. Papers should be formatted using the Lecture Notes in Computer Science (LNCS) style. Please send your submissions by email to larrosa(a)lsi.upc.es using the subject line Soft-2003 Workshop Submission. Important Dates The proposed schedule of important dates for the workshop is as follows: Paper Submission deadline June 24th Notification of acceptance July 24th Camera-ready version deadline August 14th Workshop Date September 29th Workshop Organizers: Stefano Bistarelli Istituto per l'Informatica e la Telematica, C.N.R., Pisa, Italy Stefano.Bistarelli(a)iit.cnr.it Dipartimento di Scienze, Universita' degli Studi "G. D'Annunzio", Pescara, Italy bista(a)sci.unich.it Javier Larrosa Universitat Politècnica de Catalunya, Barcelona, Spain larrosa(a)lsi.upc.es Thomas Schiex Institut National de La Recherche Agronomique, Castanet Tolosan Cedex - France tschiex(a)toulouse.inra.fr Program Committee: Fadi Aloul (Electrical Engineering & Computer Science University of Michigan - Ann Arbor, USA) Hélène Fargier (IRIT, Université Paul Sabatier, France) Thom Fruehwirth (University of Ulm, Germany) Carmen Gervet (IC-Parc, Imperial College, UK) Ulrich Junker (ILOG, France) Jimmy H. M. Lee (The Chinese University of Hong Kong, Hong Kong) Pedro Meseguer (IIIA-CSIC, Bellaterra, Spain) Barry O'Sullivan (University College Cork, Ireland) Francesca Rossi (University of Padova, Italy)

1 0

ANN: C->Haskell 0.11.5 "Powder Snow"
by Manuel M T Chakravarty 10 Jun '03

10 Jun '03

I am pleased to announce version 0.11.5 "Powder Snow" of the C interface generator C->Haskell. This is the first binary release of the 0.11.x "Powder Snow" series, which supports CPP directives, conditional compilation, and inline C code. More information as well as source code and RPMs for GHC 6.0 are available from http://www.cse.unsw.edu.au/~chak/haskell/c2hs/ Happy Hacking! Manuel

1 0

for all quantifier
by peter＠premise.demon.co.uk 09 Jun '03

09 Jun '03

On the hskell list, spj wrote > I forget whether I've aired this on the list, but I'm seriously > thinking = that we should change 'forall' to 'exists' in existential > data constructors Thanks! It made me wonder what colour the sky is on planet Haskell. >From a Curry-Howard point of view, (I think) the quantifiers are currently the wrong way round. It is actually painful! Peter Hancock

3 2

Multiparameter class confusion
by Graham Klyne 09 Jun '03

09 Jun '03

There is a recurring difficulty I'm having using multiparameter classes. Most recently, I have a class Rule: [[ class (Expression ex, Eq (rl ex)) => Rule rl ex where ... ]] Which I wish to instantiate for a type GraphClosure via something like: [[ instance (Label lb, LDGraph lg lb) => Expression (lg lb) where ... data (Label lb, LDGraph lg lb) => GraphClosure lg lb = ... instance Rule GraphClosure (NSGraph RDFLabel) where ... ]] This gives an error that I think is indicative of a kind error in the use of GraphClosure. If I unbracket the (NSGraph RDFLabel) then the error transfers to the use of Rule. I think that what I really *want* to do here is change the kind of GraphClosure to be (* -> *) rather than (* -> * -> *). But if I try this: [[ data (Label lb, LDGraph lg lb) => GraphClosure (lg lb) = ... ]] a syntax error is reported by Hugs and GHC. If I simply drop lb from the definition of GraphClosure, I get different errors because the type lb (and its associated contraint) is significant to its implementation [Later...] After further trial-and-error, I find that by reversing the arguments to GraphClosure and rearranging some other type signatures thus: [[ data (Label lb, Eq lg) => GraphClosure lb lg = ... ]] and [[ instance Rule (GraphClosure RDFLabel) RDFGraph where ]] I can get things to compile. But I note that I'm forced to drop the LDGraph constraint from the declaration of GraphClosure. This is all feeling rather like black magic to me. Does it really all need to be this confusing, or am I overlooking some fundamental? #g ------------------- Graham Klyne <GK(a)NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E

2 2