- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] type level strings?
by oleg＠okmij.org 24 Nov '11

24 Nov '11

Evan Laforge has defined > data Thing { > thing_id :: ThingId > , thing_stuff :: Stuff > } > newtype ThingId = ThingId String and wishes to statically preclude binary operations with things that have different ThingIds. However, Things and their Ids can be loaded from files and so cannot be known to the compiler. He wished for type-level strings -- which is what the enclosed code gives. When we've got two Things loaded from two different files we must do a run-time check to see if these two things have in fact the same ThingId. That is inevitable. The question is how frequently do we have to make such a test? One approach is to do such a ruin-time test on each binary operation on things. The original Thing above was of that approach: > instance Monoid Thing where > mappend (Thing id1 stuff1) (Thing id2 stuff2) > | id1 /= id2 = error "..." > | otherwise = Thing id1 (stuff1 `mappend` stuff2) Every time we mappend things, we must check their ids. It has been suggested to use existentials. We get the the following code: > maybeAppend :: Exists Thing -> Exists Thing -> Maybe (Exists Thing) > maybeAppend (Exists t1) (Exists t2) = > case thing_id t1 `equal` thing_id t2 of > Just Refl -> Just $ Exists (t1 `mappend` t2) > Nothing -> Nothing How different is this from the original mappend? Every time we wish to mappend two things, we have to do the run-time test of their ids! We added phantom times, existentials, GADTs -- and got nothing in return. No improvement to the original code, and no static guarantees. When we have to mappend things several times, it seems optimal to do the run-time ID check only once (we have to do that check anyway) and then mappend the results without any checks, and with full static assurance that only Identical things are mappended. The enclosed code implements that approach. The instance for Monoid makes patent only things with the same id may be mappended. Moreover, there is no run-time id check, and we do not have to think up the id to give to mempty. The test does read two things from a `file' (a string) and does several operations on them. The run-time test is done only once. The ideas of the code are described in the papers with Chung-chieh Shan on lightweight static capabilities and implicit configurations. {-# LANGUAGE RankNTypes, ScopedTypeVariables #-} module Thing where import Data.Monoid import Data.Char -- The data constructor Thing should not be exported newtype Thing id = Thing{ thingStuff :: Stuff } type Stuff = [Int] -- or any monoid class IDeal id where get_id :: id -> String -- The user should use make_thing make_thing :: IDeal id => id -> Stuff -> Thing id make_thing _ t = Thing t -- It is statically assured that only things with the same id -- may be mappended. Moreover, there is no run-time id check -- And we do not have to think up the id to give to mempty instance Monoid (Thing id) where Thing t1 `mappend` Thing t2 = Thing (t1 `mappend` t2) mempty = Thing mempty instance IDeal id => Show (Thing id) where show (Thing t) = show $ (get_id (undefined::id),t) -- A statically-known Id (just in case) data Id1 = Id1 instance IDeal Id1 where get_id _ = "Id1" -- Reading a thing from a file (or at least, a string) data DynId id = DynId instance Nat id => IDeal (DynId id) where get_id _ = int_to_str $ nat (undefined::id) read_thing :: String -> (forall id. IDeal id => Thing id -> w) -> w read_thing str k = reify_ideal i (\iD -> k (make_thing iD t)) where (i,t) = read str -- Run-time equality check -- If id and id' are the same, cast the second to the same id eqid_check :: forall id id'. (IDeal id, IDeal id') => Thing id -> Thing id' -> Maybe (Thing id) eqid_check _ (Thing t) | get_id (undefined::id) == get_id (undefined::id') = Just (Thing t) eqid_check _ _ = Nothing test file1 file2 = read_thing file1 (\t1 -> read_thing file2 (\t2 -> do_things t1 t2)) where -- A run-time test is inevitable, but it is done only once do_things t1 t2 | Just t2' <- eqid_check t1 t2 = do_things' t1 t2' do_things _ _ = error "bad things" -- Now it is assured we have the same id -- we can do things many times do_things' :: IDeal id => Thing id -> Thing id -> String do_things' t1 t2 = show $ mempty `mappend` t1 `mappend` t2 `mappend` t2 `mappend` t1 t1 = test "(\"id1\",[1,2])" "(\"id1\",[3,4])" -- "(\"id1\",[1,2,3,4,3,4,1,2])" t2 = test "(\"id1\",[1,2])" "(\"id2\",[3,4])" -- "*** Exception: bad things -- Reifying strings to types -- They say String kinds are already in a GHC branch. -- Edward Kmett maintains a Hackage package for these sort of things -- Assume ASCII for simplicity str_to_int :: String -> Integer str_to_int "" = 0 str_to_int (c:t) = fromIntegral (ord c) + 128 * str_to_int t int_to_str :: Integer -> String int_to_str = loop "" where loop acc 0 = reverse acc loop acc n | (n',c) <- quotRem n 128 = loop (chr (fromIntegral c) : acc) n' data Z = Z data S a = S a data T a = T a class Nat a where nat :: a -> Integer instance Nat Z where nat _ = 0 instance Nat a => Nat (S a) where nat _ = 1 + nat (undefined::a) instance Nat a => Nat (T a) where nat _ = 2 * nat (undefined::a) reify_integer :: Integer -> (forall x. Nat x => x -> w ) -> w reify_integer 0 k = k Z reify_integer n k | even n = reify_integer (n `div` 2) (\x -> k (T x)) reify_integer n k = reify_integer (n-1) (\x -> k (S x)) reify_ideal :: String -> (forall x. IDeal x => x -> w) -> w reify_ideal str k = reify_integer (str_to_int str) (k . dynid) where dynid :: x -> DynId x dynid = undefined tr1 = reify_integer 10 nat tr2 = int_to_str $ reify_integer (str_to_int "id1") nat

1 0

Munich Haskell Meeting
by Heinrich Hördegen 24 Nov '11

24 Nov '11

Dear all, next week on Tuesday, 29 November, our monthly Haskell get-together will be held at Cafe Puck in Munich. Starting time is 19h30. Please feel free to join us. We are always happy to see someone new. There have been lots of people last time and we did not have enough tables. Therefore, if you plan to join us, please go to this page and hit the button. This well help to reserve places: http://www.haskell-munich.de/dates There is also the question, what to do in December. Any suggestions? We hope to see you soon, Heinrich -- -- hoerdegen(a)funktional.info www.funktional.info --

1 0

Last CFP: 12th International Workshop on Language Descriptions, Tools, and Applications (LDTA 2012)
by Emilie Balland 24 Nov '11

24 Nov '11

LDTA 2012 Call for Papers 12th International Workshop on Language Descriptions, Tools, and Applications www.ldta.info Tallinn, Estonia March 31 & April 1, 2012 an ETAPS workshop LDTA is an application and tool-oriented workshop focused on grammarware - software based on grammars in some form. Grammarware applications are typically language processing applications and traditional examples include parsers, program analyzers, optimizers and translators. A primary focus of LDTA is grammarware that is generated from high-level grammar-centric specifications and thus submissions on parser generation, attribute grammar systems, term/graph rewriting systems, and other grammar-related meta-programming tools, techniques, and formalisms are encouraged. LDTA is also a forum in which theory is put to the test, in many cases on real-world software engineering challenges. Thus, LDTA also solicits papers on the application of grammarware to areas including, but not limited to, the following: - program analysis, transformation, generation, and verification, - implementation of Domain-Specific Languages, - reverse engineering and re-engineering, - refactoring and other source-to-source transformations, - language definition and language prototyping, and - debugging, profiling, IDE support, and testing. Note that LDTA is a well-established workshop similar to other conferences on (programming) language engineering topics such as SLE and GPCE, but is solely focused on grammarware. Paper Submission ------------------------- LDTA solicits papers in the following categories. - research papers: original research results within the scope of LDTA with a clear motivation, description, analysis, and evaluation. - short research papers: new innovative ideas that have not been completely fleshed out. As a workshop, LDTA strongly encourages these types of submissions. - experience report papers: description of the use of a grammarware tool or technique to solve a non-trivial applied problem with an emphasis on the advantages and disadvantages of the chosen approach to the problem. - tool demo papers: discussion of a tool or technique that explains the contributions of the tool and what specifically will be demonstrated. Each submission must clearly state in which of these categories it falls, and must not be published or submitted elsewhere. Papers are to use the standard LaTeX article style and the authblk style for affiliations; a sample of which is provided at www.ldta.info. Research and experience papers are limited to 15 pages, tool demonstration papers are limited to 10 pages, and short papers are limited to 6 pages. The final version of the accepted papers will, pending approval, be published in the ACM Digital Library and will also be made available during the workshop. Please submit your abstract and paper using EasyChair at http://www.easychair.org/conferences/?conf=ldta2012. The authors of each submission are required to give a presentation at LDTA 2011 and tool demonstration paper presentations are intended to include a significant live, interactive demonstration. The authors of the best papers will be invited to write a journal version of their paper which will be separately reviewed and, assuming acceptance, be published in journal form. As in past years this will be done in a special issue of the journal Science of Computer Programming (Elsevier Science). Invited Speaker --------------------- Janis Voigtländer (University of Bonn, Germany). Important Dates --------------------- Abstract submission: Nov. 28, 2011 Full paper submission: Dec. 5, 2011 Author notification: Jan. 20, 2012 Camera-ready papers: Feb. 05, 2012 LDTA Workshop: Mar. 31 - Apr. 1, 2012 LDTA Tool Challenge ----------------------------- The 2011 Workshop pioneered the LDTA Tool Challenge where tool developers were invited to develop solutions to a range of language processing tasks over a simple but evolving set of imperative programming languages. We expect a challenge to form part of LDTA every two years. The 2012 workshop will feature presentations devoted to a de-brief of the 2011 challenge, based on the paper currently being prepared by challenge participants. Program Committee --------------------------- Suzana Andova, Eindhoven University of Technology, The Netherlands (co-chair) Anya Helene Bagge, University of Bergen, Norway Kyung-Goo Doh, Hanyang University, Ansan, South Korea Jeff Gray, University of Alabama, USA Görel Hedin, Lund Institute of Technology, Sweden Zoltán Horváth, Eötvös Loránd University, Budapest, Hungary Zhenjiang Hu, National Institute of Informatics, Japan Roberto Ierusalimschy, Pontifícia Universidade Católica do Rio de Janeiro, Brazil Ivan Kurtev, University of Twente, The Netherlands Marjan Mernik, University of Maribor, Slovenia Nate Nystrom, University of Lugano, Switzerland João Saraiva, Universidade do Minho, Braga, Portuga Sylvain Schmitz, Ecole Normale Supérieure de Cachan, France Anthony Sloane, Macquarie University, Australia (co-chair) Robert Tairas, Inria, France Laurence Tratt, King's College London, UK Vadim Zaytsev, Centre for Mathematics & Computer Science, The Netherlands Organizing Committee ------------------------------ Anya Helene Bagge, University of Bergen, Norway Emilie Balland, INRIA, France Steering Committee --------------------------- Mark van den Brand, Eindhoven University of Technology, The Netherlands Görel Hedin, Lund University, Sweden Tony Sloane, Macquarie University, Australia Eric Van Wyk, University of Minnesota, United States

1 0

Polls on Haskellers.com
by Michael Snoyman 24 Nov '11

24 Nov '11

I noticed the recent thread about mascots, and trying to get accurate polling information. Don't consider this email to say I think we need safeguards against a poll on mascots (are people *really* trying to rig the election on this???), but I thought this might be a good features for Haskellers.com. Since we already have the "verified account" issue, we could use that to break down polls. More specifically, anyone would be allowed to vote, and then you could review results for verified users only, all logged in users, or theoretically even not-logged-in users (not sure how I feel about this one). If people would use this feature, I think I can add it next week. Michael

2 1

type level strings?
by Evan Laforge 24 Nov '11

24 Nov '11

So suppose I have a simple data type: > data Thing { > thing_id :: ThingId > , thing_stuff :: Stuff > } > newtype ThingId = ThingId String Stuff is a Monoid, and Things need to be combined as well, so: > instance Monoid Thing where > mappend (Thing id1 stuff1) (Thing id2 stuff2) > | id1 /= id2 = error "..." > | otherwise = Thing id1 (stuff1 `mappend` stuff2) > mempty = Thing $ (ThingId "dummy value?") mempty So clearly both the error and the "dummy value?" are not very nice (and mappend would need a special hack to treat the dummy as compatible with everything). I'd like to be able to lift that ID up to the type level, and then I don't have to worry about incompatible IDs and the mempty can figure out the ID from the type. Now if ThingId were a natural, I gather there's a new GHC feature for type level naturals that can do this kind of thing. Of course any string could be encoded into a large natural, but the resulting type errors would be less than readable. There is probably also a way to encode type level strings in the same way as the traditional way for type level naturals, e.g. 'data A; ... data Z;' and then a type encoding for lists. But I'm guessing that would also lead to excessive compilation times and crazy type errors. In any case, I don't think this can work even if I used naturals instead of ints, because it seems to me I can't write a function '(NatI n) => ThingId -> Thing n' without a statically knowable constant value for 'n'. Otherwise, the value has magically disappeared into the type system and I can't expect to get it back after types are erased. So I need a runtime value for the ThingId, but it still seems like it should be possible to do something better than the 'error' and "dummy value?". Maybe there's a completely different way to ensure that incompatible Things can't be mappended. Any ideas?

4 5

Quickcheck research
by Macías López 24 Nov '11

24 Nov '11

Hello: I'm a Master's student in Computer Science. I have to make a project involving some research, I'm very interested in Quickcheck and I wonder if there are some areas which need work or if there is some potential research topic related to it. In particular I know that Erlang Quickcheck has been worked on a lot and has some features like state machines or C bindings which may be useful to the Haskell community. I would appreciate any directions. Cheers, Macías López.

4 5

Re: [Haskell-cafe] Quickcheck research
by Jonathan Fischoff 24 Nov '11

24 Nov '11

> which makes me think that Arbitrary isn't the right set of > abstractions for controlling coverage of the value space. I agree with you Wren. I think what is needed is a library for expressing the distribution of values for a given type. I can see several ways of specifying distributions, directly (exponential, normal, etc), qualitative constraints (a tuple where each value is less then the next), constraints on moments (MaxEnt), etc, there are many ways that are not mutually exclusive. There are other ways to improve quickcheck. Writing arbitrary instance could be made more declarative. The process of describing an indicator function that fully determines the set of values that are valid for my type, and writing the sequence of steps necessary to make the function efficient could be separated. Combinatorial species and symbolic combinatorics are too possibilities to simplify the creation of arbitrary functions. There might be way go from list of functions to an generator. Something like make_arb :: [a -> Bool] -> Gen a That is psuedo code, since you can't reify a function. But that would be the idea, although I don't think it would work in all cases. Also, the current quickcheck workflow is to run it until a example of valid input fails a test. When this happens the example should be used in a regression. Creating unit tests automatically from failed quickcheck cases would be a time saver. Additionally the right type mutation of testing would be a great addition to quickcheck. -Jonathan

1 0

"lambda.fm" How can I use this to help the Haskell community?
by Ben Wright 24 Nov '11

24 Nov '11

A while back I somehow managed to get the domain name, "lambda.fm" and I am simply creating this post to get some ideas from the community on what it could be used for to help the FP community. So tell me what you think.

4 3

Re: [Haskell-cafe] A Mascot
by John Lato 23 Nov '11

23 Nov '11

> From: Michael Orlitzky <michael(a)orlitzky.com> > > On 11/22/11 16:52, heathmatlock wrote: >> Wasn't planning on it, but I saw some emails on the topic, so I worked >> on what I presented earlier: > > Anyway, creative design-by-committee is doomed, so my advice is to > ignore this and all other advice =) +1 (The knight is my favorite, but Da for Mascot regardless)

1 0

Fwd: XML modification
by Dmitry Olshansky 23 Nov '11

23 Nov '11

Personally I prefer xml-enumerator. You can work with xml-stream or with DOM through cursor (like XPath). I think that in your case working with stream is preferrable. You can just make an Enumeratee like >import qualified Data.Enumerator.List as EL > myEnum = EL.map f > where > f (EventBeginElement n ats) = ... -- parse attributes > f e = e 2011/11/23 Andrew Coppin <andrewcoppin(a)btinternet.com> > Hi guys. > > I've got a folder with about 80 XML files in it. I want to take each file > and make specific modifications to it. (Mostly just finding specific > attributes and changing their values to make then all consistent.) > > Now I guess it wouldn't take me /that/ long to code something from > scratch. But does anybody have a better suggestion for tools or libraries > that might be useful? > > ______________________________**_________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe> >

1 0