- Haskell - Haskell.org

slightly too(?) complex list pattern matching
by Hal Daume III 17 Jun '02

17 Jun '02

Hi all, I don't think I can do this, but I figured I'd ask anyway. Suppose I have: > data X = X | Y | Z and I want to match against a list of Xs. But all I want is to ensure that there's a Y followed by a Z, but I don't care if there's anything else (or lots of other stuff) in between. Namely, I want to match: .*Y.*Z.* Now, I can match YZ.* easily with: > foo (X:Y:_) = ... furthermore, my matches never require any backtracking, so you won't see something like ".*X.*Y.*X.*Z" which could possibly make you backtrack (so, there are no duplicates in what I'm matching against). Anway, the current way I do this is by having a function: > match [] _ = True > match (m:ms) (x:xs) > | m == x = match ms xs > | otherwise = match (m:ms) xs (Actually, I do a bit more -- I return Maybe [Int] where Nothing signifies that the match failed and Just intList specifies the indices of the matched elements, but this is superfluous). so this requires me to write things like: > foo l > | Just indices <- [X,Y] `match` l = > let [x,y] = map (l!!) indices > in ... instead of the nice haskellesque syntax: > foo [..,x@X,..,y@Y,..] = ... anyway, I'm curious if anyone else has pounded against this wall at all and if there's any tool (drift, or something perhaps) that would allow me to write more succinct versions? Thanks! - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

�𾴵��Ͽͻ��
by syhua3000 17 Jun '02

17 Jun '02

�𾴵��Ͽͻ�� ã� www.8dns.netΪ�˴�л��Լ��ͻ��˾��֧�ֺ��Σ��ٴ��¾ɷ��ܣ��… ��ȫ��ͬʱ��ǻ��˲�Ʒ �۸��ܸ��ʵķ��񡣣��˾��վ��ȫ�¸İ棺www.8dns.net�� 200M HTML�ռ�+1��۸�150Ԫ/�� 100M�ռ�(֧��ASP)+100M��ҵ�ʾ�+20M ACCESS��ݿ�+1�� 288Ԫ/�� 200M�ռ�(֧��ASP)+200M��ҵ�ʾ�+30M Access��ݿ�+1�� 338Ԫ/�� ֻ��ۼ۸񡣻�ӭѡ��Ҳ��ӭ��Ϊ��ǵĴ��! ��ǻ��и��Żݼ۸�� http://www.8dns.net �� ===================================================================== ��ʼ��õ��˵��Ϣ��˵��û�ã��ֱ�Ǹ�� ʼ��Գ�ŵֻ��һ�Ρ��ϣ��Ǵ��б��ɾ��ĵ�ַ��š�лл��<br> ===================================================================== --------------------------------------------------------------- �е�Ⱥ��ʼ�,��ר��(http://www.21cmm.com) ��CMM��У(http://www.21cmm.com)��Ŀ��ר��

1 0

Re: runIO (?)
by Ashley Yakeley 16 Jun '02

16 Jun '02

At 2002-06-16 16:20, Andre W B Furtado wrote: >I'd like to run some IO operations in a Monad (other than the IO Monad). Is >there any kind of "runIO" to do this? No (unless your monad encapsulates the IO monad). -- Ashley Yakeley, Seattle WA unsafePerformIO is NOT Haskell!

1 0

runIO (?)
by Andre W B Furtado 16 Jun '02

16 Jun '02

I'd like to run some IO operations in a Monad (other than the IO Monad). Is there any kind of "runIO" to do this? (One approach is to make my Monad to encapsulate the IO Monad, but I'd not like to do this for other reasons). Thanks a lot, -- Andre

1 0

trees with pointers to parents & memory gobbling
by Hal Daume III 15 Jun '02

15 Jun '02

