- Haskell - Haskell.org

Re: seeking ideas for short lecture on type classes
by Norman Ramsey 27 Jan '03

27 Jan '03

Now that I have made it abundantly clear that my understanding of type classes is highly imperfect, perhaps I will repeat my plea: * Can you recommend any interesting, elementary examples? * Of all the many articles on the topic, which few might you recommend for beginners? Would Faxen's static semantics be a good place to start? Jones's `Typing Haskell in Haskell'? One of Phil Wadler's papers (which one)? Thanks again for any help, Norman

2 1

existential typing question
by Dean Herington 27 Jan '03

27 Jan '03

Can someone explain why the type declaration for `g` is required in the following? class RT r t where rt :: r -> t data D t = Dt t | forall r. RT r t => Dr r f :: D t -> D t f = g where -- g :: D t -> D t g (Dr r) = Dt (rt r) As given above, the program evokes these error messages: with GHC 5.04.2: Bug4.hs:10: Could not deduce (RT r t1) from the context (RT r t) Probable fix: Add (RT r t1) to the existential context of a data constructor arising from use of `rt' at Bug4.hs:10 In the first argument of `Dt', namely `(rt r)' In the definition of `g': Dt (rt r) with Hugs: ERROR "Bug4.hs":6 - Cannot justify constraints in explicitly typed binding *** Expression : f *** Type : D a -> D a *** Given context : () *** Constraints : RT _6 a -- Dean

2 2

seeking ideas for short lecture on type classes
by nr＠eecs.harvard.edu 27 Jan '03

27 Jan '03

In a fit of madness, I have agreed to deliver a 50-minute lecture on type classes to an audience of undergraduate students. These students will have seen some simple typing rules for F2 and will have some exposure to Hindley-Milner type inference in the context of ML. I am soliciting advice about * Cool examples of type classes * Papers I could read to explain how to implement type classes, especially if I could show the `dictionary translation' which is then followed by ordinary Hindley-Milner type inference * Any other material on which I might base such a lecture I'm especially in need of a guide to the literature, as the `Haskell bookshelf' at haskell.org is silent on the topic of type classes. Please send me your recommendations. Norman Ramsey

5 5

Lazy evaluation alternative
by Chris Clearwater 26 Jan '03

26 Jan '03

I wonder if I could run an idea I've had by this list. It seems to me you could get some of the desired effects of lazy evaluation by using continuation passing style in code. For example, take this psuedo-code using CPS to represent an infinite data type. Using non-CPS this would be something like: ones = 1 : ones using strict evaluation this would lead to an infinite loop. However using CPS this could be represented as: ones c = c (1 : ones) where c is the continuation. This would not infinite loops as ones is still waiting for the continuation argument. Another example: natural n c = c (n : natural n+1) Again no infinite recursion! What do you think? Please CC me in any reply.

3 2

hot queue implementation
by Hal Daume III 24 Jan '03

24 Jan '03

Does anyone have an implementation of hot (heap on top) priority queues in Haskell (or perhaps ML)? 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

Last Call for Papers: Deadline February 7
by SAS 2003 24 Jan '03

24 Jan '03

---------------------------------------------------------------------- Call for Papers SAS '03 10th Annual International Static Analysis Symposium June 11-13, 2003 : San Diego, California http://www.lix.polytechnique.fr/~radhia/sas03/index.html ACM Federated Computing Research Conference FCRC 2003 http://www.acm.org/sigs/conferences/fcrc/ ---------------------------------------------------------------------- Static Analysis is increasingly recognized as a fundamental tool for high performance implementations and verification systems of programming languages. The series of Static Analysis Symposia has served as the primary venue for presentation of theoretical, practical, and application advances in the area. The 10th International Static Analysis Symposium SAS'03 will be held at the Town and Country Resort & Conference Center in San Diego (USA) as part of the Federated Computing Research Conference FCRC 2003. Previous symposia were held in Madrid, Paris, Santa Barbara, Venice, Pisa, Paris, Aachen, Glasgow and Namur. The technical program for SAS'03 will consist of invited lectures, tutorials, panels, presentations of refereed papers, and software demonstrations. Contributions are welcome on all aspects of Static Analysis, including, but not limited to: abstract interpretation, data flow analysis, verification systems, program transformation, abstract domains, optimizing compilers, theoretical frameworks, type inference, abstract model checking, complexity analysis, abstract testing, security analysis, mobile code, hardware systems, distributed systems, embedded systems. Submissions can address any programming paradigm, including concurrent, constraint, functional, imperative, logic and object-oriented programming. Survey papers that present some aspect of the above topics with a new coherence are also welcome. Papers must describe original work, be written and presented in English, and must not substantially overlap with papers that have been published or that are simultaneously submitted to a journal or a conference with refereed proceedings. Submission instructions: All submissions must be performed electronically at http://www.lix.polytechnique.fr/~radhia/sas03/submission.html. Submitted papers should be at most 15 pages excluding bibliography and well-marked appendices. Program committee members are not required to read the appendices, and thus papers should be intelligible without them. Publication: The proceedings will be published by Springer in the Lecture Notes in Computer Science series (see http://www.springer.de/comp/lncs/authors.html for the LNCS Author's Instructions). Thus, adhering to that style already in the submission is strongly encouraged. Papers should be submitted either in PostScript or PDF format and they should be interpretable by Ghostscript or Acrobat Reader. Papers must be printable on either A4 paper or US letter, and preferably on both. Selected papers will be published in a special issue of a journal. Important dates: Deadline for submissions : February 7, 2003. Notification : March 18, 2003. Deadline for reception of the final versions : March 30, 2003. The conference : June 11-13, 2003. Program Committee: Radhia Cousot (Chair) CNRS and Ecole polytechnique, France Alex Aiken University of California, Berkeley, USA Luddy Harrison Intel Corporation, USA Susan Horwitz University of Wisconsin-Madison, USA Andy King University of Kent, UK Giorgio Levi University of Pisa, Italy Michael Lowry NASA Ames Research Center, USA Laurent Mauborgne Ecole normale superieure, France Alan Mycroft Cambridge University, UK Germ�n Puebla Technical University of Madrid, Spain Francesco Ranzato University of Padova, Italy Shmuel Sagiv Tel-Aviv University, Israel David Sands Chalmers U. and U. of Goteborg, Sweden Helmut Seidl University of Trier, Germany Mary Lou Soffa University of Pittsburgh, USA Harald S�ndergaard University of Melbourne, Australia Contact info: sas03(a)lix.polytechnique.fr

1 0

Re: Lazy evaluation alternative
by Kevin S. Millikin 24 Jan '03

24 Jan '03

>>>>> "Chris" == Chris Clearwater <chris(a)sharkzone.com> writes: Chris> LIAR. You want to steal my idea for yourself! It's MINE! :) I hate to be the one to break it to you, but we used to routinely show this trick to Intro to CS students. Chris> But anyways, it was to show that when a list is defined Chris> like that, (natural m) becomes a list itself because it is Chris> of the form: \c -> c hd tl after partial evaluation. Yes. But it's not the CPS that delays evaluation, it's just the lambda. Switching to a strict language, Scheme, one would write: > (define ones (lambda () (cons 1 ones))) Explicitly delaying the evaluation of (cons 1 ones) by putting it under a lambda. We *could* perform the CPS translation, but it's not necessary to delay evaluation, lambda does that all by itself. > ones #<procedure> > (ones) (1 . #<procedure>) > (cdr (ones)) #<procedure> > ((cdr (ones))) (1 . #<procedure>) Of course, if we wanted *lazy* evaluation, we would want to avoid performing the cons more than once if it is demanded more than once. We have to use something other than lambda for that: > (define ones (delay (begin (printf "forcing...~n") (cons 1 ones)))) > ones #<procedure> > (force ones) forcing... (1 . #<procedure>) > (force ones) (1 . #<procedure>) > (cdr (force ones)) #<procedure> > (force (cdr (force ones))) (1 . #<procedure>) Notice how many times (cons 1 ones) got evaluated. So your trick *is* used to implement lazy evaluation in other languages. It's not very pleasant if you write a lot of lazy code, because you have to explicitly suspend evaluation of values using delay and explicitly demand evaluation using force. Thus, we have lazy languages that make the laziness implicit. -- Kevin S. Millikin Architecture Technology Corporation Research Scientist Specialists in Computer Architecture (952)829-5864 x. 162 http://www.atcorp.com

3 2

Re: Lazy evaluation alternative
by Chris Clearwater 24 Jan '03

24 Jan '03

On Fri, Jan 24, 2003 at 03:07:48PM +0100, Thomas Johnsson wrote: > > > > > Yes I am. But the + should be in CPS form anyways to be perfectly > > correct, so: natural n c = (+) n 1 (\m -> c n : (natural m)) > > > > I think Jerzy (in his usual polite manner :-) refers to the every group has it's moshez (don't ask :) > cons operator, the :, which in a strongly typed language > the right argument, the tail, is required to be a list. > The function is declared as natural n c = ..., > so (natural m) must be a funcion. Well, let's pretend I made my own datatype then that supports the right type class interfaces, and has a function as a tail :) But also, this brings me to another idea! Data structures should be built from lambdas and CPS! For example, a list of integers: 1 : 2 : 3 list = \c -> c 1 (\c -> c 2 nil) now: natural n c = c n (natural n+1) full blown CPS: natural n c = (+) n 1 (\m -> c n (natural m)) so, here (nautral m) _is_ a list just like the above list! > Might I guess that you come from the lisp / scheme world? No. :) > > Regards, > -- Thomas > >

3 2

Lazy evaluation alternative
by Chris Clearwater 24 Jan '03

24 Jan '03

I wonder if I could run an idea I've had by this list. It seems to me you could get some of the desired effects of lazy evaluation by using continuation passing style in code. For example, take this psuedo-code using CPS to represent an infinite data type. Using non-CPS this would be something like: ones = 1 : ones using strict evaluation this would lead to an infinite loop. However using CPS this could be represented as: ones c = c (1 : ones) where c is the continuation. This would not infinite loop as ones is still waiting for the continuation argument. Another example: natural n c = c (n : natural n+1) Again no infinite recursion! What do you think? Please CC me in any reply.

2 2

A problem about hGetContents
by Nick Name 24 Jan '03

24 Jan '03

I would like to use hGetContents just to retrieve the list of the lines of a file, but if I code a function like: linesFromFile :: FilePath -> IO [String] linesFromFile f = do h <- openFile f ReadMode l <- hGetContents h hClose h return (lines l) I obviously always get the empty list as a result. How should I code the function? Vincenzo -- Teatri vuoti e inutili potrebbero affollarsi se tu ti proponessi di recitare te [CCCP]

4 6