Hi all, I have a datatype which (simplified) looks like: data FBTree a = FBLeaf (Maybe (FBTree a)) a | FBBranch (Maybe (FBTree a)) (FBTree a) (FBTree a) is basically a tree with Maybe a parent node. however, unlike the nice non-haskell equivalent, they tend to eat up memory as you traverse them. for instance, given the conversion functions and helper functions: data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Eq, Show) data FBTree a = FBLeaf (Maybe (FBTree a)) a | FBBranch (Maybe (FBTree a)) (FBTree a) (FBTree a) instance Eq a => Eq (FBTree a) where a == b = unFBTree a == unFBTree b instance Show a => Show (FBTree a) where showsPrec i = showsPrec i . unFBTree mkFBTree = mkFBTree' Nothing where mkFBTree' par (Leaf a) = FBLeaf par a mkFBTree' par (Branch l r) = this where this = FBBranch par (mkFBTree' (Just this) l) (mkFBTree' (Just this) r) unFBTree (FBLeaf _ a) = Leaf a unFBTree (FBBranch _ l r) = Branch (unFBTree l) (unFBTree r) findRoot (FBLeaf (Just par) _) = findRoot par findRoot (FBBranch (Just par) _ _) = findRoot par findRoot t = t findLeftMostChild (FBBranch _ l _) = findLeftMostChild l findLeftMostChild t = t if we just walk up and down a tree a bunch of time, heap profiling reports huge amounts of memory usage. witness: tree = Branch (Branch (Branch (Branch (Branch (Leaf 'h') (Branch (Leaf 'a') (Leaf 's'))) (Leaf 'k')) (Branch (Leaf 'e') (Leaf 'l'))) (Leaf 'l')) (Leaf '!') fbtree = mkFBTree tree main = print $ last $ take 100000 $ iterate (findLeftMostChild . findRoot) fbtree even if i put an appropriate call to seq in the iteration, i still get lots of memory eaten up, can someone say how i can fix this? - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

2 1

Summer School on Generic Programming, Oxford, UK
by Roland Backhouse 14 Jun '02

14 Jun '02

Summer School and Workshop on Generic Programming St Anne's College, Oxford, UK 26th to 30th August 2002 In conjunction with Summer School and Workshop on Advanced Functional Programming This school is a successor to the Summer School and Workshop on Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, held in Oxford in April 2000 and with lecture notes shortly to appear as LNCS 2297. For this school we have recruited an excellent group of lecturers on generic programming, that is, the construction of programs that work on different datatypes and yet may exploit the structure of that data. ************ Lecturers ************ * Roland Backhouse (University of Nottingham): A Generic Theory of Datatypes * Peter Buneman (University of Edinburgh): Semi-Structured Data * Roy Crole (University of Leicester): Categories and Types * Jose Luiz Fiadeiro (University of Lisbon and ATX Software): Theory and Practice of Software Architecture * Johan Jeuring (University of Utrecht): Generic Haskell * Martin Odersky (Ecole Polytechnique Federale de Lausanne): Object-Oriented and Functional Approaches to Compositional Programming ************ Deadlines ************ For registration: 12th July 2002 ************ Organizers ************ Roland Backhouse (University of Nottingham) Jeremy Gibbons (University of Oxford) ************ Further information ************ Web: http://www.comlab.ox.ac.uk/oucl/research/areas/ap/ssgp/info.html PDF poster: http://www.comlab.ox.ac.uk/oucl/research/areas/ap/ssgp/ssgp-poster.pdf Email: ssgp-info(a)comlab.ox.ac.uk Post: SSGP, c/o Jane Ellory, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom. Fax: +44 1865 273839; mark "fao SSGP (Jane Ellory)"

1 0

FW: Haskell accumulator
by Dominic Cooney 14 Jun '02

14 Jun '02

Paul Graham is collecting canonical accumulator generators at http://www.paulgraham.com/accgen.html , and has Dylan, E, JavaScript, various dialects Lisp, Lua, Rebol, Ruby, Perl, Python and Smalltalk. Could the serious Haskellers comment on this attempt of mine? foo n = do n' <- newIORef n return (\i -> do { modifyIORef n' (i+); readIORef n' }) This is all related to arguments about the benefits of succinctness and expressivity in programming languages. Dominic Cooney -----Original Message----- From: Paul Graham [mailto:pg@archub.org] Sent: Thursday, 13 June 2002 11:17 PM To: dominic(a)dcooney.com Subject: Re: Haskell accumulator Would this (if the type signature is unnecc) then be the canonical def in Haskell? foo n = do n' <- newIORef n return (\i -> do { modifyIORef n' (i+); readIORef n' }) --Dominic Cooney wrote: > This is a multi-part message in MIME format. > > ------=_NextPart_000_0001_01C212A8.F2F6A010 > Content-Type: text/plain; > charset="us-ascii" > Content-Transfer-Encoding: 7bit > > If you are still collecting these Revenge of the Nerds accumulators, > here it is in literate Haskell: > > > mkAccum :: (Num a) => a -> IO (a -> IO a) > > mkAccum n = do > > n' <- newIORef n > > return (\i -> do { modifyIORef n' (i+); readIORef n' }) > > There are a couple of interesting things here; firstly the (Num a) => is > an example of Haskell's type classes. > > The second is the 'IO' written everywhere. Haskell is pure, and IO is > the library-sanctioned state monad. Thus mkAccum and the accumulator > itself evaluate to "IO things" since they involve mutable state. > > The only other interesting thing about the type signature is that it is > completely unnecessary. The compiler infers the most general type. The > programmer can write explicit type signatures to narrow the type of a > function, or (more commonly) have the compiler provide a sanity check. > > 'Return' is unusual too-- it wraps things in the IO monad. Ordinarily it > is not required, e.g. > > > incr n = \x -> n + x > > Although this could simply be written as a partial application, like: > > > incr n = (+) n > > A whole test program is attached re: the accumulator. > > On another note, I am eagerly awaiting the arrival of ANSI Common Lisp > from Amazon. I may be converted yet. > > Dominic Cooney > > > ------=_NextPart_000_0001_01C212A8.F2F6A010 > Content-Type: application/octet-stream; > name="accum.lhs" > Content-Transfer-Encoding: 7bit > Content-Disposition: attachment; > filename="accum.lhs" > > This can be built with: > > ghc -fglasgow-exts -package lang --make accum.lhs -o accum > > GHC is available from http://www.haskell.org/ghc . > > > > module Main (main) where > > Haskell is pure-- the state of the world is in the IO monad. Hence > the accumulator requires these imports. > > > import IOExts (IORef, newIORef, readIORef, modifyIORef) > > > The accumulator. > > > mkAccum :: (Num a) => a -> IO (a -> IO a) > > mkAccum n = do > > n' <- newIORef n > > return (\i -> do { modifyIORef n' (i+); readIORef n' }) > > > Small test program. > > > main :: IO () > > main = do > > acc <- mkAccum 42 > > x <- acc 1 > > put x > > x <- acc 2 > > put x > > > Put is a small function that prints something. > > > put :: (Show a) => a -> IO () > > put = putStrLn.show > ------=_NextPart_000_0001_01C212A8.F2F6A010-- >

5 4

TERMGRAPH 2002: Extended submission deadline
by Detlef Plump 14 Jun '02

14 Jun '02

Dear Colleagues, Due to request the submission deadline for TERMGRAPH 2002 - The International Workshop on Term Graph Rewriting - has been extended to June 20, 2002. The Call for Papers can be found at: http://www.cs.york.ac.uk/~det/Termgraph_2002/cfp.html With best regards, Detlef Plump

1 0

Call for Participation: 7th ERCIM FMICS (Malaga, Spain) July 12-13, 2002
by Hubert Garavel 14 Jun '02

14 Jun '02

****************************************************************************** * * CALL FOR PARTICIPATION * * 7th International Workshop on Formal Methods for Industrial Critical Systems * (FMICS 02) * * University of Málaga (Spain) * July 12-13, 2002 * Colocated with the 29th ICALP conference * * http://www.inrialpes.fr/vasy/fmics/workshop-7 * ****************************************************************************** *** SCOPE OF THE WORKSHOP *** The aim of the FMICS workshops is to provide a forum for researchers who are interested in the development and application of formal methods in industry. In particular, these workshops should bring together scientists who are active in the area of formal methods and interested in exchanging their experiences in the industrial usage of these methods. They also aim at the promotion of research and development for the improvement of formal methods and tools for industrial applications. *** INVITED SPEAKERS *** Andrew Gordon (Microsoft Research Cambridge, UK) Andreas Podelski Max-Planck Institut für Informatik, Germany) Wang Yi (Uppsala University, Sweden) *** PROGRAMME *** ------------------------ FRIDAY 12 July 2002 --------------------------------- INVITED PRESENTATION Andreas Podelski (Max-Planck Institut für Informatik, Germany) Abstraction for Software Model-Checking SESSION - ABSTRACTION AND MODEL-CHECKING - Chair: H. Garavel (INRIA, France) M. Bourahla (Univ. of Biskra, Algeria), M. Benmohamed (Univ. of Constantine, Algeria) Predicate Abstraction and Refinement for Model Checking VHDL State Machines M. del Mar Gallardo, J. Martinez, P. Merino, E. Pimentel (Univ. of Málaga, Spain) A Tool for Abstraction in Model Checking SESSION - TESTING - Chair: R. Cleaveland (SUNY, New York, USA) D. Lugato, C. Bigot, Y. Valot (CEA Saclay, France) Validation and Automatic Test Generation on UML Models: the AGATHA approach J.C. Burguillo, M. Llamas, M.J. Fernández (Univ. of Vigo, Spain), T. Robles (Polytechnical Univ. of Madrid, Spain) Heuristic-Driven Techniques for Testing Distributed Systems B. Steffen (Univ. of Dortmund, Germany), T. Margaria (METAFrame, Germany), O.Niese (Univ. of Dortmund, Germany) Scalable System-level CTI Testing through Lightweight Coarse-grained Coordination INVITED PRESENTATION Andrew D. Gordon (Microsoft Research, Cambridge, UK) Authenticity Types for Cryptographic Protocols SESSION - INDUSTRIAL CASE STUDIES I - Chair: H. Hermanns (Univ. of Twente, NL) N. Lopez, M. Simonot, V. Donzeau-Gouge (CNAM, Paris, France) A Methodological Process for the Design of a Large System: Two Industrial Case-Studies C. Daws (CWI, Amsterdam, NL), M. Kwiatkowska, G. Norman (Univ. of Birmingham, UK) Automatic Verification of the IEEE-1394 Root Contention Protocol with KRONOS and PRISM TOOL DEMOS WORKSHOP BANQUET ----------------------- SATURDAY 12 July 2002 ------------------------------- INVITED PRESENTATION Wang Yi (Uppsala Univ., Sweden) Synthesis of Verified Real Time Software SESSION - INDUSTRIAL CASE STUDIES II - Chair: W. Fokkink (CWI, Amsterdam, NL) V. Valero, F.L. Pelayo, F. Cuartero, D. Cazorla (Univ. of Castilla, Spain) Specification and Analysis of the MPEG-2 Video Encoder with Timed-Arc Petri Nets S. Boldo, M. Daumas (Ecole Normale Supérieure de Lyon, France) Properties of the Subtraction Valid for any Floating Point System SESSION - MODEL CHECKING Chair: S. Gnesi (IEI-CNR, Pisa, Italy) X. Thirioux (IRIT-LIMA, Toulouse, France) Simple and Efficient Translation from LTL Formulas to Buchi Automata A. Biere, C. Artho, V. Schuppan (ETH Zürich, Switzerland) Liveness Checking as Safety Checking H. Hansen (Tempere Univ. of Technology, Finland), W. Penczek (Institute of Computer Science, Warsaw, Poland), A. Valmari (Tempere Univ. of Technology) Stuttering-Insensitive Automata for On-the-Fly Detection of Livelock Properties A.Valmari, H. Virtanen, A. Puhakka (Tempere Univ. of Technology, Finland) Context-Sensitive Visibility FMICS WORKING GROUP MEETING ----------------------------------------------------------------------------- *** REGISTRATION **** The registration procedure is described on the FMICS 02 web site http://www.inrialpes.fr/vasy/fmics/workshop-7 which also provides traveling and accomodation information. *** ORGANIZATION *** FMICS 02 Programme Committee Chairs H. Garavel (INRIA Rhone-Alpes, France) R. Cleaveland (SUNY, New York, USA) FMICS 02 Local Organizing Committee (University of Málaga) M. del Mar Gallardo P. López J. Martínez P. Merino (local organization chair) _____________________________________________________________________________

1 0

tables
by Peter Padawitz 13 Jun '02

13 Jun '02

Have Parnas' tabular expressions and algorithms ever been implemented in Haskell? Would anyone consider this a reasonable project? Peter --- Prof. Dr. Peter Padawitz Informatik 5 University of Dortmund D-44221 Dortmund Germany phone +49-231-755-5108 fax +49-231-755-4851 or -5802 secretary +49-231-755-5801 email peter.padawitz(a)udo.edu internet http://ls5.cs.uni-dortmund.de/~peter "Computer science is no more about computers than astronomy is about telescopes." -Dijkstra

2 1