[Haskell-cafe] Postdoctoral Research Position at Yale University
Postdoctoral Research Position at Yale University The Nettle Project in the Computer Science Department at Yale University seeks applicants for a one-year (minimum) postdoctoral research position. The successful candidate will apply modern, high-level programming language ideas (such as embodied in Haskell) to help design and implement a language for the control of BGP-based network routers, with the goal of realizing high-level networking protocols for traffic engineering, security, and related networking concerns. The ideal candidate will have strength both in programming language concepts and implementation techniques, as well as networking fundamentals. A PhD in computer science or related field is required. Yale is an affirmative action, equal opportunity employer. Interested candidates should send their CV or resume to Professor Paul Hudak at paul.hu...@yale.edu. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] on starting Haskell-Edu, a new education-related Haskell-related mailing list
Simon Marlow wrote: My main concern here is that the remit for the new list is not clear enough. I can see a potential need for two lists: * a list for discussion related to teaching Haskell; * a list devoted to those learning Haskell, with a less research- oriented feel than haskell-cafe. it's not obvious to me that both of those needs should be served by a single list. I believe it's important that the mailing lists served by haskell.org should have clear non-overlapping topics. So I suggest that we add haskell-edu for the purposes of discussing the use and teaching of Haskell in education. For the second point above, I'd be inclined not to add a new list, but I don't feel that strongly - if there's a concensus in favour of adding haskell-beginners (for example), that would be fine. Cheers, Simon Using Simon's names, I think that there is a greater need for haskell-beginners than for haskell-edu. Despite the friendly people on haskell-cafe, it is very intimidating, and very busy (sadly, I've mostly stopped reading it for the latter reason). I don't think that haskell-cafe serves well at all as a forum for beginners, whereas it might serve just fine as a forum for instructors. In any case, these are two distinct purposes, and I agree with Simon that it's probably unwise to have a single mailing list for both. I would vote for starting a haskell-beginners list and see how it goes. I think that a decent number of experienced people will chip in to answer questions (they don't have to be experts -- just good at explaining things), and in my experience beginners like to help fellow beginners -- i.e. it will sustain itself. I would also be interested in a haskell-edu list, but as I said before I don't think the demand for it is as great as that for haskell-beginners. By the way, the haskell-art mailing list is not very active, but it has served a useful role. I wonder if it would help to have a description of it (and any new lists that we create) to the descriptions at: http://www.haskell.org/haskellwiki/Mailing_lists -Paul Hudak ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] anybody can tell me the pronuncation of haskell?
Well, Haskell was Curry's first name, so perhaps we should use "Moses", which was Schönfinkel's first name, and has some nice biblical metaphors :-) -Paul [EMAIL PROTECTED] wrote: Tim Chevalier(*) writes: I think to ease the acceptance of Haskell in the broader world, we should just change the name to Schönfinkel. On the other hand, is better not to try Curry, since the French pronounce it: Queue-rhrhrh. This is for me absolutely inacceptable and scandalous, since thus, they confuse him with Madame Curie, who was Polish, and I am a patriot. And after a few years, people from some Other Respectable Cultures will think that Haskell discovered Radium (for French: Hhhhudiomm). Thank you for this inspiring and awfully useful discussion. Jerzy K. (K is pronounced as K, the name of some heroes of Kafka, who was a Germanophone Czech Jew. Do not confuse his K with another K, by Dino Buzzati, who was Italian). === (*) Pronounced //possibly// as Che Guevara, with Guevara replaced by Valier. Now, Valier is a mountain in Les Pyrenées, (http://www.pyrenees-team.com/pteam/photos/valier/valierg/18) and the first person who climbed it was a bishop. The second one was also a bishop, so perhaps Tim should be careful. Some more messages on this subject, and I will have really to call an ambulance so they can take me away, far from Internet... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New to Haskell
If the semantics of a language says that a function
f is equivalent to a function g, but there is a function h such that
h(f) is not equivalent to h(g), then h cannot be a function. Therefore
that language cannot be a (purely) functional language.
That is the pure and simple reason why functions are not Showable in
Haskell.
This doesn't mean that it isn't possible to show functions -- even
compiled code can usually be reverse-engineered to yield some printable
version of an equivalent function -- but if the language is to remain
pure, such facilities should be relegated to the development tools
(debugger, etc.).
-Paul
Benja Fallenstein wrote:
Hi Henning,
On Dec 18, 2007 3:53 PM, Henning Thielemann
[EMAIL PROTECTED] wrote:
Since this was discussed already here, I summed it up in:
http://www.haskell.org/haskellwiki/Show_instance_for_functions
I find the discussion under "theoretical answer" unsatisfying. The
property that a Show instance for functions would break is
extensionality, and while extensionality is a desirable trait and
matches the common mathematical intuitions, a system with intensional
functions certainly isn't "unmathematical" or impure.
Further, even with extensionality, we can (with compiler support) in
principle have Show instances other than enumerating the graph. At
least for simple non-recursive functions, showing the Bhm tree of the
function could be useful (except that you loop forever if you
encounter bottom somewhere, of course, instead of printing "bottom" as
you would if you could print the actual Bhm tree). For example, id
would be shown as "\a - a," maybe would be shown as "\a b c - case c
of { Just d - b d; Nothing - a }," and all would be shown as "\a -
case a of { (b:c) - case b of { False - False; True - case c of {
(d:e) - case d of { False - False" et cetera ad infinitum.
Of course, for functions on ints this would indeed reduce to
enumerating the graph, printed as an infinite case _expression_.
- Benja
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New to Haskell
Benja Fallenstein wrote: Not so fast :-) Caveat one, there may be useful ways to for functions to implement Show that don't conflict with extensionality (i.e., the property that two functions are equal if they yield the same results for all inputs). Sure, and I suppose one way to do this is to put the show function for functions into the IO monad -- then you can't inspect the results. But if you want to inspect the result, then I have no idea how to do this. Caveat two, we generally assume extensionality when reasoning about Haskell, but it's entirely possible to give a semantics for Haskell that doesn't assume extensionality. IMHO, a good answer to the question why functions aren't showable in Haskell needs to explain why we prefer our semantics to be extensional, not say that by god-given fiat, Haskell is extensional, so we can't show functions. Well, my caveat was that the Haskell designers wanted it this way. So you are essentially rejecting my caveat, rather than creating a new one. :-) -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New to Haskell
Benja Fallenstein wrote:
I mean, I reject the answer "They wanted it this way" because I think
the answer should be, "They wanted it this way because They looked at
substituting equals under a lambda, and They saw it was good" ;-)
Your version of the answer is in fact correct, but is just an
elaboration of the original one.
So, I don't see what your point is...
Sure, and I suppose one way to do this is to put the show function for
functions into the IO monad -- then you can't inspect the results. But
if you want to inspect the result, then I have no idea how to do this.
If you can show and enumerate the argument type and show the result
type of a function, one way is to enumerate the graph of the function.
Yes, but this requires a STANDARD way to do this -- meaning that the
underlying domains are enumerable in a standard way. I don't think
that is always possible. And of course you may have an infinite graph,
whereas the function itself is finite.
Regarding the rest of your message: I don't see how this helps, since
some terms do not have head-normal forms. Even in the pure lambda
calculus there are terms that denote the same value but that are not
convertible to one another. It seems that at best this approach would
yield only partial success.
-Paul
The wiki page gives the example,
Prelude \x - x+x
functionFromGraph [(0,0), (1,2), (2,4), (3,6),
Interrupted.
If you have special compiler support, and consider a fragment of
Haskell that contains only functions -- i.e., no algebraic data types,
no Ints etc. (it's kind of a boring fragment!, but you can have Church
numbers) --, you can reduce the function to head normal form. Head
normal form looks like this:
\VAR1 VAR2 ... VARm - VARi EXPR1 ... EXPRn
and there is a reduction strategy that finds the head normal form of
an arbitrary _expression_ if there is one; a proof that if there isn't
one, the _expression_ denotes bottom; and a proof that if you have two
HNFs, and they differ in the part before EXPR1 or differ in the number
of EXPRjs, these HNFs denote different values.
Therefore, when you have reduced the function to HNF, you can print
"\VAR1 VAR2 ... VARm - VARi "
(or more precisely, you can write a lazy 'show' that yields the above
characters as soon as it has computed the HNF). Then, you go on to
recursively compute the HNF of EXPR1, and you show that inside
parantheses.
Some examples:
show (\x - x) == "\a - a"
show (.) == "\a b c - a (b c)"
(let fix f = f (fix f) in show fix)
== "\a - a (a (a (a (a.
[Unless I'm making some stupid mistake] It's well-established that
this is computable and doesn't break extensionality (i.e., that
applying this show to two functions with the same extension will give
the same result -- or conversely, if show gives different results for
two functions, there are arguments for which these functions yield
different results).
By itself, this isn't very interesting, but I *think* you should be
able to add algebraic data types and case expressions to this fragment
of Haskell and still do "essentially" the same thing. Then, you could
show, for example,
show either == "\a b c - case c of { Left d - a d; Right e - b e }"
- Benja
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Yampa / AFRPVectorSpace.hs
Certainly looks like a typo to me! Peter Verswyvelen wrote: While studying the vector space class in AFRP, I encountered the following strange code: class Floating a = VectorSpace v a | v - a where ... v1 ^-^ v2 = v1 ^+^ v1 -- (negateVector v2) I have no idea why the (negateVector v2) has been commented out, but surely this must be a typo? Cheers, Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] [Fwd: PADL'08: Call for Participation (Early Reg. Deadline: Dec 13)]
___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell] Re: PADL'08: Call for Participation (Early Reg. Deadline: Dec 13)
CALL FOR PARTICIPATION!!! Tenth International Symposium on Practical Aspects of Declarative Languages 2008 (PADL '08) http://www.ist.unomaha.edu/padl2008/ San Francisco, USA January 7-8, 2008 Co-located with ACM POPL'08 You are cordially invited to the Tenth International Symposium on Practical Aspects of Declarative Languages that will be held on Jan 7-8, 2008 right before ACM POPL. The program includes invited talks by two eminent practitioners of declarative techniques/languages: John Launchbury and Walter Wilson. If you are attending ACM POPL, we encourage you to stay for a whole week in San Francisco and attend PADL as well. Please note that the deadline for early registration is fast approaching. Invited Talks: o Industrial Functional Programming John Launchbury o Large Scale Logic Servers in Business and Government Walter Wilson LIST OF ACCEPTED PAPERS o Efficient Reasoning for Nogoods in Constraint Solvers with BDDs Sathiamoorthy Subbarayan. o High-Level Database Programming in Curry Bernd Brassel, Michael Hanus and Marion Mueller. o Parser Combinators for Ambiguous Left-Recursive Grammars Richard Frost, Rahmatullah Hafiz and Paul Callaghan. o Switched-on Yampa. Declarative Programming of Modular Synthesizers George Giorgidze and Henrik Nilsson. o The Role of Abduction in Declarative Authorization Policies Moritz Y. Becker and Sebastian Nanz. o Towards a High-Level Implementation of Execution Primitives for Non-restricted, Independent And-parallelism Amadeo Casas, Manuel Carro and Manuel Hermenegildo. o Certified development tools implementation in Objective Caml B. Pagano, O. Andrieu, B. Canou, E. Chailloux, J-L Colaco, T. Moniot and P. Wang. o DCGs + Memoing = Packrat Parsing: But is it worth it? Ralph Becket and Zoltan Somogyi. o Model-Based Testing of Thin-Client Web Applications and Navigation Input P. Koopman, P. Achten and R. Plasmeijer. o Unification of Arrays in Spreadsheets with Logic Programming Phil Cox and Patrick Nicholson. o A Generic Programming Toolkit for PADS/ML: First-Class Upgrades for Third-Party Developers M. Fernandez, K. Fisher, J. Nathan Foster, M. Greenberg and Y. Mandelbaum. o Automatic Coding Rule Conformance Checking Using Logic Programming G. Marpons, J. Mario, A. Herranz, L. Fredlund, M. Carro and J. J. Moreno-Navarro. o Multi-threading programming in Logtalk Paulo Moura, Paul Crocker and Paulo Jorge Nunes. o Scheduling light-weight parallelism in ARTCOP Jost Berthold, Abyd Al Zain and Hans-Wolfgang Loidl. o Specialising Simulator Generators for High-Performance Monte-Carlo Methods G. Keller, H. Chaffey-Millar, M. Chakravarty, D. Stewart and C. Barner-Kowollik. o Hierarchical Master-Worker Skeletons Jost Berthold, Mischa Dieterle, Rita Loogen and Steffen Priebe. o Comprehension and dependency analysis of aspect-oriented programs through declarative reasoning Laleh Mousavi Eshkevari, Venera Arnaoudova and Constantinos Constantinides. o An Improved Continuation Call-Based Implementation of Tabling Pablo Chico de Guzman, Manuel Carro, Manuel Hermenegildo, Claudio Silva and Ricardo Rocha. o Matchete: Paths through the Pattern Matching Jungle Martin Hirzel, Nathaniel Nystrom, Bard Bloom and Jan Vitek. o Flexible, Rule-based Constraint Model Linearisation Sebastian Brand, Gregory Duck, Jakob Puchinger and Peter Stuckey. Conference Organization: General Chair: Hai-Feng Guo Program Chair: Paul Hudak David Warren ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Semantics of uniqueness types for IO (Was: Why can't Haskell be faster?)
One can certainly use an operational semantics such as bisimulation, but you don't have to abandon denotational semantics. The trick is to make output part of the "final answer". For a conventional imperative language one could define, for example, a (lifted, recursive) domain: Answer = Terminate + (String x Answer) and then define a semantic function "meaning", say, such that: meaning loop = _|_ meaning loop' = "x", "x", ... In other words, loop denotes bottom, whereas loop' denotes the infinite sequence of "x"s. There would typically also be a symbol to denote proper termination, perhaps . A good read on this stuff is Reynolds book "Theories of Programming Languages", where domain constructions such as the above are called "resumptions", and can be made to include input as well. In the case of Clean, programs take as input a "World" and generate a "World" as output. One of the components of that World would presumably be "standard output", and that component's value would be _|_ in the case of loop, and "x", "x", ... in the case of loop'. Another part of the World might be a file system, a printer, a missile firing, and so on. Presumably loop and loop' would not affect those parts of the World. If returning one World is semantically problematical, one might also devise a semantics where the result is a sequence of Worlds. -Paul Arnar Birgisson wrote: Hi there, I'm new here, so sorry if I'm stating the obvious. On Nov 1, 2007 2:46 PM, apfelmus [EMAIL PROTECTED] wrote: Stefan Holdermans wrote: Exposing uniqueness types is, in that sense, just an alternative to monadic encapsulation of side effects. While *World - (a, *World) seems to work in practice, I wonder what its (denotational) semantics are. I mean, the two programs loop, loop' :: *World - ((),*World) loop w = loop w loop' w = let (_,w') = print "x" w in loop' w' both have denotation _|_ but are clearly different in terms of side effects. (The example is from SPJs awkward-squad tutorial.) Any pointers? For side-effecting program one has to consider bisimilarity. It's common that semantically equivalent (under operational or denotational semantics) behave differently with regard to side-effects (i/o) - i.e. they are not bisimilar. http://en.wikipedia.org/wiki/Bisimulation Arnar ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell libraries for computer vision
Henning Thielemann wrote: On Mon, 15 Oct 2007, Don Stewart wrote: http://alberrto.googlepages.com/easyvision An experimental Haskell system for fast prototyping of computer vision and image processing applications. Looks ridiculously cool. Image processing with Haskell - really interesting. I know of an older approach: Prototyping Real-Time Vision Systems: An Experiment in DSL Design by Alastair Reid et.al. Yes, see: http://haskell.org/yale/papers/padl01-vision/index.html http://haskell.org/yale/papers/icse99/index.html -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Troubles understanding memoization in SOE
Henning Thielemann wrote: On Wed, 26 Sep 2007, Peter Verswyvelen wrote: I hope I won't come to the conclusion that after one year learning the cool lazy functional programming language Haskell (which I want to use for making simple videogames in a clean way for teaching), I haven't tested it, but know of the existence of Haskell in Space: http://www.informatik.uni-bremen.de/~cxl/lehre/pi3.ws01/asteroids/ Also see these two: http://www.haskell.org/haskellwiki/Frag http://haskell.org/yale/papers/haskell-workshop03/index.html -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Troubles understanding memoization in SOE
Peter Verswyvelen wrote: I thought the lambda function that memo1 returns would be called over and over again, and instead of reevaluating the stream from the beginning, it would just return the stream since it is in the cache, but actually it just gets called twice in recursive situations: the first time it evaluates y = f x, stores the thunk in the cache, and returns the thunk, the second time it finds the same thunk in the cache, and then computation of the rest of the stream continues without consulting the cache anymore right? Actually the function may be called more than twice -- but each time after the first, it uses the cached value instead of recomputing it. Even in a non-recursive situation, such as x + x, this saves some computation. The recursive situation just make it worse. From my clumsy explanation you can see that I'm still thinking too imperative, too eager. Haskell is more lazy than I am, which is an incredible achievement :-) The confusing thing here is that it is a combination of functional and imperative -- the functional evaluation is happening lazily, but the unsafe stuff causes some imperative side effects, namely the updating of the cache. It would really help if I could see the lazy computation; do you think this kind of memo code is traceable using HAT? I don't know -- I've never used HAT! I'll guess I'll have to check out arrows / yampa again. A year ago I did not understand a single thing in those papers, but I should try it again now I read the SOE book :-) Ok, good luck. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Troubles understanding memoization in SOE
Hi Peter. Paul Liu replied well to your later email, but I just wanted to point out that memoization is not being used here to make the recursion work -- lazy evaluation does just fine. Rather, the memoization is being used for what it's normally good for, namely, to avoid repeated computation. In a recursive context having multiple references to the recursive variable, this can result in an exponential blow-up that grinds the computation to a halt very quickly. I suspect that when you observed your program getting stuck that it was simply blowing up so quickly that it /appeared /stuck. Also, the reason that there is no space leak in the memoization process is that, as Paul Liu pointed out, I only save the last value -- that's the reason for the IORef. The last value is sufficient because FAL is carefully designed so that it executes each time step completely before the next one begins. Finally, I should point out this is the only place in SOE where I use unsafe features in Haskell. I felt so bad about it that you'll notice that I don't even discuss it in the text! Interestingly, also as Paul Liu pointed out, switching to arrows solves the problem, but in a subtle way that we only recently realized. The paper that Paul cited (http://www.cs.yale.edu/~hl293/download/leak.pdf) describes this in detail. I hope this helps, -Paul Hudak Peter Verswyvelen wrote: Hi, in SOE, the following memoization function is implemented: memo1 :: (a-b) - (a-b) memo1 f = unsafePerformIO $ do cache - newIORef [] return $ \x - unsafePerformIO $ do vals - readIORef cache case x `inCache` vals of Nothing - do let y = f x writeIORef cache [(x,y)] -- ((x,y) : --if null vals then [] else [head vals]) return y Just y - do return y inCache :: a - [(a,b)] - Maybe b x `inCache` [] = Nothing x `inCache` ((x',y'):xys) = if unsafePtrEq x x' then Just y' else x `inCache` xys This is then used in type Time = Float type UserAction = G.Event data G.Event = Key Char Bool | Button Point Bool Bool | MouseMove Point | Resize | Closed deriving Show newtype Behavior a = Behavior (([Maybe UserAction],[Time]) - [a]) newtype Event a = Event (([Maybe UserAction],[Time]) - [Maybe a]) Behavior fb `untilB` Event fe = memoB $ Behavior (\uts@(us,ts) - loop us ts (fe uts) (fb uts)) where loop (_:us) (_:ts) ~(e:es) (b:bs) = b : case e of Nothing - loop us ts es bs Just (Behavior fb') - fb' (us,ts) memoB :: Behavior a - Behavior a memoB (Behavior fb) = Behavior (memo1 fb) If I understand it correctly, the memoization is required because otherwise recursive streams wouldn't work. For example, in the Pong game example, a ballPositionX stream is generated by integrating a ballVelocityX stream, but the ballVelocityX stream changes sign when the ball hits the left or right walls, and to determine that event, the ballPositionX stream is required. So both streams are mutually recursive, and without memoization, the program would be stuck (at least my own FRP experiments, which don't use memoization yet, gets stuck :-)). Another trick to prevent this, is the b : case e of code in untilB, which causes the event to be handled a bit too late, to avoid cyclic interdependencies. I hope I got that right. Now my questions. So, the keys (x) and values (y) in (memo1 fb) are streams (aka infinite lists)? More correctly, memo1 uses a pointer to the head of the list as a key, for fast comparing (as you can't compare infinite lists)? But since both key and value are infinite streams, won't this approach cause a serious space leak because the whole list cannot be reclaimed by the garbage collector? So the full ballPositionX and ballVelocityX streams would remain in memory, until the program exits? Since this doesn't happen when I run the SOE examples (I guess!), I clearly misunderstand this whole thing. I could explain it when the pointer to the list is actually a pointer to the delayed computation (a thunk?) of the tail, but the code doesn't seem to do that. Thanks for any help, I hope I explained the problem well enough. Peter Verswyvelen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] let and fixed point operator
ok wrote: What is so bad about f x = g x'' where x'' = x' + transform x' = x * scale (if you really hate inventing temporary names, that is). There's nothing at all wrong with this, assuming it's what you meant to type :-), and it might even correspond perfectly to the mathematical notation used in some textbook. But I would argue that this example is pretty simple, and that if there were a lot of xs and x's and x''s then the chance of making a typing mistake is greater, I believe, than if you had used x, xscaled, and xtransformed. (On the other hand this is all pretty subjective... :-) -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] let and fixed point operator
Andrew Coppin wrote: OK, so it's only tangentally related, but... do you have *any idea* how many times I've written something like let x = (some complex function of x) in (some other complex function of x) when in fact what I *meant* to do was type x' instead of x?! I try not to use primes (x', x'', etc.) on variables for exactly this reason, and instead try to use more descriptive names, such as newx, or y, or whatever. Of course you can still make typing mistakes, but that's always the case... -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Explaining monads
I've seen the analogy with recipes used before, but I think that you need to be careful when you try to distinguish the analogy to monads from the analogy to functions. The reason is that, in the one-of-many ways that I view monads, a monad is just a high-order /function /that abstracts away function composition. In particular, if I have an action f, and an action g, I can think of them as recipes, because I can combine them via f = g. It's only after I combine all of my actions together that I apply the result to my input (via run). Well, that's just like function composition. In particular, if I have a function f, and a function g, I can think of them as recipes, because I can combine them via f . g. It's only after I combine all of my functions together that I apply the result to my input. -Paul Sebastian Sylvan wrote: On 14/08/07, Dan Piponi [EMAIL PROTECTED] wrote: On 8/14/07, Sebastian Sylvan [EMAIL PROTECTED] wrote: Well that's easy, don't use the recipe analogy to explain code, use it for monadic values exclusively, and you avoid the confusion entirely! I don't think it's that complicated. It certainly is complicated. I think I have a good grasp of monads to the point where I can tease novel monads (and comonads) out from algorithms that people previously didn't see as monadic. And yet I still don't understand what you are saying (except with respect to one specific monad, IO, where I can interpret 'action' as meaning an I/O operation). Monads have a monadic type. They represent an abstract form of an action, which can be viewed as an analogy to real-world cooking recipes. All functions can be viewed as recipes. (+) is a recipe. Give me some ingredients (two numbers) and I'll use (+) to give you back their sum. No, (+) is a function, not a recipe. Again, you're introducing confusion because you use the same analogy for two *different* things. Use it for one of the things and you don't have that problem. I want to use recipe to mean an abstraction for an action. It could litterally be a text string containing the C code required to do a particular IO action, for example. (+) isn't an abstraction in the same sense, it *is* the action itself. (+) is the actual value of the function that will add two numbers together. A monadic value is an abstract recipe that you can't actually use directly (you can only combine them, and if you're lucky you can perform them once you're done combining them, e.g. ST, but not IO). As long as you don't deliberately confuse things by using the same analogy for two different things I don't see where confusion would set in. If I was one of your students and you said that monads are recipes I would immediately ask you where the monads are in my factorial program regardless of whether you had introduced one or two different analogies for recipes. Why would you? I really don't see where you would get that idea? If I tell you that a function returns a fruit, would you ask where the fruit in your factorial program is? Probably not. Why would you go off and take an analogy for monads and apply it to something completely different and still think the analogy holds? A function is *not* a recipe in this analogy, it's just a function (which you hopefully should've covered by the time you get to monads. Monadic values, and *only* monadic values (not functions!) are to be viewed as analogous to real world cooking recipes in this analogy. Functions shouldn't. If you start mixing things together it will get confused, so just don't! I don't think this is very difficult to understand, so if you still don't get it, I think you're just going to have to read it again because I can't explain it any better, and in my experience, newbies tend to understand this analogy within seconds (maybe that's the problem, you're not a newbie)... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] [Fwd: PADL 2008: Call for Papers]
Original Message Subject:PADL 2008: Call for Papers Date: Sat, 4 Aug 2007 19:25:58 -0500 (CDT) From: Gopal Gupta [EMAIL PROTECTED] [ Colleagues, note that this will be the 10th PADL; We strongly urge you to submit papers, the deadline is only 3 weeks way] CALL FOR PAPERS!!! Tenth International Symposium on Practical Aspects of Declarative Languages 2008 (PADL '08) http://www.ist.unomaha.edu/padl2008/ San Francisco, USA January 7-8, 2008 Co-located with ACM POPL'08 Declarative languages build on sound theoretical bases to provide attractive frameworks for application development. These languages have been successfully applied to vastly different real-world situations, ranging from data base management to active networks to software engineering to decision support systems. New developments in theory and implementation have opened up new application areas. At the same time, applications of declarative languages to novel problems raises numerous interesting research issues. Well-known questions include designing for scalability, language extensions for application deployment, and programming environments. Thus, applications drive the progress in the theory and implementation of declarative systems, and benefit from this progress as well. PADL is a forum for researchers and practitioners to present original work emphasizing novel applications and implementation techniques for all forms of declarative concepts, including, functional, logic, constraints, etc. Topics of interest include: * innovative applications of declarative languages; * declarative domain-specific languages and applications; * practical applications of theoretical results; * new language developments their impact on applications; * evaluation of implementation techniques on practical applications; * novel uses of declarative languages in the classroom; and * practical experiences PADL 08 welcomes new ideas and approaches pertaining to applications and implementation of declarative languages. PADL 08 will be co-located with the ACM POPL. IMPORTANT DATES AND SUBMISSION GUIDELINES Paper Submission: August 24, 2007 Notification: September 27, 2007 Camera-ready: October 23, 2007 Symposium: January 7-8, 2008 Authors should submit an electronic copy of the full paper (written in English) in Postscript (Level 2) or PDF. Papers must be no longer than 15 pages, written in 11-point font and with single spacing. Since the final proceedings will be published as Lecture Notes in Computer Science by Springer Verlag, authors are strongly encouraged to use the LNCS paper formatting guidelines for their submission. Each submission must include on its first page the paper title; authors and their affiliations; contact author's email and postal addresses, telephone and fax numbers, abstract, and three to four keywords. The keywords will be used to assist us in selecting appropriate reviewers for the paper. If electronic submission is impossible, please contact the program chair for information on how to submit hard copies. MOST PRACTICAL PAPER AWARD The Most Practical Paper award will be given to the submission that is judged by the program committee to be the best in terms of practicality, originality, and clarity of presentation. The program committee may choose not to make an award, or to make multiple awards. Contacts: For information about papers and submissions, please contact the Program Chair: Paul Hudak PC co-Chair - PADL 2008 Department of Computer Science Yale University P.O. Box 208285 New Haven, CT 06520 - 8285 Email: [EMAIL PROTECTED] David S. Warren PC co-Chair - PADL 2008 Department of Computer Science Stony Brook University Stony Brook, NY Email: [EMAIL PROTECTED] For other information about the conference, please contact: Hai-Feng Guo General Chair - PADL 2008 Department of Computer Science College of Information Science Technology University of Nebraska at Omaha Omaha, NE, U.S.A. Email: [EMAIL PROTECTED] Sponsored by: COMPULOG Americas (http://www.cs.nmsu.edu/~complog) and University of Nebraska at Omaha ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell-cafe] [Fwd: PADL 2008: Call for Papers]
Original Message Subject:PADL 2008: Call for Papers Date: Sat, 4 Aug 2007 19:25:58 -0500 (CDT) From: Gopal Gupta [EMAIL PROTECTED] [ Colleagues, note that this will be the 10th PADL; We strongly urge you to submit papers, the deadline is only 3 weeks way] CALL FOR PAPERS!!! Tenth International Symposium on Practical Aspects of Declarative Languages 2008 (PADL '08) http://www.ist.unomaha.edu/padl2008/ San Francisco, USA January 7-8, 2008 Co-located with ACM POPL'08 Declarative languages build on sound theoretical bases to provide attractive frameworks for application development. These languages have been successfully applied to vastly different real-world situations, ranging from data base management to active networks to software engineering to decision support systems. New developments in theory and implementation have opened up new application areas. At the same time, applications of declarative languages to novel problems raises numerous interesting research issues. Well-known questions include designing for scalability, language extensions for application deployment, and programming environments. Thus, applications drive the progress in the theory and implementation of declarative systems, and benefit from this progress as well. PADL is a forum for researchers and practitioners to present original work emphasizing novel applications and implementation techniques for all forms of declarative concepts, including, functional, logic, constraints, etc. Topics of interest include: * innovative applications of declarative languages; * declarative domain-specific languages and applications; * practical applications of theoretical results; * new language developments their impact on applications; * evaluation of implementation techniques on practical applications; * novel uses of declarative languages in the classroom; and * practical experiences PADL 08 welcomes new ideas and approaches pertaining to applications and implementation of declarative languages. PADL 08 will be co-located with the ACM POPL. IMPORTANT DATES AND SUBMISSION GUIDELINES Paper Submission: August 24, 2007 Notification: September 27, 2007 Camera-ready: October 23, 2007 Symposium: January 7-8, 2008 Authors should submit an electronic copy of the full paper (written in English) in Postscript (Level 2) or PDF. Papers must be no longer than 15 pages, written in 11-point font and with single spacing. Since the final proceedings will be published as Lecture Notes in Computer Science by Springer Verlag, authors are strongly encouraged to use the LNCS paper formatting guidelines for their submission. Each submission must include on its first page the paper title; authors and their affiliations; contact author's email and postal addresses, telephone and fax numbers, abstract, and three to four keywords. The keywords will be used to assist us in selecting appropriate reviewers for the paper. If electronic submission is impossible, please contact the program chair for information on how to submit hard copies. MOST PRACTICAL PAPER AWARD The Most Practical Paper award will be given to the submission that is judged by the program committee to be the best in terms of practicality, originality, and clarity of presentation. The program committee may choose not to make an award, or to make multiple awards. Contacts: For information about papers and submissions, please contact the Program Chair: Paul Hudak PC co-Chair - PADL 2008 Department of Computer Science Yale University P.O. Box 208285 New Haven, CT 06520 - 8285 Email: [EMAIL PROTECTED] David S. Warren PC co-Chair - PADL 2008 Department of Computer Science Stony Brook University Stony Brook, NY Email: [EMAIL PROTECTED] For other information about the conference, please contact: Hai-Feng Guo General Chair - PADL 2008 Department of Computer Science College of Information Science Technology University of Nebraska at Omaha Omaha, NE, U.S.A. Email: [EMAIL PROTECTED] Sponsored by: COMPULOG Americas (http://www.cs.nmsu.edu/~complog) and University of Nebraska at Omaha ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Equational Reasoning goes wrong
Note that you can take any closed term e and do the following equational reasoning: e == let x = e in x == let x = x in x == _|_ Technically, though, this is not wrong, in that it is still consistent, where consistency is defined using the usual information ordering on domains. Conventional equational reasoning is consistent, it's just that it may lose information. And in that sense, it doesn't have to lose everything at once -- for example with data structures one could go from (e1,e2), say, to (_|_,e2), to (_|_,_|_), and finally to _|_. As mentioned by a few others, constraining equational reasoning so that information is not lost has been studied before, but I'm not sure what the state-of-the-art is -- does anyone know? -Paul Neil Mitchell wrote: Hi Haskell is known for its power at equational reasoning - being able to treat a program like a set of theorems. For example: break g = span (not . g) Which means we can replace: f = span (not . g) with: f = break g by doing the opposite of inlining, and we still have a valid program. However, if we use the rule that anywhere we encounter span (not . g) we can replace it with break g then we can redefine break as: break g = break g Clearly this went wrong! Is the folding back rule true in general, only in specific cases, or only modulo termination? Thanks Neil ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: historical question about Haskell and Haskell Curry
Jon Fairbairn wrote: If not, why isn't Haskell called "Alonzo"? ;-) I think that was one of the suggestions made among many others. Haskell has the advantage of sounding less like a person's name (which might have been why Curry didn't like it) Actually, the more compelling reason we chose "Haskell" over "Alonzo" was that, at the time, Church was alive -- he died in 1995 -- whereas Curry was not -- he died in 1982. We felt uncomfortable naming the language after someone who still alive (however odd that may sound). -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsers are monadic?
Hi Claus. I am sympathetic with your comments regarding monads and continuations. It's interesting to note that the original I/O system in Haskell was based on streams and continuations. The continuation version had two continuations in fact -- one for success and one for failure. For example, readFile had the type: readFile :: Name - FailCont - StrCont - Behaviour Here StrCont was the success continuation, which took a string (the file contents) as argument. I rather liked the flexibility that this offered -- since I/O errors were fairly common, it made sense to give success and failure equal status. The down-side of using continuations is that you have to carry them around explicitly, so one might argue that they clutter the code a bit, and that was one of the advantages of switching to monads. On the other hand, one could argue that having them explicit makes things in some way clearer. All of this is described in fair detail in the History of Haskell paper, by the way (see http://portal.acm.org/toc.cfm?id=1238844). It's worth noting that, in comparing continuation and monadic program fragments, we comment in that paper: Although these two code fragments have a somewhat imperative feel because of the way they are laid out, it was really the advent of do-notation—not monads themselves—that made Haskell programs look more like conventional imperative programs (for better or worse). This syntax seriously blurred the line between purely functional programs and imperative programs, yet was heartily adopted by the Haskell Committee. In retrospect it is worth asking whether this same (or similar) syntactic device could have been used to make stream or continuation-based I/O look more natural. Best wishes, -Paul Claus Reinke wrote: The standard, naïve approach to monadic parsing is very nice, but inefficient. So *please read* some material based on HuttonMeijer approach, but don't stay there, read something more modern, since we thereby seem to have left the phase of simple answers to simple questions;-) i'd like to raise a pet issue of mine. my own first combinator parsers (inspired by Wadler's How to replace failure by a list of successes, but adapted to a call-by-value language) were based on continuations. .. ok, now everybody has had time to chime in with monadic parsers are based on continuations or continuations are just one specific monad. so let me return to the particular issue i'm interested in: contrary to monadic parsers, those continuation-based parsers had *two* continuations, one for success, one for failure. and that seemed to be a very natural match for the problem. for all that i like monadic programming in general, i often feel that it is biased towards handling only the success path well, by offering built-in support for a single continuation only. for instance, one can use (Either String) as a parser monad with error messages, but it isn't straightforward to express error handling into that format, preserving both success and failure- related info (such as reporting the error corresponding to the longest partially successful parse). also, negation does not seem to be an easy fit (succeed if a specific parser would not be successful at the current point; this seems to require monad-specific information, so perhaps there's a MonadNegate class missing?). has anyone else had similar experiences with expressive limitations of monadic programming? things that one might be able to work around, but that don't feel as natural or simple as they should be? things that one hasn't been able to express at all (such as Swierstra Duponcheel's static analysis of combinator parsers which inspired Hughes's proposal to use arrows)? claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] HGL on Windows
Unfortunately your memory serves you well -- see: http://hackage.haskell.org/trac/ghc/ticket/742 -Paul peterv wrote: I vaguely remember to have read that HGL is (currently) not supported on Windows, but I cant find this information any more. Is this correct? It seems not to be included in GHC 6.6 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New New newbie question/help
I think that an easier solution is to just change the type of equilateralTri to: equilateralTri :: Window - Float - Float - Float - IO() But I am on the road and wasn't able to actually run the code. -Paul Dougal Stanton wrote: On 27/06/07, Balu Raman [EMAIL PROTECTED] wrote: equilateralTri :: Window - Int - Int - Int - IO() equilateralTri w x y side = drawInWindow w (withColor Red (polygon [(x,y),(a,b),(x,y)])) where b = y + side * sin(pi/3) a = x + side * cos(pi/3) Your problem lies in this section here. Let's look at the error message: triangle.hs:17:36: No instance for (Floating Int) arising from use of 'pi' at triangle.hs:17:36-37 Probable fix: add an instance declaration for (Floating Int) In the first argument of '(/)', namely 'pi' In the first argument of 'cos', namely '(pi / 3)' In the second argument of '(*)', namely 'cos (pi/3)' Failed, modules loaded: none The problem comes from the calculations of 'a' and 'b'. The function sin doesn't return an Int value. It returns types within the type class Floating (annotated as below, for some unspecified 'a'). sin (pi/3) :: Floating a = a side :: Int Since the type checker has one unknown type, a, and one known, Int, it tries to put the two together. Then it finds that Int is not an instance of the Floating class, so a /= Int. So it asks you to make one: Probable fix: add an instance declaration for (Floating Int) In this case, the advice is bad. There is no reasonable way of making a machine integer a member of the floating class. What you need to do instead is ensure that you're using a type that is a member of the Floating class - that is, convert from an Int before you start the calculation. The function fromIntegral should come in handy: let n = 3 :: Int (fromIntegral n) * sin (pi/3) 2.598076211353316 Good luck! D. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] New New newbie question/help
Hi Balu. It looks like you've gotten some excellent advice from others, but permit me to add a further comment regarding the broader context, now that I've had a chance to look a little closer. It looks like you're trying to solve the "fractal snowflake" exercise. One of the challenges in programming with numbers is deciding what representation to use. Ints are great because they are efficient, but if you need to use trigonometric functions such as sine, etc. then you need Floats or Doubles. The problem here is that you need both -- you need Ints because polygon is defined in terms of pixels, which are represented as Ints, and you need Floats because you need to compute the coordinates of an equilateral triangle, which (interestingly) can't be represented using integer coordinates. But also, in the case of the snowflake fractal, you will need to scale the size as you recurse. The reason that the latter is important is that it implies that the arguments to equilateralTri should perhaps be floats -- otherwise you will once again run into numeric conversion problems as you try to scale the arguments (unless you always start with a pixel size that is a multiple of six). So -- I would still suggest using Window - Float - Float - Float - IO() as the type for equilateralTri. It's only when you make the call to polygon that you need Ints. And there you can just use "round" to convert the Floats to Ints. As an aside, looking at your code a bit closer, I see this: (polygon [(x,y),(a,b),(x,y)])) where b = y + side * sin(pi/3) a = x + side * cos(pi/3) Something is not right here -- you repeat (x,y) as a vertex. Probably the third vertex should be (x+side,y). Also, note that sin (pi/3) and cos (pi/3) are constants (namely 0.866... and 0.5, resp.). I hope this helps, -Paul Balu Raman wrote: I am for ever obliged to this haskell community. Who would have thought that Prof.Hudak would reply instantly, from on-the-road. I am reading his SOE. Thanks so much. I went with peterv's response after trying so many things. I tried to change to : equilateralTri Window - Float - Float - Float - IO() which bombed because polygon wants list of integer-pairs. I read the definitions of fromIntegral and round and they are defined as : fromIntegral :: (Num b, Integral a) = a - b round :: (RealFrac a, Integral b) = a-b Is it proper/ok to defines them as : fromIntegral :: (a::Integral) - (b::Num) and round :: (a::RealFrac) - (b::Integral) ? Is RealFrac is-a Num ? Does the order matters in (Num b,Integral a) = a - b or (Integral a,Num b) = a - b With your encouragements, I'll keep pluuging. Thanks. - br On 6/27/07, peterv [EMAIL PROTECTED] wrote: I'm also a haskell newbie, but I'll try to help; the experts here will correct me if I'm wrong. The compiler cannot in all cases infer the type of a number. pi can be a Float, a Double, or even a complex number. Furthermore unlike in C/C++ you cannot just mix integer and floating operations. For example, the following works for me: f :: Int - Int f side = round ( (fromIntegral side) * sin ( (pi::Float) / 3 ) ) or easier f side = round ( (fromIntegral side) * sin (pi / 3.0) ) I'm sure the experts here will have a better solution. Peter -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] On Behalf Of Balu Raman Sent: Wednesday, June 27, 2007 1:25 PM To: Haskell-Cafe@haskell.org Subject: [Haskell-cafe] New New newbie question/help Hi, Hope someone can help me, just starting out with SOE.My code : module Main where import Graphics.SOE.Gtk spaceClose :: WIndow - IO() spaceClose w = do k - getKey w if k == ' ' then closeWindow w else spaceClose w equilateralTri :: Window - Int - Int - Int - IO() equilateralTri w x y side = drawInWindow w (withColor Red (polygon [(x,y),(a,b),(x,y)])) where b = y + side * sin(pi/3) a = x + side * cos(pi/3) main = runGraphics( do w - openWindow "Equilateral Triangle" (400,400) equilateralTri w 50 300 200 spaceClose w ) all of the above in file triangle.hs when I do a :l triangle.h in ghci,I get the following error triangle.hs:17:36: No instance for (Floating Int) arising from use of 'pi' at triangle.hs:17:36-37 Probable fix: add an instance declaration for (Floating Int) In the first argument of '(/)', namely 'pi' In the first argument of 'cos', namely '(pi / 3)' In the second argument of '(*)', namely 'cos (pi/3)' Failed, modules loaded: none Can someone help me what's going on to a brand new newbie. All I can figure out is that some type mismatch between float and int . I tried various combinations of lets and wheres and I still get the same complaints. I am just linearly studying SOE Thanks, - br ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Just curios
As reported in the recent HOPL paper, A History of Haskell, Haskell Brooks Curry actually didn't like his first name! I learned this when I visited his wife, Virginia Curry, at the time when we decided to name a language after her husband. By the way, Haskell Curry's mother's name was Anna Baright and his father's name was Samuel Silas Curry. Samuel was the President of the School of _expression_ in Boston and Anna was the Dean of the school. Haskell met a student at the School of _expression_ whose name was Mary Virginia Wheatly, who would later become his bride. (Silas Curry's school was one of the motivations for naming my book -- the other being that Haskell programs are just expressions :-) You can learn more about Haskell Curry at: http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Curry.html -Paul Andrew Coppin wrote: OK, so this doesn't actually have anything to do with programming in Haskell, but... How in the name of God does a human being end up walking around with a name like "Haskell B. Curry"? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What puts False before True?
PR Stanley wrote: I think so, too. In Boolean algebra (which predates computers, much less C), FALSE has traditionally been associated with 0, and TRUE with 1. And since 1 0, TRUE FALSE. The question, however, still remains: why False = 0 and True 1? I appreciate that it's so in boolean algebra but why? Why not True = 0 and False = 1? Because if you take () to be (*), and (||) to be (+), you get a homomorphism between the two resulting algebras (assuming 1+1 = 1). That is, if we define: h(False) = 0 h(True) = 1 then: h(ab) = h(a) * h(b) h(a||b) = h(a) + h(b) -Paul P.S. Another reason to justify False True is that show False show True. :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad pronounced like gonad?
This reminds me of a joke (which depends on recognizing a connection between monads, continuations, control, and goto statements): Q: What do you get when you cross a monad with a continuation? A: A gonad. (I am sure I will hear the groans right through the ethernet! :-) -Paul Tom Harper wrote: Hahahah, it's pronounced the way you've been saying it =) On 5/10/07, Dan Weston [EMAIL PROTECTED] wrote: I've been pronouncing monad like gonad (moh-nad), but it occurs to me that it might be pronounced like monoid (mah-nad). Is there an official way to pronouce this word - maybe with a Scottish accent? :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Josephus problem and style
Here's a solution that I think is a bit more elegant. -Paul josephus n k = let loop xs = let d:r = drop (k-1) xs in d : loop (filter (/= d) r) in take n (loop (cycle [1..n])) Anthony Chaumas-Pellet wrote: Hello, I've written a function to compute the general Josephus problem, giving both the number of the survivor and the order in which the others are killed. However, I am not overly fond of my actual Haskell implementation, so I would like some comments on elegance. My current function is as follow:: josephus k n = josephus' k 1 [1..n] [] where josephus' k i (x:xs) sorted | xs == [] = (x, reverse sorted) | i `mod` k == 0 = josephus' k (i+1) xs ([x] ++ sorted) | otherwise = josephus' k (i+1) (xs ++ [x]) sorted The biggest difficulty I had is representing the circle (a continuous unit, unlike the list). The only solution I've found is to explicitly concatenate lists during each iteration, using an index to check whether the current element should be kept. It seems to me that manupilating lists so often makes the resulting function unclear, and hides the basic principle behind the Josephus sequence. So, I'm looking for a better way to write this function, but enlightenment eludes me. I've taken up Haskell in earnest a couple weeks ago, after a fairly long stay in Lisp land (perhaps it shows). My previous Eureka! moment in Haskell was matrix multiplication, along the lines of: matProd a b = [[sum (zipWith (*) x y) | y - transpose b]| x - a] Thanks! Anthony Chaumas-Pellet ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] NYTimes.com: John W. Backus, 82, Fortran Developer, Dies
This page was sent to you by: [EMAIL PROTECTED] John Backus, inventor of Fortran, Turing Award winner, and also an early pioneer in functional programming, died Saturday at his home in Oregon. Many of us have fond memories of him in the earlier days of our careers, and we all owe a lot to him for giving credibility to functional programming through his Turing Award lecture, Can Programming Be Libarated From the von Neumann style? Here is an article from the New York Times. BUSINESS | March 20, 2007 John W. Backus, 82, Fortran Developer, Dies By STEVE LOHR Mr. Backus assembled and led the I.B.M. team that created Fortran, the first widely used programming language. http://www.nytimes.com/2007/03/20/business/20backus.html?ex=1175054400en=d76ca10764a7769fei=5070emc=eta1 -- ABOUT THIS E-MAIL This e-mail was sent to you by a friend through NYTimes.com's E-mail This Article service. For general information about NYTimes.com, write to [EMAIL PROTECTED] NYTimes.com 500 Seventh Avenue New York, NY 10018 Copyright 2007 The New York Times Company ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell-cafe] NYTimes.com: John W. Backus, 82, Fortran Developer, Dies
This page was sent to you by: [EMAIL PROTECTED] John Backus, inventor of Fortran, Turing Award winner, and also an early pioneer in functional programming, died Saturday at his home in Oregon. Many of us have fond memories of him in the earlier days of our careers, and we all owe a lot to him for giving credibility to functional programming through his Turing Award lecture, Can Programming Be Libarated From the von Neumann style? Here is an article from the New York Times. BUSINESS | March 20, 2007 John W. Backus, 82, Fortran Developer, Dies By STEVE LOHR Mr. Backus assembled and led the I.B.M. team that created Fortran, the first widely used programming language. http://www.nytimes.com/2007/03/20/business/20backus.html?ex=1175054400en=d76ca10764a7769fei=5070emc=eta1 -- ABOUT THIS E-MAIL This e-mail was sent to you by a friend through NYTimes.com's E-mail This Article service. For general information about NYTimes.com, write to [EMAIL PROTECTED] NYTimes.com 500 Seventh Avenue New York, NY 10018 Copyright 2007 The New York Times Company ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: fix
Assuming 1 :: Int, then: ones = 1 : ones is equivalent to: ones = fix (\ones - 1:ones) where fix has type ([Int] - [Int]) - [Int]. It's also the case that: inf = 1+inf is equivalent to: inf = fix (\inf - 1+inf) where fix has type (Int - Int) - Int. Unfortunately (perhaps), the fixed point returned is _|_, since it is the LEAST solution to the recursive equation. -Paul Dan Weston wrote: But in fact it seems to me that the type variable a not only can, but must unify with b-c. Is there any use of fix for which this is not true? If this is true, is the type a instead of b-c because it is not possible in general for the type checker to verify this fact, making it some kind of underivable true statement? If it is not true, I would dearly love to see a use of fix with a type for which functional application is not defined. For me, it is this aspect (the type of fix) that has made it so much harder to understand fix than it should have been. Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Origins of (x:xs)?
Pattern matching goes back to Burstall and Darlington's work in the 1970's. As for x:xs, the xs is meant to be the plural of x, and is pronounced exs (I guess...). Similarly, n:ns is one n followed by many more ens. Make sense? (By the way, : is often pronounced followed by.) -Paul Hudak Toby Hutton wrote: Hi, This may have been asked before, sorry if so. I've wondered where the convention of pattern matching a list to (x:xs) came from? I've read a couple of old papers recently which let me believe it may have started back in the '70s with Miranda and its ilk. Does anyone know why (x:xs)? Is xs meant to be a synonym for 'excess'? Yours curiously, Toby. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell] haskell.org memory upgrade
Dear Haskellers -- Haskell.org will go down today at 1500 EST for about 10 minutes for a memory upgrade. Sorry for the inconvenience, -Paul Hudak ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
[Haskell-cafe] haskell.org memory upgrade
Dear Haskellers -- Haskell.org will go down today at 1500 EST for about 10 minutes for a memory upgrade. Sorry for the inconvenience, -Paul Hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Writing Haskell For Dummies Or At Least For People Who Feel Like Dummies When They See The Word 'Monad'
Hi Sebastian. As a writer of one of those "academic" Haskell textbooks, I've been following this thread with some interest. In fact, I agree with pretty much everything that's been said. But I must point out that, even though Chapter 18 in SOE is titled "Higher Order Types", and that's where I introduce the Monad class, I actually introduce IO in Chapter 3 -- page 36 in a 363 page textbook to be more precise. In fact, I do exactly as you suggest -- introduce IO early in a way that most imperative programmers are familiar with, and then expose the beauty and generality of monads much later -- i.e. in Chapter 18. I don't know if you were referring to SOE when you said Chapter 18, but I thought that I should point out the coincidence, at least, if that's what it is! :-) While I'm at it, I have a couple of other general comments: I purposely wrote SOE in a style that I was hoping would be different from the standard language textbook, namely I tried to introduce language features as they were needed in solving problems, rather than just rattling off a list of language features. Granted, my toy "multimedia" examples are not well motivated by the real world, so it doesn't necessarily apply to what's now being proposed. But I wanted to point out that this was nevertheless really hard to do, and the sequencing of the material was a real challenge -- I'm not even sure that I would follow this formula again if I rewrote the book. Maybe some of you can do better, but it's really tough to show someone how an advanced Haskell programmer would solve advanced problems that arise in the real world. As a simple example, I love this recent quote by Garrett Morris: "I'm personally fond of framing most non-trivial Haskell problems as defining domain specific languages; as a result, everything over about 200 lines that I've written in the past 3 years has used the mtl [Monad Transformer Library] in some form or fashion. It's great." So how do we teach Garrett's way of programming (which I like very much) to the masses? One would guess that we'd need to explain not only monads, but also monad transformers, first. One of the things I found myself doing in SOE is saying things like, "remember that thing we did way back in Chapter 3? Using monads, we can now express it more elegantly and modularly and succinctly like this: ..." But there is danger in doing this. If we teach newbies how to do things the "beginner's" way first (recursion instead of higher-order functions, lists instead of user-defined data types, specialized functions instead of type classes, and so on), then we risk the user saying "Oh this is just typed Lisp, so I'm outa here." So, I am *all for* someone writing a textbook that tackles real, meaty problems from the real world. But it's not at all clear to me how to do it. There seems to be a need for a fine balance between elementary stuff and advanced stuff, mixed with both elementary and advanced applications. I hope that some of you are up for the challenge! -Paul Hudak Sebastian Sylvan wrote: On 12/11/06, Kirsten Chevalier [EMAIL PROTECTED] wrote: It's not as if this is the first time that this has been suggested, but some people have suggested that a practical book about Haskell would be a good idea. I agree. Some people have also suggested that the right moment for this hasn't arrived yet, and I see that as a challenge. IMO the number one problem with existing books is that they are far to structured. I.e. "first we'll spend one chapter on functions, then one on types, then one on laziness, then one on data types" etc. But that means you can't really show off anything useful until the last chapter! I think the problem is that most authors are academics, and used to a very systematic way of explaining things - the problem is that when Average Joe has read two chapters, he will want to try out some ideas of his own, and if you haven't given him the basic tools to do Real Stuff by then, he'll think the language isn't meant for real world usage and that impression will stick. Yes, monads are cool, but for Average Joe who doesn't give a hoot about category theory we don't need too specific. And we REALLY don't need to hold off on IO until chapter 18 because we feel that we couldn't do the subject "justice" until then (again, there is no need to explain it in detail right away). For example, most books on C++ include plenty of operations on various ostreams way before they actually explain how they work. As far as the newbie is concerned, "cout" is a keyword that lets you print stuff, and later on he'll realise that it's just a library. So my point is that the book should give examples of REAL programs, even if they're just small examples. Use IO when necessary and start off by keeping i
Re: [Haskell-cafe] Functional GUI combinators for arbitrary graphs ofcomponents?
If you consider just Dags, I believe that this question is equivalent to asking what set of combinators will allow you to create an arbitrary composition of functions that allow sharing inputs and returning multiple results. And I think that one answer to that is the set of combinators that make up the Arrow class. If you want to include recursion (i.e. cycles), then you'd have to throw in ArrowLoop (although that might only provide a nested form of cycles). It's in this sense that Fudgets is analogous to Fruit. -Paul Brian Hulley wrote: Brian Hulley wrote: Anyway to get to my point, though all this sounds great, I'm wondering how to construct an arbitrary graph of Fudgets just from a fixed set of combinators, such that each Fudget (node in the graph) is only mentioned once in the expression. To simplify the question, assume we have the following data structure to describe the desired graph: data LinkDesc a = Series a a | Broadcast a [a] | Merge [a] a type GraphDesc a = [LinkDesc a] The above is more complicated than necessary. The problem can be captured by: type GraphDesc a = [(a,a)] Brian. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Self Study with SOE
Hi Deech. I'm afraid that there is no solutions manual for SOE. I have many of the solutions scattered about in various places, and have been meaning to cull them together, but haven't had the time. However, the following website should be helpful to you: http://plucky.cs.yale.edu/CS429F04 This is from a course I taught two years ago, and it contains a number of solutions to SOE problems, as well as powerpoint slides for most of the chapters, and information on more advanced topics such as Yampa. I hope this helps, -Paul Aditya Siram wrote: Hi all, I have been steadily working through Haskell SOE. However, as the exercises become more involved, I would like to know, not only that the answer I come up with works, but that I am doing it the right way (the elegant way?). For instance, Chapter 8 Exercise 8.3 requires me to modify the area and perimeter functions to accept negative arguments. My solution would be to change the functions to take the absolute value of the arguments as they come in. This would work but it doesn't seem all that elegant. Additionally, SOE exercises do not come with test data so I can test correctness. Is it part of my responsibililty as a student to come up with test data (boundary conditions etc) as I try to answer the questions? Is there some kind of solutions manual available? I promise I am not doing this as homework for a course. Thanks... Deech ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: optimization help
[EMAIL PROTECTED] wrote: Paul Hudak wrote: In fact avoiding space leaks was one of the motivations for our moving to an arrow framework for FRP (now called Yampa). Arrows amount to a point-free coding style, although with "arrow syntax" the cumbersomeness of programming in that style is largely alleviated. I think that's an entirely different thing. You changed representation of signal transformers from newtype SF a b = SF ([a] - [b]) to data SF a b = SF (a - (b, SF a b)) I think that you misunderstood what I said. When we went from FRP to Yampa, we changed from using signals directly, i.e. Signal a, to using signal functions, i.e.: SF a b = Signal a - Signal b When we did this, we made SF abstract, and we adopted the arrow framework to allow composing, etc. signal functions. This meant that you could not get your hands on Signals directly, which helped to prevent space leaks. What you describe above is a change that we made in the implementation of signal functions (specifically, from streams to continuations), which indeed is an entirely different thing. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: optimization help
In fact avoiding space leaks was one of the motivations for our moving to an arrow framework for FRP (now called Yampa). Arrows amount to a point-free coding style, although with arrow syntax the cumbersomeness of programming in that style is largely alleviated. -Paul jeff p wrote: Hello, The (almost) point-free versions run faster than my fast imperative version and take up significantly less heap space-- even the version which reads everything and then writes takes up about 1/3 the heap space as my version. I get the impression that point-free style is a preventive measure against space leaks. thanks again, Jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] GADT: call for proper terminology
Lennart Augustsson wrote: Well, I think the GADT type definition syntax is the syntax data type definitions should have had from the start. Too bad we didn't realize it 15 years ago. -- Lennart I agree! In my experience teaching Haskell, the current syntax is a bit confusing for newbies, and for years I've been telling students, It really means this: ... and then I write out a syntax more like GADT's. I also think that if we had adopted this syntax from the beginning, GADT's would have been discovered far sooner than now. -Paul ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] ANN: Efficient, dynamically compiled, lazy functional semantics on JVM, having tight integration with the Java language
Title: Re: [Haskell] ANN: Efficient, dynamically compiled, lazy functional semantics on JVM, having tight integration with the Java language I suspect many of us are dying to ask: Why not just use Haskell? -Paul Luke Evans wrote: It could be for a subset of Haskell (probably a large one). Haskell has some features that CAL does not (many just syntactic sugar, some not) were actually working on a short paper to summarise the differences, primarily for people on this list. Even without a one-to-one correspondence, this might work in many situations where special lower level CAL could be generated in lieu of higher-level Haskell features. Still, you would probably be able to go a very long way with not much more than straightforward syntax transformations. Of course, use of Haskell libraries would either have to be mapped to CAL ones, or the Haskell library functions converted themselves (with this treatment applied recursively to dependees). Lwe On 9/26/06 10:52 PM, "Tomasz Zielonka" [EMAIL PROTECTED] wrote: On Tue, Sep 26, 2006 at 09:22:21PM -0700, Luke Evans wrote: Here are a few 'highlights' from our feature list: - A lazily evaluated, strictly-typed language called CAL, with many similarities to Haskell Do you think that CAL would be a good target for a Haskell compiler? In other words, would it be a good idea to use CAL as an intermediate language for a Haskell - Java byte-code compiler? Best regards Tomasz ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Haskell.org down
Sorry to bother everyone with this, but some input I've gotten from the community has been helpful. Haskell.org is up again, and here is the latest action on part of our IT staff: If anything further develops I'll let you know. Thanks, -Paul I had to reboot haskell this AM it was really hung. My first assumption is abuse by web crawlers. I have denied access to all web crawlers at the moment while I continue looking further into this and the load is staying low. I'll keep you posted. Paul Hudak wrote: We are looking into it. Sorry for the inconvenience. -Paul Jason Dagit wrote: On 9/23/06, Donald Bruce Stewart [EMAIL PROTECTED] wrote: Hmm. Looks like its gone down again? And again... Seems fishy... Very. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell.org down
We are looking into it. Sorry for the inconvenience. -Paul Jason Dagit wrote: On 9/23/06, Donald Bruce Stewart [EMAIL PROTECTED] wrote: Hmm. Looks like its gone down again? And again... Seems fishy... Very. Professor Paul Hudak Department of Computer ScienceOffice: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell.org down
Thanks Don. I alerted our IT staff this morning, and they seem to have things working again, although here is their final response: The web server had over 150 client connections which exceeded its limit. I restarted the web server and all is well. I'll keep and eye on it and see if someone is trying a denial of server attack, or it could be you need a newer faster machine. :-) So either Haskell is getting really popular (on a Friday night?) or there's something fishy going on. -Paul Donald Bruce Stewart wrote: Just in case it has gone unnoticed, haskell.org seems to have been down for a few hours now. Do we have an admin looking into this? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskore
As Henning points out, the darcs version of Haskore is now the standard, which Henning has been kind enough to set up. However, it has also been extended and re-organized, and at least currently does not have the simplistic feel of the original Haskore. On the other hand, the version that is described in Chapter 20 of SOE (which is called "MDL") is very simple and elegant and would be a great way to "learn Haskell". Even though it's in Chapter 20, it depends only on material presented much earlier in the book. I hope this helps, -Paul Henning Thielemann wrote: On Fri, 22 Sep 2006, David Curran wrote: Hi I have been trying to learn haskell (tip over the vending machine) for a while and eventually decided the Haskore music library might be a good way to start understating the language. I am using windows and hugs98. The IOExtensions.hs file will not work under windows. Any ideas on how to make it work or is this library *nix only? I think that this problem was resolved in the revised Haskore version, see http://darcs.haskell.org/haskore/ and its binary file wrapper http://darcs.haskell.org/haskore/src/Haskore/General/IO.hs However, I feel that this Haskore version is no longer simple enough for learning. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskore microtonal support
An easier and better way to support microtonal music in Haskore is to use the csound back-end instead of MIDI. I'd be happy to help someone develop such a thing if interested. -Paul Magnus Jonsson wrote: On Thu, 14 Sep 2006, Henning Thielemann wrote: On Thu, 14 Sep 2006, Magnus Jonsson wrote: Now even more interestingly, my program also deals with music! :) I'm generating microtonal midi files. I use it for very much the same purpose as you do (although my program is not yet finished). Is it something we could and should add to Haskore? If Haskore could support microtones that would make this world a slightly better world for me. Here are the basic things you need to support microtonal music: - Pitch representations would have to be able to express any pitch. - One appealing approach is to represent a pitch directly as it's frequency. - Probably the most useful representation though is a base pitch, say one of C,D,E,F,G,A,B, followed by a list of accidentals that modify the pitch. The user should be able to define his own base pitches and accidentals, in terms of cents or frequency ratios or something similar. - Generating microtonal midi files requires that you add pitch-bend messages before all notes. That restricts each midi channel to only being able to play one note at a time. This is a big deficiency in the midi protocol imo. / Magnus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fran - Functional Reactive Animation
Actually Pan (and Pan#) are NOT the same as Fran -- quite a bit different, in fact. You may have to email Conal Elliott for a working version of Fran, OR you could look at my simplified version (which I call FAL, for Functional Animation Language) described in Chapter 15 of my textbook, The Haskell School of Expression. You can get a working version of FAL by downloading the source code from www.haskell.org/soe, although I should warn that the graphics lib on which it depends no longer works on all platforms and with all compilers. Another option is to look at Yampa (www.haskell.org/yampa) which when combined with a suitable graphics back-end is essentially an arrowized version of Fran. I would recommend this route if you want to avoid space-leak problems that are inherent with pure Fran. Let me know if you have any problems. -Paul Jared Updike wrote: I think this works: http://haskell.org/edsl/pansharp.html Jared. On 8/23/06, HIGGINS Neil (ENERGEX) [EMAIL PROTECTED] wrote: Fran is a Haskell library (or embedded language) for interactive animations with 2D and 3D graphics and sound. See http://www.conal.net/fran/ and http://research.microsoft.com/research/downloads/download.aspx?FUID=c9eff407-ce59-4a2a-90cb-de099a9bacbd I would like to use Fran as a rapid prototyping environment for animations, but it appears to be broken under WinHugs. I'm looking for someone with much better Haskell prowess than myself who might be able resurrect Fran under WinHugs. Unfortunately I can only offer my gratitude in return. It's a long shot, I know. Kind regards, Neil Higgins Snr Strategic Planning Engineer ENERGEX Em: [EMAIL PROTECTED] Ph: 3407 4800 Fx: 3407 4832 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why shouldn't variable names be capitalized?
Ok, you asked for it, so here's my worst :-) 1) Here's what the History of Haskell has to say about this: Namespaces were a point of considerable discussion in the Haskell Committee. We wanted the user to have as much freedom as possible, while avoiding any form of ambiguity. So we carefully defined a set of lexemes for each namespace that were orthogonal when they needed to be, and overlapped when context was sufficient to distinguish their meaning. As an example of overlap, capitalised names such as Foo can, in the same lexical scope, refer to a type constructor, a data constructor, and a module, since whenever the name Foo appears, it is clear from context to which entity it is referring. As an example of orthogonality, we designed normal variables, infix operators, normal data constructors, and infix data constructors to be mutually exclusive. We adopted from Miranda the convention that data constructors are capitalised while variables are not; and added a similar convention for infix constructors, which in Haskell must start with a colon. ... The key point here is that we wanted data constructors to be orthogonal to formal parameters. For example, in: foo x y = ... We know that x and y are formal parameters, whereas if they were capitalized we'd know that they were constructors. Some of us had had experience with ML where this distinction is not made, and we didn't like that. There are surely other ways to achieve this, but captilization was one of the least painful, as we saw it. 2) Note that this is not a compiler issue -- the compiler won't have much problem either way -- but it is a readability issue. 3) I suspect that you are mostly kidding, but Haskell doesn't require you to know any category theory to write imperative code! I hope this helps, -Paul Martin Percossi wrote: Hi, I'm wondering what the rationale was for not allowing capitalized variable names (and uncapitalized type names and constructors). I can only think of two arguments, and IMHO both of them are bad: 1. Enforces a naming convention. Fine - but my view is that this doesn't belong in the language definition (it belongs in the user's coding standards). I get annoyed, for example, that when I write code that manipulates matrices and vectors, I can't refer to the matrices with capital letters as is common in the literature. And to anyone who says that it's good to enforce naming consistency, I have this to say: Any language that requires me to learn about category theory in order to write imperative code should treat me like an adult when it comes to the naming of variables as well. ;-) 2. It makes it easier to write the compiler. I don't think I need to explain why this is bad... I imagine that someone is just itching to sort me out. Do your worst! ;-) Thx Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] if-then-else as rebindable syntax (was Re: Why does Haskell have the if-then-else syntax?)
I'm all for making Haskell easy for beginners, but as Simon points out, this change shouldn't really affect them. Since I'm also a fan of using Haskell as the host for embedded DSL's, I think this would be a good addition, since it provides more flexibility with the syntax. -Paul Simon Peyton-Jones wrote: Just to be clear, to get rebindable syntax in GHC today, you have to ask for it explicitly, via -fno-implicit-prelude If you use that flag, you'd better know what it means. It already means that do-notation uses whatever () and (=) are in scope, not Control.Monad.() etc. This if-thing is just another example. No beginner will encounter this complication; they'd have to ask for it. Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why does Haskell have the if-then-else syntax?
Mike Gunter wrote: I had hoped the History of Haskell paper would answer a question I've pondered for some time: why does Haskell have the if-then-else syntax? The paper doesn't address this. What's the story? thanks, -m Thanks for asking about this -- it probably should be in the paper. Dan Doel's answer is closest to the truth: I imagine the answer is that having the syntax for it looks nicer/is clearer. if a b c could be more cryptic than if a then b else c for some values of a, b and c. except that there was also the simple desire to conform to convention here (I don't recall fewer parentheses being a reason for the choice). In considering the alternative, I remember the function cond being proposed instead of if, in deference to Scheme and to avoid confusion with people's expectations regarding if. A related issue is why Haskell does not have a single arm conditional -- i.e. an if-then form, which would evaluate to bottom (i.e. error) if the predicate were false. This was actually discussed, but rejected as a bad idea for a purely functional language. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional progr., infinity, and the Universe
Stepan Golosunov wrote: 1:_|_ is certainly finite. And what is length _|_ ? _|_, of course!! :-) The point being, length is well-defined only for total lists; it is undefined for partial lists. But this doesn't mean that a partial list isn't finite. What is finite list then? Is ones = 1:ones also finite? Hmmm... never tried to write all this down in one place before, but I think this covers all cases: A partial list is one that ends in _|_. A total list is one that ends in []. A finite list is either partial or total. Any other list is infinite. So ones is infinite. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional progr., infinity, and the Universe
Jerzy Karczmarczuk wrote: OK, I think that this subject matured enough to rest in peace... I would have to agree with that, although... Couldn't an infinite list just be regarded as the maximum element of the (infinite) set of all finite lists? Perhaps his intuition is right, but there are fundamental differences - A. Between the chain of partial lists and the set of finite lists Well, each partial list is finite. Of course it isn't the set of ALL finite lists, but it is the set of all those finite lists that approximate the given infinite list. B. Between a limit and the maximum element of a set. But the limit of a chain IS the maximal element of the set of all elements comprising the chain, since the LUB, in the case of a chain, is unique, and thus we don't have to worry about choosing the least element (i.e. it reduces to the upper bound, or maximal element). So I'd say that Brian has at least come close to discovering God :-) -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional progr., infinity, and the Universe
Bill Wood wrote:
On Fri, 2006-06-23 at 09:38 -0400, Paul Hudak wrote:
But the limit of a chain IS the maximal element of the set of all
elements comprising the chain, since the LUB, in the case of a chain, is
unique, and thus we don't have to worry about choosing the least
element (i.e. it reduces to the upper bound, or maximal element).
There must be something additional going on, since in general the fact
that an ordered subset of a set has a LUB in the set does not imply that
the LUB is in the subset. For example, the subset {1 - 1/n : n in N+}
of Q has LUB = 1, but 1 is not an element of the subset. It would seem
that while the infinite list is the LUB of the chain of finite lists, it
is not itself a member of the chain of finite lists. So, what am I
missing?
I don't think you missed anything, just provided more detail than I
thought was needed. As the LUB is indeed an infinite object, it is not
in the set of finite, partial lists. But that's pretty common in domain
theory, and is analogous to the example that you gave.
-Paul
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional progr., infinity, and the Universe
[EMAIL PROTECTED] wrote: Well, each partial list is finite. I think quite a few people would agree that a finite list is one ending in []. So 1:_|_ is a partial list, but not a finite one. 1:[] is a finite list. 1:_|_ is certainly finite. In what sense is it not? That doesn't quite make sense, IMHO. The chain _|_, 1:_|_, 1:1:_|_, 1:1:1:_|_, ... has the limit (or upper bound) ones, but ones does not appear in the chain. An upper bound of a set may not appear in the set. But the maximal element of a set by definition (element of) necessarily is in the set. So you cannot use the two notions interchangably. BTW, if the limit of a chain would always appear in the chain (by virtue of being the maximal element of the set of all elements comprising the chain), then every chain would be stationary eventually. That would quite simplify denotational semantics, wouldn't it? Sorry, see my reply to Bill Wood. I should have said that the LUB is indeed not in the set. If it WERE in the set, then you simply wouldn't have an infinite object. (In the flat domain of integers, for example, every chain consists of exactly two elements: _|_ and n, for each n.) But this characteristic is common in domain theory, and is what distinguishes what are called interesting elements from other elements (if I recall the terminology correctly). And come to the conclusion, in a later mail, that both: A. the list [0,1,2,3,4,5,..] is longer than [1,2,3,4,5,..] and B. ie [0,1,2,3,4,..] is the same length as [1,2,3,4,5,..] I think not. Obviously not. I know that this conclusion was qualified by assuming that they all grow at the same rate, which of course has no counterpart in the denotational semantics setting discussed above. So it's not a wrong statement, just one that cannot really be formulated. My email didn't comment on this issue. I agree that growth rate is not relevant when we're talking about values. The answer here has to do with the cardinality of infinite sets. Well, anyway, didn't want to be nitpicking. But I think it's important that if we want to think about Haskell's semantics denotationally (which in itself is somewhat problematic), we should at least be careful not to blur concepts. And asserting that the limit of a chain is always an element of that chain is a dangerous oversimplification that does not work out. I agree; sorry about that. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Functional progr., infinity, and the Universe
Stepan Golosunov wrote: On Fri, Jun 23, 2006 at 10:57:48AM -0400, Paul Hudak wrote: [EMAIL PROTECTED] wrote: I think quite a few people would agree that a finite list is one ending in []. So 1:_|_ is a partial list, but not a finite one. 1:[] is a finite list. 1:_|_ is certainly finite. In what sense is it not? And what is length _|_ ? _|_, of course!! :-) The point being, length is well-defined only for total lists; it is undefined for partial lists. But this doesn't mean that a partial list isn't finite. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Functional progr., infinity, and the Universe
Actually Brian's intuition is right on target. One way to define an infinite list is as the limit of an infinite chain of partial lists (which, in domain theory, is essentially how all elements are defined). A chain is a sequence a1 = a2 = ... = an, where = is the domain ordering. A partial list is any list ending in _|_ (i.e. bottom). So, for example, the infinite list of ones can be defined as the limit of the following chain: _|_ = 1 : _|_ = 1 : 1 : _|_ = 1 : 1 : 1 : _|_ ... To verify that this is a chain, remember that (:) is right associative, and _|_ = x for all x. Or, another way to look at this, is that the infinite list is the LUB (least upper bound) of the infinite set of all of these partial (but finite) lists. That explanation corresponds most closely with Brian's intuition. If anyone thinks that this explanation is baroque, I should also point out that in a pragmatic sense this idea forms the basis for doing inductive proofs on programs generating infinite lists (as described in my book, as well as in many other sources). -Paul [EMAIL PROTECTED] wrote: Brian Hulley wrote: Couldn't an infinite list just be regarded as the maximum element of the (infinite) set of all finite lists? Brian, I will say something you might find acrimonious and impolite, but it is serious, you might find this in some philosophical works. If you are right, then YOU JUST PROVED THE EXISTENCE OF GOD. = More seriously... Perhaps you (and possibly Piotr Kalinowski) would look up some materials on intuitionism in mathematics, on the constructive theory of sets, etc. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
-interpreter or whatever we may call it, and with the help of that external entity, and under external control, it can be said to have access to and to interact with resources outside the Haskell program text, inside the runtime context (about which context-free reasoning can't tell us anything). I think that I'm saying something a little stronger, namely that if you capture in a black box the entire universe EXCEPT for the one Haskell program that you're trying to reason about, then the interactions between that black box and the Haskell program can be explained purely functionally and deterministically. That may be an over-simplified view of things -- but it's at least one line to draw when deciding how much about a language's semantics should be explained to the user. I don't see how the whole of black box and Haskell program could be captured purely functionally and deterministically. even if Stoye limited the necessary extensions to the purely functional world view to just one non-deterministic merge, only in his sorting office, he needed that extension of the purely functional world, and once you have a black box with such a merge in it, you cannot guarantee that the non-determinism won't be visible at the black box interface (in fact, that would be the whole point of introducing it in the first place), so even if you don't know anything else about that black box, you cannot assume that it will be a pure function. which means, as far as I can see, that even if the Haskell program is purely functional, the combined system of Haskell program and black box is not. you and I may know what you are doing when taking that over-simplified view of things, but I vaguely remember my struggles with the intricacies of the various functional i/o systems, and from those memories I claim that you would not help your readers if you chose not to explain or even to hide those intricacies. you can always tell the beginner that they can, for many cases, ignore those details - they will look into it briefly, then go away happy that they don't need to understand it immediately. but you do need to help the advanced learners by giving them the option to look into those details once their intuition develops far enough to want better answers. [that is just my view of things, naturally, but I remember going through the library shelves to find books that would suit me, and if I saw any skimming over interesting details, I dropped those books faster than any group of populistic authors could publish them; of course, I had to go to the original papers in the end, but I did prefer those books that, instead of hiding advanced material, guided the reader initially around, and eventually into them:-] :-) Seriously, I think that it would be a useful exercise to write a meta-interpreter of Haskell I/O, in Haskell. That's basically what the appendix of the Haskell Report was many years ago, but it used a stream model of I/O. And I think that this is consistent with your final point below. I wrote my first substantial Haskell program at the time of about Haskell 1.2, and I agree: that appendix was useful for understanding Haskell's i/o story at the time (request/response streams, if I recall correctly; before monads;-). cheers, claus -- Professor Paul Hudak Department of Computer ScienceOffice: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
Points well taken Claus. See further comments below. Claus Reinke wrote: Hi Paul, I think that you're asking for a semantics of the entire OS, i.e. the entire outside world, and for that I agree that something other than equational reasoning is needed to reason about it. I was about to reply no, only of the interface between Haskell and the OS, but perhaps that comes to nearly the same in the end? at least, I'd like to see a simplified Haskell view of the OS added to the picture, which seems to imply that one needs to take at least one step beyond the Haskell only picture, into the domain in which different reasoning tools may be more appropriate. without having to go into all of the OS, such a step should widen the horizon sufficiently to explain the difference between i/o is purely functional (wrong, but popular) and haskell's role in i/o is purely functional, but other roles need to be taken into account to complete the picture (better). Yes, I could agree with that point of view. However, I would argue that that is outside the mandate of a book on Haskell. But maybe that's the point -- i.e. others feel otherwise. I think I do, and obviously (judging from how often this topic reappears) Haskell learners find the current presentations confusing. if a Haskell book shies away from the topic of i/o, or defers it to some late chapter, beginners get the impression that it is more difficult than it should be while advanced learners are frustrated by the lack of coverage. if a Haskell book shies away from explaining at least the basics of how the interactions with the OS go beyond the functional world, even though the Haskell part of it is still functional, beginners go away with a wrong idea (often repeated as a dogma to other newcomers) and advanced learners struggle with their intuition, which tells them that there must be something else going on. the latter was the case Brian was making, I think. Well, in defense of such an approach, there are very few (if any?) textbooks in ANY language that take a formal approach to defining what I/O does. But your point is still well taken, in that I think that the EXPECTATIONS for books on FP to do this are higher because (a) many of them take a formal approach to explaining the internal meaning of programs, and thus readers expect the same for I/O, and (b) the model of I/O that they use (say, monads) is sometimes so different from conventional wisdom that SOMETHING needs to be said, lest the reader be left in the dark! My main point it that if we're reasoning about a single Haskell program (with no impure features), then the entire world, with all its non-determinism internal to it, can be modelled as a black box -- i.e. a function -- that interacts with the single Haskell program in a completely sequential, deterministic manner. And for that, equational reasoning is perfectly adequate. I assume you mean the Haskell program interacts deterministically with non-deterministic inputs, rather than that the OS interacts deterministically with the Haskell program. Yes. The original Haskell report in fact had an appendix with a semantics for I/O written as a Haskell program with a single non-deterministic merge operator. The reason for the non-deterministic merge was to account for SEVERAL Haskell programs interacting with the OS, but for a single program it can go away. I claim that such a semantics is still possible for Haskell, and equational reasoning is sufficient to reason about it. non-deterministic merge is necessary there, and beyond the purely functional domain. and unless you let all your Haskell programs run in the dark, there will always be more than one agent interacting with shared resources: that Haskell program, you, OS daemons, etc. I think that I'm saying something a little stronger, namely that if you capture in a black box the entire universe EXCEPT for the one Haskell program that you're trying to reason about, then the interactions between that black box and the Haskell program can be explained purely functionally and deterministically. That may be an over-simplified view of things -- but it's at least one line to draw when deciding how much about a language's semantics should be explained to the user. the merge idea stems from a time when i/o was described in terms of infinite streams and their transformations, which turned out to be rather difficult to compose in practice. the transition to step-wise interactions and their composition is what makes the process-calculus style more natural these days. not to mention that it prepares readers for other adventures in these modern times - in fact, future readers may be more familiar with process interactions from their other interests, and therefore confused by any attempt to avoid these ideas. Interesting. One might rewrite your first two sentences as: the merge idea stems from a time when i/o was described in terms
Re: [Haskell-cafe] The values of infinite lists
Brian Hulley wrote: Paul Hudak wrote: ... My main point it that if we're reasoning about a single Haskell program (with no impure features), then the entire world, with all its non-determinism internal to it, can be modelled as a black box -- i.e. a function -- that interacts with the single Haskell program in a completely sequential, deterministic manner. And for that, equational reasoning is perfectly adequate. I think the problem is that to understand something you need a lot more than just the capability to reason about it. For example, given laws such as: x * (y + z) == (x * y) + (x * z) x + (y + z) = (x + y) + z I can reason that x * (y + (z + w)) = (x * y + x * z) + x * w But this does *not* mean that therefore I *understand* it. I think understanding is a much deeper process. I have to grapple with the underlying shape, the gesture, the motion of the symbolic transformation and really *feel* the lawfulness of it as a profound inner life experience. So to get back to the question of understanding monads, yes I can reason about them equationally using pure functions but to understand Haskell I need to understand how it is situated in my own human experience ... I agree with all of this. But then you say: and my human experience seems to me to be more than just a deterministic sequential function of Unique - Time - SenseInput. This seems like a value judgement. Someone else might very much like the functional model of things, and might not like some other model. And one might argue that if the functional view is the same as the view that one is using to reason about the rest of the program, then that is a Good Thing. So I'm not saying that there aren't other approaches (denotational semantics, operational semantics, process calculi, etc.) but they might each have the problem of understanding how it is situated in my own human experience. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
Hi Claus -- I think that you're asking for a semantics of the entire OS, i.e. the entire outside world, and for that I agree that something other than equational reasoning is needed to reason about it. However, I would argue that that is outside the mandate of a book on Haskell. But maybe that's the point -- i.e. others feel otherwise. My main point it that if we're reasoning about a single Haskell program (with no impure features), then the entire world, with all its non-determinism internal to it, can be modelled as a black box -- i.e. a function -- that interacts with the single Haskell program in a completely sequential, deterministic manner. And for that, equational reasoning is perfectly adequate. The original Haskell report in fact had an appendix with a semantics for I/O written as a Haskell program with a single non-deterministic merge operator. The reason for the non-deterministic merge was to account for SEVERAL Haskell programs interacting with the OS, but for a single program it can go away. I claim that such a semantics is still possible for Haskell, and equational reasoning is sufficient to reason about it. If you disagree, then please tell me which features in Haskell (a particular I/O command, perhaps?) cannot be modelled as a function. I'm not familiar with your thesis, but I note in the abstract that you extend an existing, purely functional language with facilities for input/output and modular programming. If those extensions cannot be modelled as pure functions, then I would agree that a process calculus (say) would be the right way to go. But as far as i know, Haskell doesn't have such features. -Paul Claus Reinke wrote: Paul Hudak wrote: As an author of such a book, I'm not willing to do this. Or at least, if we omit concurrency and impure operations such as unsafePerformIO, Haskell is a purely functional, sequential, and deterministic language, whose semantics, including that of IO, can be explained via conventional equational reasoning. I'm very surprised to hear you say this, and I certainly cannot agree. a language that contains elements that are not best expressed as functions is not purely functional anymore, even when its design carefully ensures that it is still pure, and mainly functional, and can be reasoned about equationally. the element that falls outside the remit of functions is the interaction with the runtime context (operating system/other processes/users/external world/..). Haskell's approach to this issue is mostly functional and clearly separates functional part from the part that is out of its hands: functionally compute an interaction description, have that interaction performed under outside control, have control returned to functional evaluation with a representation of the interaction result, repeat until done. (an informal recipe like this may be even more suitable for learners than either process calculus rules or claims about being purely functional in principle). if you wanted to model that middle part functionally, you'd have to cover all of the external world as well as scheduling. one nice thing about a process calculus style operational semantics is the modular description; you only need to model how Haskell programs fit into the external world, not the external world itself: assuming that world to be modelled in the same style, we need a miniscule amount of process calculus rules to describe the i/o interactions, falling back to functional-only reasoning for the vast majority of the language. I'm sure that it can also be explained via a suitable process calculus, but that is an overkill -- such calculi are best used for describing non-deterministic / concurrent languages. using a process calculus framework does not imply that each process has to be non-deterministic / concurrent -- it just makes it easier to show how the purely functional, sequential and deterministic evaluation inside a process running Haskell is embedded into and influenced by interactions with the rest of the framework. attempts to ignore that external framework tend to cloud the issues. and as Brian points out, that is more confusing for learners of the language than having to take a tiny bit of process calculus with your mostly functional prescription!-) cheers, claus (*) it is rather dated by now, and certainly not up to the demands of pragmatic Haskell programmers today, but I discussed some of the various functional i/o styles in this way in chapter 3 of http://www.cs.kent.ac.uk/people/staff/cr3/publications/phd.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The values of infinite lists
Robert Dockins wrote: On May 23, 2006, at 9:50 AM, Paul Hudak wrote: If you disagree, then please tell me which features in Haskell (a particular I/O command, perhaps?) cannot be modelled as a function. IO.hGetContents? I suspect the result of using hGetContents on a file you have open for writing in the same program can't be modeled as a pure function; at best you can say it depends on the order of evaluation which isn't defined. Not that it's necessarily a huge blow to your argument (hGetContents is viewed with some suspicion anyway), but it is a Haskell98 feature. Ah yes, operations involving file handles are a good example, but I think the problem here is that we don't actually have a formal semantics for what's supposed to happen. I recall seeing threads about this in the past, where in particular the interactions of lazy evaluation with opening and closing files was being debated. But, I would argue that in principle we COULD (and probably should) specify a deterministic semantics if someone were willing to sit down and spell it out. Things obviously get more complicated in the presence of concurrency. I'm not certain, but I believe some of the memory consistency models being discussed for Haskell' are not expressible using a non-deterministic merge, which basically assumes that all program actions are serializable. http://www.haskell.org//pipermail/haskell-prime/2006-March/001168.html Yes, I agree, although I specifically excluded concurrency from my argument. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] map and list comprehensions
John Peterson wrote: I think the point was that all syntax (like list comprehensions or pattern matching) in Haskell is tied directly to the Prelude. So [ f x ...] is ALWAYS using the Prelude definitions of things while map could be hidden and redefined. Yes, of course. I was implicitly assuming that we were talking about Prelude's map. The inability to change the meaning of constructs expanded from syntax as considered a bug by some, a feature by others. And I don't rember where Paul stood on this ... It has always seemed to me that there should be a way to define something as syntactic expansion into things that cannot be redefined, otherwise the language definition becomes vague. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why is $ right associative instead ofleftassociative?
Bulat Ziganshin wrote: LA In my opinion all the special syntactic sugar for lists should go LA away. I don't think lists are special enough to motivate it. i have proposal (not for Haskell', of course) of using : and [] syntax for general notion of traversable collections: Minor point, perhaps, but I should mention that : is not special syntax -- it is a perfectly valid infix constructor. [] and all its variants, however, are special syntax. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why is $ right associative instead ofleftassociative?
Ben Rudiak-Gould wrote: Paul Hudak wrote: Minor point, perhaps, but I should mention that : is not special syntax -- it is a perfectly valid infix constructor. But Haskell 98 does treat it specially: you can't import Prelude hiding ((:)), or rebind it locally, or refer to it as Prelude.:. In fact I've always wondered why it was done this way. Can anyone enlighten me? I think that originally it was because various primitives were defined (via Translations in the Haskell Report) in terms of lists. But with qualified imports I'm also not sure why this is necessary. Of course it might be confusing if it were rebound locally, but no more confusing than the fact that [f x | x - xs] is not the same as (map f xs). It's not? Hmmm... why not? (At one time list comprehensions were another way to write do notation -- i.e. they were both syntactic sugar for monads -- in which case these would surely be different, but that's not the case in Haskell 98, as far as I know.) -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why is $ right associative insteadofleftassociative?
Chris Kuklewicz wrote:
Brian Hulley wrote:
Ben Rudiak-Gould wrote:
... but no more confusing than the fact that [f x | x - xs] is
not the same as (map f xs).
Can you explain why? On page 258 of Paul Hudak's book The Haskell
School of Expression he states that do x- xs; return (f x) is
equivalent to [f x | x - xs] which is clearly just map f xs
I can't find anything wrong with the example in the book but perhaps
I've missed something?
He may mean that if you *redefine* the operator Prelude.((:)) then the
desugaring and other steps may end up binding the old or the new (:) and no
longer be identical. This is touched on in
http://www.haskell.org/ghc/docs/6.4.1/html/users_guide/syntax-extns.html#rebindable-syntax
In particular, if you redefine Monad, then [ f x | x-xs ] and do {x-xs; return
x} may no longer mean the same thing.
Right, but the original question is whether or not [f x | x - xs] is
the same as map f xs. My book's been out for six years and no one has
mentioned this issue, so if it's a problem I'd like to know why so that
I can add it to my Errata list!
Thanks, -Paul
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Why is $ right associative instead of leftassociative?
Actually, one of the main reasons that we chose (:) is that that's what Miranda used. So, at the time at least, it was not entirely clear what the de facto universal inter-language standard was. In any case, I agree with Stefan regarding Haskell Prime! -Paul Stefan Holdermans wrote: Brian wrote: I think the mystery surrounding :: and : might have been that originally people thought type annotations would hardly ever be needed whereas list cons is often needed, but now that it is regarded as good practice to put a type annotation before every top level value binding, and as the type system becomes more and more complex (eg with GADTs etc), type annotations are now presumably far more common than list cons so it would be good if Haskell Prime would swap these operators back to their de facto universal inter-language standard of list cons and type annotation respectively. I don't think Haskell Prime should be about changing the look and feel of the language. Regards, Stefan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Detecting Cycles in Datastructures
Another belated reply to an old thread... Andrew Pimlott wrote: On Fri, Nov 18, 2005, Paul Hudak wrote: unwind :: Expr - Expr unwind (Add e1 e2) = Add (unwind e1) (unwind e2) unwind (Rec fe)= x where x = unwind (fe x) unwind e = e Since this discussion started around observing sharing in the implementation, I wanted to see whether, by the time we convert your cunning representation back into an infinite data structure, we have the sharing we hoped to observe in the first place. fe2 e = Add (Const 1) e-- recursive e2 = Rec fe2 -- top-level loop e2u = unwind e2-- infinite main = walk e4u where walk (Add e1 e2) = walk e2 blows up, showing that we do not. The problem with unwind seems to be that the computation of the fixed point keeps calling unwind, which keeps reconstructing the fixed point: ... The first solution I gave to the original email from Tom Hawkins doesn't blow up, but you are right that the expanded version (to deal with nested loops) does blow up. Actually, my original definition of unwind was this: unwind :: Expr - Expr unwind (Add e1 e2) = Add (unwind e1) (unwind e2) unwind (Rec fe)= x where x = fe x unwind e = e Indeed this works fine on the above example -- i.e. it doesn't blow up (in Hugs, at least). The only reason I added the extra call to unwind is to handle nested loops, but sadly that causes loss of sharing, as you have pointed out. I then tried unwind (Rec fe) = unwind (fix fe) fix f = x where x = f x even though I didn't think it would work: (fix fe) would create a properly sharing structure, but unwind would unshare it: e2u = unwind (x where x = ((\e - Add (Const 1) e) x)) ( = Add (Const 1) x) = Add (Const 1) (unwind (x where x = Add (Const 1) x)) = Add (Const 1) (Add (Const 1) (unwind (x where x = Add (Const 1) x))) = ... This does blow up in ghci, but not in ghc (6.4.1), even without optimization. I'm not quite sure why, ... Interesting... This is arguably the most elegant solution, since it just replaces the constructor Rec with the function fix. Perhaps surprisingly, it doesn't blow up in Hugs either! If we unwind e2 we get: unwind e2 = unwind (Rec (\e- Add one e)) = unwind (fix (\e- Add one e)) = unwind (x where x = (\e- Add one e) x) = unwind (x where x = Add one x) The question is, what happens next? It seems to me that to prevent blow-up the interpreter would have to do something like this: = x where x = Add one (unwind x) but I don't know how this happens. I would have expected the unwinding that you showed above. Perhaps someone who understands either GHC or Hugs can explain this -- I suspect it has something to do with the interpretation of where. It would be great if there were a simple technique that one could expect every reasonable implementation to use. ... but anyway I want a version that exhibits sharing even in any reasonable implementation. Your message gives the technique (in mapE); we only have to apply it to unwind. But there is a problem--your code has a bug! mapE :: (Int-Int) - Expr - Expr mapE f e = mapE' f e 0 where mapE' f (Const i) n = Const (f i) mapE' f (Add e1 e2) n = Add (mapE' f e1 n) (mapE' f e2 n) mapE' f (Rec fe)n = Rec (absLoop n (mapE' f (fe (Loop n)) (n+1))) mapE' f (Loop i)n = Loop i absLoop :: Int - Expr - Fix Expr absLoop n e = \e' - let abs (Loop n') | n==n' = e' abs (Add e1 e2) = Add (abs e1) (abs e2) abs e = e in abs e e4 = Rec (\e1- Add (Const 1) (Rec (\e2- Add e1 e2))) -- nested loop e7 = mapE succ e4 e8 = Rec (\e1- Add (Const 2) (Rec (\e2- Add e1 e2))) b4 = e7==e8 -- returns True! Notice that absLoop does not look inside Rec. But there could be a Loop (with the right n) there! Thanks for catching this, and your solution seems right to me. See further comments below. Really, we want absLoop to eliminate all the Loops it can find. But it can't, because it only knows the replacement expression for one Loop. It would be simpler for the Loop just to contain the expression. To enable that, I added a constructor Stop that is like Loop, except it takes an Expr instead of an Int. I use this constructor for my sharing unwind as well; Loop is only needed for (==). (It would probably be even better to add an annotation type argument to Expr; this could enable stricter typechecking that would have caught the bug.) Complete code: data Expr = Const Int | Add Expr Expr | Rec (Fix Expr)-- implicit loop | Loop ID -- not exported | Stop Expr ... It's interesting to note that with this datatype, the original example: cyclic = Add (Const 1) cyclic could be written as: cyclic = Add (Const 1) (Stop cyclic) instead of: cyclic e = Add
Re: [Haskell-cafe] Hacking Haskell in Nightclubs?
[EMAIL PROTECTED] wrote: Real-time audio is much simpler these days due to SuperCollider, a truly excellent cross platform audio synthesis server by James McCartney. ... OSC messages can be timestamped, and SuperCollider has a sample accurate scheduling queue, so language timing jitter can easily be worked around. I think that the SuperCollider model is an excellent fit with languages like Haskell. Thanks, this is just what I've been waiting for! I believe the time-stamping of events, and a suitable scheduling queue, are critical for making real-time music. With the work you've done I suspect it would be pretty easy to build a SuperCollider backend for Haskore. -Paul Regards, Rohan On Mon Nov 28 21:35:38 EST 2005 Paul Hudak wrote: Although Haskore (haskell.org/haskore) doesn't currently support real-time music, it's something I've thought about numerous times in the past, and wish I had the time to do it... -Paul Hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hacking Haskell in Nightclubs?
Although Haskore (haskell.org/haskore) doesn't currently support real-time music, it's something I've thought about numerous times in the past, and wish I had the time to do it... -Paul Hudak Echo Nolan wrote: Hello all, I read an article on using perl for live improvised synthesis a while ago (http://www.perl.com/pub/a/2004/08/31/livecode.html). Does anyone have thoughts in doing this is haskell? Would strong typing make jazzy programming too difficult? Regards, Echo Nolan -- Professor Paul Hudak Department of Computer ScienceOffice: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Detecting Cycles in Datastructures
This is a very late response to an old thread... Tom Hawkins wrote: In a pure language, is it possible to detect cycles in recursive data structures? For example, is it possible to determine that cyclic has a loop? ... data Expr = Constant Int | Addition Expr Expr cyclic :: Expr cyclic = Addition (Constant 1) cyclic Or phased differently, is it possible to make Expr an instance of Eq such that cyclic == cyclic is smart enough to avoid a recursive decent? -Tom --- Perhaps it's obvious, but one way to do this is to make the cycle *implicit* via some kind of a fixed-point operator, which is a trick I used recently in a DSL application. For example, you could define: data Expr = Const Int | Add Expr Expr | Loop -- not exported deriving (Eq, Show) The purpose of Loop is to mark the point where a cycle exists. Instead of working with values of type Expr, you work with values of type Expr - Expr, or Fix Expr: type Fix a = a - a For example: fe1,fe2 :: Fix Expr fe1 e = Add (Const 1) (Const 1) -- non-recursive fe2 e = Add (Const 1) e -- recursive You can always get the value of an Expr from a Fix Expr whenever you need it, by computing the fixed point: fix f = x where x = f x e1,e2 :: Expr e1 = fix fe1 -- finite e2 = fix fe2 -- infinite Note that e2 is equivalent to your cyclic. But now we can also test for equality: instance Eq (Fix Expr) where fe1 == fe2 = fe1 Loop == fe2 Loop For example, fe2 == fe2 returns True, whereas e2 == e2 (i.e. your cyclic == cyclic) diverges. Of course, note that, although fe1 == fe2 implies that fix fe1 == fix fe2, the reverse is not true, since there will always be loops of varying degrees of unwinding that are semantically equivalent, but not syntactically, or structurally, equivalent. Thus this definition of equality is only approximate, but still, it's useful. If you want to have multiple loops, or a loop not at the top level, then you need to add some kind of a loop constructor to Expr. I've sketched that idea below, and pointed out a couple of other useful ideas, such as showing a loop, and mapping a function over a loop without unwinding it. I hope this helps, -Paul -- module Cyclic where Loop now needs an ID because there may be more than one of them. data Expr = Const Int | Add Expr Expr | Rec (Fix Expr)-- implicit loop | Loop ID -- not exported type Fix a = a - a type ID= Int To check equality of and show Exprs, we need to supply unique IDs to each recursive loop, which we do via a simple counter. instance Eq Expr where e1 == e2 = let eq (Const x) (Const y) n = x == y eq (Loop i1) (Loop i2) n = i1 == i2 eq (Add e1 e2) (Add e1' e2') n = eq e1 e1' n eq e2 e2' n eq (Rec fe1) (Rec fe2) n = eq (fe1 (Loop n)) (fe2 (Loop n)) (n+1) eq _ _ n = False in eq e1 e2 0 instance Show Expr where show e = let show' (Const x) n = (Const ++ show x ++ ) show' (Add e1 e2) n = (Add ++ show' e1 n ++ ++ show' e2 n ++ ) show' (Loop i)n = (Loop ++ show i ++ ) show' (Rec fe)n = (Rec ++ show n ++ ++ show' (fe (Loop n)) (n+1) ++ ) in show' e 0 Unwinding (i.e. computing fixpoints): Note: unwind should never see a Loop constructor. unwind :: Expr - Expr unwind (Add e1 e2) = Add (unwind e1) (unwind e2) unwind (Rec fe)= x where x = unwind (fe x) unwind e = e The 2nd equation above is analogous to: fix f = x where x = f x And these two equations could also be written as: fix f = f (fix f) unwind (Rec fe) = unwind (fe (Rec fe)) Examples: fe1,fe2 :: Fix Expr fe1 e = Add (Const 1) (Const 1) -- non-recursive fe2 e = Add (Const 1) e -- recursive e1,e2,e3 :: Expr e1 = Rec fe1 -- no real loop e2 = Rec fe2 -- top-level loop e3 = Add e2 (Const 0)-- lower-level loop e4 = Rec (\e1- Add (Const 1) (Rec (\e2- Add e1 e2))) -- nested loop b1,b2 :: Bool b1 = e3==e3 -- returns True b2 = e3==e2 -- returns False e1u,e2u,e3u :: Expr e1u = unwind e1 -- finite e2u = unwind e2 -- infinite e3u = unwind e3 -- infinite e4u = unwind e4 -- infinite Now suppose we define a function, say mapE, that applies a function to the leaves (in this case the Const Int's) of an Expr. For example: mapE succ (Add (Const 1) (Const 2)) = Add (Const 2) (Const 3) Then if we define something like: cyclic1 = Add (Const 1) cyclic1 and do mapE succ
Re: [Haskell-cafe] Detecting Cycles in Datastructures
Henning Thielemann wrote: On Fri, 18 Nov 2005, Paul Hudak wrote: For example: fe1,fe2 :: Fix Expr fe1 e = Add (Const 1) (Const 1) -- non-recursive fe2 e = Add (Const 1) e -- recursive Do you mean fe1 _ = Add (Const 1) Loop ? No, I really meant it as written. I included this example just to point out that an expression didn't have to be infinite to represent it as the fixpoint of a function. Note that the least fixpoint of fe1 is Add (Const 1) (Const 1). Loop shouldn't ever be used by the user -- that's why I added the comment that it was not exported. It's just there to open the function for inspection. In this sense, the trick is analogous to the use of higher-order abstract syntax -- i.e. using the meta-language (Haskell) to represent functions in the object language (expressions). -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Detecting Cycles in Datastructures
Greg Woodhouse wrote: --- Paul Hudak [EMAIL PROTECTED] wrote: Tom Hawkins wrote: In a pure language, is it possible to detect cycles in recursive data structures? For example, is it possible to determine that cyclic has a loop? ... data Expr = Constant Int | Addition Expr Expr cyclic :: Expr cyclic = Addition (Constant 1) cyclic Or phased differently, is it possible to make Expr an instance of Eq such that cyclic == cyclic is smart enough to avoid a recursive decent? I'm a little confused. It's one thing to demonstrate that a (possibly infinite) digraph contains a loop, but quite another to show that it does not. Carrying around a copy of the subgraph consisting of nodes actually visited is workable in a pure language, but there's no guarantee of termination. The question that was originally posted assumed that the graph was represented using direct recursion in Haskell. In which case you cannot detect a cycle, as previous replies pointed out. Of course, if you represented the graph in some more concrete form -- such as an explicit list of nodes and edges -- then you could detect the cycle using a standard graph algorithm, at the expense of losing the elegance of the Haskell recursion. My post was just pointing out that there is a third possibility, one that retains most of the elegance and abstractness of Haskell, yet still allows detecting cycles. Perhaps it's obvious, but one way to do this is to make the cycle *implicit* via some kind of a fixed-point operator, which is a trick I used recently in a DSL application. So, you imagine f to be a function that (non-deterministally) follows an edge in a digraph. The idea being that G is (possibly infinite) digraph and F is a subgraph. The function f would non-deterministically select a vertext of F, follow an edge in G (again chosen non-deterministically), add the (possibly new) edge to F, and return the resulting graph. Then, you are asking if f has a fixpoint in this broader context? I don't understand this... and therefore it's probably not what I imagine! I'm saying simply that a cyclic graph can be represented as the fixed point of a function. For example, you could define: data Expr = Const Int | Add Expr Expr | Loop -- not exported deriving (Eq, Show) The purpose of Loop is to mark the point where a cycle exists. Instead of working with values of type Expr, you work with values of type Expr - Expr, or Fix Expr: type Fix a = a - a For example: fe1,fe2 :: Fix Expr fe1 e = Add (Const 1) (Const 1) -- non-recursive fe2 e = Add (Const 1) e -- recursive You can always get the value of an Expr from a Fix Expr whenever you need it, by computing the fixed point: fix f = x where x = f x If it can be computed. Maybe I'm off-track here, but it seems to me that when you introduce laziness into the equation, you lose any guarantee of there even being a fixpoint, much less one that can be computed. Actually it's the other way around -- laziness is what makes this work! The least fixpoint of fe2 in a strict language, for example, is bottom. e1,e2 :: Expr e1 = fix fe1 -- finite e2 = fix fe2 -- infinite Note that e2 is equivalent to your cyclic. But now we can also test for equality: instance Eq (Fix Expr) where fe1 == fe2 = fe1 Loop == fe2 Loop For example, fe2 == fe2 returns True, whereas e2 == e2 (i.e. your cyclic == cyclic) diverges. Of course, note that, although fe1 == fe2 implies that fix fe1 == fix fe2, the reverse is not true, since there will always be loops of varying degrees of unwinding that are semantically equivalent, but not syntactically, or structurally, equivalent. Thus this definition of equality is only approximate, but still, it's useful. I'm lost. Are you saying bottom is bottom? I suspect from your other post that you haven't seen the standard trick of encoding infinite data structures as fixpoints. Suppose you have a lambda calculus term for cons, as well as for the numeral 1. Then the infinite list of ones is just: Y (\ones. cons 1 ones) where Y (aka the paradoxical combinator or fixed point combinator) is defined as: \f. (\x. f (x x)) (\x. f (x x)) To see this, try unfolding the above term a few iterations using normal-order reduction. Note that the term has no recursion in it whatsoever. Now, my earlier point above is that: Y (\ones. cons 1 ones) unwinds to the same term as: Y (\ones. cons 1 (cons 1 ones)) yet the two terms (\ones. cons 1 ones) and (\ones. cons 1 (cons 1 ones)) are not the same (in fact they're not lambda convertible, either). -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Detecting Cycles in Datastructures
Greg Woodhouse wrote: --- Paul Hudak [EMAIL PROTECTED] wrote: Y (\ones. cons 1 ones) where Y (aka the paradoxical combinator or fixed point combinator) is defined as: \f. (\x. f (x x)) (\x. f (x x)) Now, this is I have seen, but it frankly strikes me as a formal trick. I've never felt that this definition of Y gave me much insight into the computation you describe below. To see this, try unfolding the above term a few iterations using normal-order reduction. Note that the term has no recursion in it whatsoever. Now, my earlier point above is that: Y (\ones. cons 1 ones) unwinds to the same term as: Y (\ones. cons 1 (cons 1 ones)) yet the two terms (\ones. cons 1 ones) and (\ones. cons 1 (cons 1 ones)) are not the same (in fact they're not lambda convertible, either). -Paul And this is what leaves me scatching my head. If you leave off the ones, then you get a sequence of finite lists [1], [1, 1], ... that seems to approximate the infinite list, but I find it difficult to imagine how you might pluck a formula like \i. 1 (the ith term) out of the air. The important property of Y is this: Y f = f (Y f) In this way you can see it as unwinding the function, one step at a time. If we define f as (\ones. cons 1 ones), then here is one step of unwinding: Y f == f (Y f) == cons 1 (Y f) If you do this again you get: cons 1 (cons 1 (Y f)) and so on. As you can see, continuing this process yields the infinite list of ones. Now note that if we define g as (\ones. cons 1 (cons 1 ones)), we get: Y g == g (Y g) == cons 1 (cons 1 (Y g)) which obviously also yields the infinite list of ones. Yet f is not equal to g. Does this help? -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Infinite lists and lambda calculus
Cale Gibbard wrote: Y = (\f. (\x. f (x x)) (\x. f (x x))) In a sense, the real definition of Y is Y f = f (Y f), this lambda term just happens to have that property, but such functions aren't rare. Actually no, the real definition is the top one, because the other one isn't even a valid lambda term, since it's recursive! There is no such thing as recursion in the pure lambda calculus. Of course, there are many valid definitions of Y, as you point out, both recursive and non-recursive. But I do believe that the first one above is the most concise non-recursive definition. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] A Gentle Introduction to Haskell Version 98
Reuben Thomas is not a co-author of the Gentle Introduction, although it looks like he's had something to do with the HTML rendering of it. John Peterson would know more about that but I think that he's off-line for awhile. In any case, the non-HTML versions should all be consistent, with Hudak/Fasel/Peterson as authors. I really don't know much about the HTML version, except that it's handy to have on-line :-) -Paul Hudak Wolfgang Jeltsch wrote: Hello, the web page under http://haskell.org/tutorial/ says: This is the master HTML version of the Gentle Introduction To Haskell, version 98. Revised June, 2000 by Reuben Thomas. However, the Postscript, gezipped PDF, PDF and DVI versions don't mention Reuben Thomas as co-author and have October 1999 as their date. The downloadable HTML version doesn't mention Reuben Thomas too and has September 28, 1999 as its date. So what is true? Ist the online version different from the download versions and is the downloadable HTML version different from the other download versions? Did Reuben Thomas modify the tutorial? Which versions do contain his modifications, which not? Best wishes, Wolfgang ___ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell] how to cite the (revised) Haskell Report
Alternatively, you could cite the book version:
@book{Haskell98Book
,editor={Simon Peyton Jones}
,title={Haskell 98 Language and Libraries -- The Revised Report}
,publisher={Cambridge University Press}
,address={Cambridge, England}
,year=2003
}
Ben Horsfall wrote:
On 14/09/05, Wolfgang Jeltsch [EMAIL PROTECTED] wrote:
Would someone be able to post a sample BibTeX entry? That would be nice.
I cite it like this:
@article{haskell98,
author = {Simon {Peyton Jones} and others},
title = {The {Haskell} 98 Language and Libraries: The Revised Report},
journal = {Journal of Functional Programming},
volume = 13,
number = 1,
pages = {0--255},
month = {Jan},
year = 2003,
note = {\url{http://www.haskell.org/definition/}},
}
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
--
Professor Paul Hudak
Department of Computer ScienceOffice: (203) 432-1235
Yale University FAX:(203) 432-0593
P.O. Box 208285 email: [EMAIL PROTECTED]
New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak
___
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] a newbie's question
Thomas Davie wrote: On Apr 21, 2005, at 3:47 PM, SCOTT J. wrote: Hi, I'm beginning to study Haskell, For the following a = [1,2,3] b = there do x - a y - b return (x , y) Winhugs cannot run it. Gives Syntax error in input (unexpected backslash ( lambda)) Your problem is that you're using monads to grab the contents of a and b, while a and b are not monadic... You probably if you're only just setting out don't want to pay attention to any of the do notation or monadic code. To get the result it looks like you want, all you need to do is this: (a, b) you can then define this as a new constant: c = (a, b) Hope that helps Bob On the other hand, perhaps he wanted all possible combinations of values in the lists a and b. Since a list is a monad, this, for example, works fine: a = [1,2,3] b = there abs = do x - a y - b return (x,y) In Hugs: abs == [(1,'t'),(1,'h'),(1,'e'),(1,'r'),(1,'e'),(2,'t'),(2,'h'),(2,'e'),(2,'r'),(2,'e') ,(3,'t'),(3,'h'),(3,'e'),(3,'r'),(3,'e')] -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: Answers to Exercises in Craft of FP
Chris, I'm not sure that I understand your argument. How about this scenario, which is what I do: Students are assigned problems, without solutions. They are given some time to work them out and turn them in. Then they are given the solutions, most of which I go over in class. This does not require posting solutions ahead of time, or in a public place, it still allows the autonomous student to do the work on his or her own (although constrained by a particular time-frame), and it permits the student to see the solutions in the end. -Paul Christian Hofer wrote: Dear Hamilton, I think we just have a different framing of the problem. You are confronted with the laziness of students and want to teach them something anyway. By that you are forced to disrespect the autonomy of students who are intrinsically motivated (e.g. by giving bonus points on exercises). I on the other hand am a great fan of the old German university system, which they are currently about to abolish in the so-called Bologna Process. The idea is to just treat students as if they were autonomous. Most students fail in the exams in their first year, because they are not used to solving exercises when nobody forces them to do it (s.th. they should of course already have learned in school). Those students that don't recover don't belong to university. But most students learn from this negative experience, that they have to work on their own. And that is more important to learn on university than the details of a certain programming paradigm... It's nice that you offer me your exercises with solutions. But I am afraid that does not really help me, because I want to do (and am actually doing) the exercises in the books that I read (because that is the way to get a better understanding). Thus what I would need are the solutions to those exercises. Regards, Chris ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Professor Paul Hudak Chair, Dept of Computer Science Office: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] What are the MonadPlus laws?
Good point; I suppose the constraint m /= _|_ should be added to the law. [EMAIL PROTECTED] wrote: The problem is this law: m = \k - mzero === mzero I think this law is untrue for _all_ MonadPlus instances, and you can trivially check this by setting m to bottom. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Some random newbie questions
Benjamin Pierce wrote: OK, I'm taking the plunge and using Haskell in a course I'm teaching this semester. To get ready, I've been doing quite a bit of Haskell programming myself, and this has raised a few questions... * What are the relative advantages of Hugs and GHC, beyond the obvious (Hugs is smaller and easier for people not named Simon to modify, while GHC is a real compiler and has the most up-to-date hacks to the type checker)? Do people generally use one or the other for everything, or are they similar enough to use Hugs at some moments and GHC at others? I taught our FP class this fall using Hugs, but in the end wish that I had used GHC. There are lots of little reasons for this, but a big one was a problem with unpredictable space utilization. I don't have the examples at my fingertips, but there were simple variations of the same program that, by all common-sense reasoning, should have behaved in the opposite way with respect to space than what they exhibited. Indeed, the problem that you report in your Sierpinkski Carpet may likely be a problem with Hugs, and not the graphics lib, and Jacob Nelson's message seems to bear this out. SOEGraphics, by the way, is built on top of HGL, a general graphics lib written by Alastair Reid. At the time, it was the best option that we had, but Alastair no longer has time to maintain it, although I believe that Ross Paterson may be maintaining it now. In any case, SOEGraphics has grown a big buggy with respect to portability across platforms and compilers. I am about to update the SOE webpage with our current best shot at a portable and bug-free version of this, but ultimately I'd like to port everything over to something like wxHaskell. -Paul ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Non-technical Haskell question
Aaron Denney wrote: On 2004-12-06, Gour [EMAIL PROTECTED] wrote: Any idea how to make a (more organize) community effort to bring Haskell out? I'd rather it didn't until a few warts were fixed. OTOH, it may be too late already, barring a Haskell 2. Does Python not have warts? Or Pearl, or Java, or C#? I don't think that a few warts prevent a language from becoming a success. But you may be right that it is too late... Haskell is getting old! Sometimes I think that for a language to succeed it must do so in its infancy. Perhaps the thing to do is create a new language with a new name, but base it entirely on Haskell's semantics, then equip it with just one really good library to solve well just one important niche problem, and see what happens. If it is seen as a shiny new silver bullet in just one niche area, it might take off like a rocket. -Paul Time flies like an arrow. Fruit flies like an apple. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Sorry, I had to drop out of this thread for a few days...
Ben Rudiak-Gould wrote:
Paul Hudak wrote:
Note that instead of:
data Shape = Circle Float
| Square Float
the Haskell designers might have used the following syntax:
data Shape where
Circle :: Float - Shape
Square :: Float - Shape
which conveys exactly the same information, and makes it quite clear
that Circle and Square are functions.
No, this is totally different from what I'm talking about. My position
for the moment is that they *aren't* functions (or, more precisely, that
they shouldn't be so taught), and anything that tries to further the
illusion that they are is then a step in the wrong direction.
Well then, I guess we'll just have to agree to disagree...:-) They are
very definitely functions in my mind: they can be applied, passed as
arguments, etc. If it acts like a duck, then it is a duck. The
confusion is that they are MORE than just functions, because of their
special treatment in pattern matching. But to deny their functionhood
in like denying a king his manhood :-)
In particular, your notation with type signatures makes it totally
unclear that Circle and Square have disjoint ranges; in fact it looks
like they have the same range.
But they DO have the same range -- they're just not surjective.
That said, what you ask for is not unreasonable, it's just that I don't
know how to express it in Haskell, for any kind of function. (Unless
one were to explicity encode it somehow.)
This notation would have increased my
confusion when I was still learning, because what I didn't understand at
that time was the nature of the type Shape. Saying that Circle and
Square are functions which take a Float and return a Shape tells me
nothing about what a Shape is; it might as well be an abstract data
type. What I needed to know, and was never clearly told, was that Shape
is *precisely the following set:* { Circle 1.2, Circle 9.3, ..., Square
1.2, Square 9.3, ...}. You could even throw in a _|_ and some
exceptions-as-values, though I'm not sure it would have been advisable
(little white lies are an important pedagogical tool, as long as you
eventually own up).
Yes, I can understand your confusion, and I have had students express
the same thing. But after I explain essentially what you have written
above, there was no more trouble.
The syntax that would have made the most sense to me would have been
something like
data Shape =
forall x::Float. Circle x
forall x::Float. Square x
with maybe a + or something joining the lines, though that might have
done more harm than good.
I don't see much advantage of this over Haskell's current syntax. You
still need to explain its semantics in a way that suits your needs, so
you might as well explain the original syntax in the same way.
Of course GHC 6.4 has your function syntax now with the introduction of
GADTs, but I think that it's a mistake; in fact it's interfering right
now with my attempt to understand what GADTs are! I suppose I would prefer
data Term a =
forall x :: Int. Lit x :: Term Int
forall x :: Term Int.Succ x :: Term Int
forall x :: Term Int.IsZero x :: Term Bool
forall x :: Term Bool.
forall y,z :: Term a. If x y z :: Term a
In fact, maybe I'll try rewriting everything in this form and see if it
helps me. I suppose once I do understand GADTs I'll have a better idea
of what would have helped.
I almost mentioned GADT's earlier, but didn't want to stray too far from
the path. In fact GADT's strengthen my argument, but I see you don't
like their syntax either.
That said, there are lots of interesting directions to pursue where
pattern-matching against functions IS allowed (requiring higher-order
unification and the like). I suppose that topic is out of the scope
of this discussion.
I don't think I've heard of this (unless you're talking about logic
programming). Can you point me to some papers?
The work that I'm only somewhat aware of is that out of the logical
frameworks community, where higher-order abstract syntax makes it
desirable to work underneath the lambda, in turn making it desirable
to pattern-match against lambdas. See, for example, Carsten
Schuermann's work (http://cs-www.cs.yale.edu/homes/carsten/).
-Paul
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie Question on type constructors
Ben Rudiak-Gould wrote: Have I succeeded in reconciling our views? Perhaps! In particular, perhaps it's just a pedagogical issue. Note that instead of: data Shape = Circle Float | Square Float the Haskell designers might have used the following syntax: data Shape where Circle :: Float - Shape Square :: Float - Shape which conveys exactly the same information, and makes it quite clear that Circle and Square are functions. I often point this out to my students, because I find it less confusing than Haskell's data type declaration, where type constructors and value constructors are intermixed (i.e. Circle Float). Would this have been less confusing for you? As for pattern matching, I think the key point relates to Keith Wansbrough's comment that an algebraic data type denotes an initial algebra. If you want to retain referential transparency, each application of the function being pattern-matchined against must yield a unique value (i.e. no confusion as Keith describes it). This is guaranteed with a constructor, but not with arbitrary functions. So, another way to look at it is that constructors simply carve out a portion of the function space where this can be guaranteed. That said, there are lots of interesting directions to pursue where pattern-matching against functions IS allowed (requiring higher-order unification and the like). I suppose that topic is out of the scope of this discussion. -Paul Ben Rudiak-Gould wrote: Paul Hudak wrote: Oh, I disagree with this point of view. Circle is certainly a value, i.e. a full-fledged function, as Brian Beckman correctly surmised. Interesting. I don't claim that my viewpoint is the One True Path, but I don't think it's wrong, either. I know you're interested in the teaching of Haskell, and the fact remains that I *was* confused by data constructors when I learned Haskell, and it *did* help me to stop thinking of them as functions. Different people learn in different ways, and that's how I learned; even now I find this view more natural than the view of constructors as functions. The wording of the OP's article made me think that he might be suffering from the same conceptual problem, so I tried to suggest the approach which worked for me. The Haskell designers did not decide for convenience that Circle is the same as \x - Circle x. Rather, that's a fundamental law (the eta law, to be exact) of the lambda calculus, on which Haskell is based. I think you're begging the question here -- the eta law applies to functions -- but maybe you're just elaborating on your view rather than arguing for it, as I was. (I.e. I was elaborating, not arguing, when I said that Circle was a function for convenience.) The real reason that the Haskell designers chose to have constructors begin with a capital letter is to make pattern-matching clearer. Certainly it's odd to be able to match on the result of a function. case factorial (2*3) of factorial n - ... won't work, so it's surprising that case Circle (2*3) of Circle x - ... does, if Circle is a function. On the other hand, if Circle 6 is just a literal value, it's not at all surprising that case Circle 6 of Circle x - ... does what it does. And, at least for me, that extends to case Circle (2*3) of Circle x - ... as well. (*) is being called in this example, and is returning an entirely new value, 6, but Circle is just getting added on to that result, and then stripped off again. There's a clear symmetry between construction and deconstruction which doesn't seem nearly as clear if Circle is seen as a function. It occurs to me that when I talk about functions here, I am talking about Haskell function values, not about functions as equations f(x) = In particular, one cannot write an invert :: (a-b) - Maybe (b-a) which never returns a wrong answer, except for invert = const Nothing -- this is why it makes no sense to me to imagine Circle as being a Haskell *value*. I have no problem imagining it as a function in a more abstract mathematical sense; it's just that Haskell function values don't have that extra structure. The view of Circle that I was trying to express is closer to Prolog clauses. One can assert circle(1.2), and that assertion will match circle(x), but it doesn't really make sense to assert circle, or to try to match it. Have I succeeded in reconciling our views? -- Ben ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell] Question about Infix/Postfix Operators in Haskell
Pedro Vasconcelos wrote: On Mon, 18 Oct 2004 09:51:52 +0200 Georg Martius [EMAIL PROTECTED] wrote: On Mon, 18 Oct 2004 09:43:26 +0200, Peter Theissen [EMAIL PROTECTED] wrote: Hi, is there any possibility of defining Infix-/Postfixoperators in Haskell? Example: Plus :: Int, Int - Int Plus x y = x + y an now I´m want to use Plus in another function as an infix: Times2:: x = x Plus x Another possiblity: define a new operator (let's call it $+) and you do without the backquotes: infixl 5 $+ ($+) :: Int-Int-Int x $+ y = x+y times2 x = x $+ x This way you can specify the associativy and binding precedence and reduce the need for parenthesis. Note that you can define associativity and precedence of ANY function used as an infix operator, and you can also use it in an infix manner when it is defined. For example: infixl 5 `plus` plus :: Int-Int-Int x `plus` y = x+y times2 x = x `plus` x -Paul ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [Haskell-cafe] Re: The State Monad
Sorry to nit-pick, but state monads are NOT syntactic sugar -- they're just an example of good old data/functional abstraction, that also happens to be in the form of a monad. On the other hand, Haskell's do notation -- now THAT'S syntactic sugar :-) -Paul Ben Lippmeier wrote: John Goerzen wrote: Which leaves me with an odd curiosity -- I still can't figure out how state monads are anything but syntactic sugar (and lead more to spaghetti code at that g) Perhaps because state monads = syntactic sugar. The state monad is just a nice(er) way of passing around some global state (Junk). Without state monads f :: Junk - a - (Junk, b) With state monads, f :: a - State Junk b Though if some function doesn't need to 'modify' your Junk, you find yourself having to re-factor things like, decend :: Junk - Exp - Exp decend state (Node a t1 t2) = Node a (decend state t1) (decend state t2) into decend :: Exp - State Junk Exp decend (Node a t1 t2) = do t1'- decend t1 t2'- decend t2 return $ Node a t1' t2' .. which IMHO is not as pretty. Ben. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Integrating Haskell into a J2EE environment
Ok, I understand. I don't know much at all about J2EE, in fact! I would just hate to see an interesting project be abandoned if all that is needed is a simple way to invoke the Haskell code with a string argument, say. Perhaps Shoeb can tell us more about what he needs. -Paul Doug Kirk wrote: Yes, I agree, and didn't mean to write off Haskell (at which, I'm completely a newbie, trying to learn, and thankful for your book!). However, I'm a Java pro, and there are many technical issues on the Java side that scream at me to keep out of the native arena, especially in a J2EE container environment, where funny things can happen with hot reloads (dumping old ClassLoaders for new ones), clustering, and the like. So it wasn't out of denigration of Haskell that I made my recommendation; far from it...from what I've seen Haskell is perfect for implementing DSL's. Rather, from the Java side is where it becomes problematic. There have been many problems integrating with native libraries from within a J2EE container, and I try to seek the most cost-effective way (I'm an independent consultant) to get the problem solved for my customers. --doug On Oct 6, 2004, at 2:59 PM, Paul Hudak wrote: I wouldn't write off Haskell so quickly. All of what Shoeb describes concerning DSL issues might be much more easily solved in Haskell, and will certainly be more flexible than a hard-wired approach. The J2EE interface might be ugly, but if the functionality needed is not too great it might not be too bad. Generally speaking, these kinds of apps -- in this case a DSL for high-level business rules -- sounds like just the sort of thing that Haskell is good for. -Paul ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] (no subject)
To add briefly to what John wrote, there is a webpage for Yampa: www.haskell.org/yampa which includes all of our publications on FRP/Yampa as well as a decent release of our latest implementation of Yampa (based on arrows). The release has ample examples of how to use Yampa for graphics, animation, and basic control systems such as used in robotics. Also, although most of the developers have dispersed, I believe that most of them are still interested in the ideas, and the [EMAIL PROTECTED] mailing list would probably be responsive if anyone bothered to use it. -Paul Hudak John C. Peterson wrote: From: John Peterson [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [Haskell-cafe] Functional Reactive Programming Functional Reactive Programming is alive but in need of some new students to push the effort a bit. A lot of us have taken teaching or industrial positions so the old FRP team is a bit depleted. I don't think anyone is working on Yampa directly at the moment. Although it's stable and working well it lacks a critical mass of nice libraries to make it attractive. I'm still plugging on a wxHaskell port to Yampa (the wxFruit stuff). I've made some semantic changes to Yampa so I probably shouldn't say it's real Yampa but pretty close. I should have something to release later this fall. Aside from that, we have a student working in the hybrid modeling area. That's good stuff but not likely to produce software of interest to Joe Haskell. Another student is keeping the robotics side of things alive but it's in the context of a very specialized robotic hardware environment. So there you go! John ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Professor Paul Hudak Chair, Dept of Computer Science Office: (203) 432-1235 Yale University FAX:(203) 432-0593 P.O. Box 208285 email: [EMAIL PROTECTED] New Haven, CT 06520-8285 WWW:www.cs.yale.edu/~hudak ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] so how does one convert an IO a into an a ?
Judging from a previous message I'm not sure if you're still using SOE, but one of the things I tried to do is introduce IO without mentioning monads at all, and if you read chapter 3 (especially section 3.1) you will see that that's the case. To those who have had imperative programming experience, I think that section 3.1 should not present any problems. But it sounds as if you've gotten past that, since you quoted something from chapter 18, where the mysteries of IO are revealed in gory detail. It looks like lots of people have given you good advice, but I'll throw in one more idea about how to convert an IO Int into an Int. Although, as many have pointed out, you can't really do this in a technical sense, you can get the effect that you want as follows: Suppose you have a function foo of type IO Int, and you wish to apply a function bar of type Int - T to the value you get from foo (T is some result type). Then all you have to do is this: do i - foo return (bar i) This is what people meant by writing a little monadic scaffolding to achieve what you want. The function bar is a pure function that does not involve IO at all. It may involve dozens of page of code, but you need the two lines of scaffolding above in order to invoke it. Now, in the end, you might say that we haven't achieved much, because the above expression has type IO T, so all we've really done is convert an IO Int into an IO T. Quite true! That's why most of the people who responded to your email eventually wrote something like: do i - foo putStr (show (bar i)) or whatever, in order to actually generate some useful output. Indeed, that useful output might also include writing to a file, displaying some graphics, etc. I hope this helps, -Paul Crypt Master wrote: Hi Thanks for your help so far, but I am still not getting this IO stuff. After reading your previous help and reading several articles on it I still cant phathom how you convert the IO Int into an Int. One person mentioned how random just returns an interative program which when eveluated returns the Int. Also from the school of expression book he says The right way to think of (=) above is simply this: It Executes e1 ... in relation to do pat - e1 so I have this: code rollDice :: IO Int rollDice = getStdRandom (randomR (1,6)) rl :: [Int] rl = [ (getRndNum x) | x - [1..] ] getRndNum :: Int - Int getRndNum x = do n - rollDice return n /code *PS Pretend return is correctly aligned under n. dont what ahppens in copy and paste* now my understanding therefore is that do n - rollDice should execute the the itererative program returned by rollDice. So now n should be my Int since IO Int was a program which when evaluted returns an Int ? However this is what haskell thinks of my thoery: *** Term : getRndNum *** Type : Int - IO (Maybe Int) *** Does not match : Int - Int So I am still in IO Int land despite having used the = in the do syntax. Worse Still I am in IO (Maybe Int) land. Monads within Monads. In yours, and many other examples I found online, the results are always passed to print which seems to know how to deal with an IO Int. Is this specially coded or overloaded or something ? There are plenty of examples which use return like so: do k - getKey w return k which is what I tried above to no avail. It seems awefully complicated just to get hold a simple Int, but naturally complicity is directly related to ones understanding. Mine is sumewhat lacking ... any help would be appreciated. Thanks, S ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Haskell and sound (was: [Haskell-cafe] Toy application advice wanted)
For what it's worth, SOE and Haskore provide support for reading and writing MIDI files, and for generating both score and orchestra files in csound. But there is no direct support for sound files, nor is there support for real-time MIDI. -Paul Claus Reinke wrote: (SOE's music component includes Midi file support, and also talks about csound)? ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: determining if a int is a power
But note that x `seq` x is equivalent to x, even operationally. To see why denotationally, note that if x evaluates to _|_, so does x `seq` x. And if x evaluates to a value v, so does x `seq` x. To see why operationally, consider the two lists: let x = 1+1 in [x `seq` x] let x = 1+1 in [x] Using conventional lazy evaluation in both cases, the term 1+1 is not evaluated until the head of the list is taken. In other words, x `seq` x in no way hurries the evaluation of x. -Paul Wolfgang Jeltsch wrote: Am Samstag, 8. November 2003, 00:22 schrieb Hamilton Richards: Also note that if x then True else False is just a verbose way of writing x Actually, it's just a verbose way of writing x `seq` x, but this detail is, of course, not interesting for beginners. Wolfgang ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: fixed point
Thomas L. Bevan wrote: Is there a simple transformation that can be applied to all recursive functions to render them non-recursive with fix. Suppose you have a LET expression with a set of (possibly mutually recursive) equations such as: let f1 = e1 f2 = e2 ... fn = en in e The following is then equivalent to the above, assuming that g is not free in e or any of the ei: let (f1,...,fn) = fix g g ~(f1,...,fn) = (e1,...,en) in e Note that all recursion introduced by the top-most LET has been removed (or, if you will, concentrated into the one application of fix). This transformation will work even if there is no recursion, and even if some of the fi are not functions (for example they could be recursively defined lazy data structures). For example: main1 = let rem = \a b - if a b then a else rem (a - b) b ones = 1 : ones x = 42 in (rem 42 9, take 3 ones, x) is equivalent to: main2 = let (rem,ones,x)= fix g g ~(rem,ones,x) = (\a b - if a b then a else rem (a - b) b, 1 : ones, 42 ) in (rem 42 7, take 3 ones, x) and both yield the result (6,[1,1,1],42). -Paul ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: fixed point
Also, had a feeling the fix function was related to the Y combinator; it seems they're the same thing! Yes, they're the same in effect, although historically fix is often defined recursively or taken as a primitive, whereas Y has its roots in the lambda calculus, where it is defined as: Y = \f.(\x.f(x x))(\x.f(x x)) which, you will note, is not recursive, yet has the property that Y f = f (Y f), so that it is in fact a fixpoint generator. (You might want to try proving this -- it's easy and illuminating.) Unfortunately, this expression will not type-check in Haskell or ML because of limitations of the Hindley-Milner type system :-(. There are ways around this, but they involve introducing a data structure to avoid problems with infinite types. -Paul ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Haskell for non-Haskell's sake
Well, there's PADL (Practical Aspects of Declarative Languages), see http://www.research.avayalabs.com/user/wadler/padl03/. -Paul Tim Docker wrote: Jerzy Karczmarczuk wrote: Presumably this reviewer has his particular visions what a science is, but I don't believe that such people dominate in the milieu of FPL. I believe that it would be interesting to organize some workshops on practical applications of functional programming...) Actually, I would be more likely to attend a workshop focusing on real world applications of functional programming than one on more theoretical advances (as interesting as they are). Tim ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: [OT] Teaching Haskell in High School
I can't resist jumping in on this one: Haskell just has some terrible properties when it comes to teaching beginners. Among them are the complex and easy-to-get-wrong syntax, the available programming environments which are OK for developers but awful for beginners. There's also a dearth of good textbooks at the level you need. Haskell is very easy to learn (and an excellent choice for a 2nd or 3rd language) when you know Scheme. I have spent many years teaching both Scheme and Haskell to beginners, and I would have to say that Haskell syntax has never been a serious problem, certainly no more than Scheme's parentheses. It is true that there is a lack of good programming environments, although Hugs is pretty easy to use, and things like Helium should be even better. (I won't say much about textbooks since I wrote one that I think is pretty good for beginners :-) Finally, aside from extraneous type error messages (which Helium should do much better at), I claim that Haskell's type system is BETTER for beginners compared to having no type system at all. As for the last point above, I could just as easily say that Scheme is very easy to learn (and an excellent choice for a 2nd or 3rd language) when you know Haskell. Now, having said all this, I will add that I have the greatest respect for the TeachScheme project, and I wish that we had something as well developed for Haskell! -Paul ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: representation getting verbose...
In Paul Hudak's SOE, I find a definition of expression: data Expr = C Float | V String | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr Now this is compelling, but sometimes, I might want to have a function that takes a variable only, not just any kind of expression. I could write something like: typeOfVariable :: Expression - Type typeOfVariable (V s) = ... _= error... But thats not very satisfying from a type-checking perspective. So it makes sense to create a constructor: data Variable = VVariable String data Expr = C Float | V Variable | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr and make typeOfVariable :: Variable - Type. But then when I want to match or create a variable expression, things are starting to get verbose: case expr of C f - ... V (Variable (VVariable s)) - ... ... I think you mean: case expr of C f - ... V (VVariable s) - ... which is not quite as verbose. And if I want a still more accurate hierarchy, the construction and destruction of Variables can really become cumbersome. For an interpreter I'm writing, I found myself writing a function constructVarExpr :: String - Expr just to make it easier. This all seems very inelegant, and I get the feeling that there's a better way to do this. Any suggestions on how I could better represent Expressions or Variables to keep the type-checking but decrease the verbosity? I don't think that the problem is as bad as you make it out to be. If you adopt my use of short constructor names, then something like: data Var = Var String data Expr = C Float | V Var | Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr is quite concise, as is: case expr of C f - ... V (Var s) - ... Also I don't see the point of defining constructVarExpr since constructVarExpr s is not much clearer or shorter than V (Var s). On the other hand, there are much deeper issues at play here regarding the representation of a language with variables as a data type. What I did in my book was very simple, and the use of variables was only given as an exercise (by the way, you left out the Let constructor, which presuambly has the form Let String Expr). Ideally you will also want to express polymorphism and properly-typed higher-order functions, which gets into the use of phantom types. A more recent idea is to use higher-order abstract syntax, in which variables and functions of the language being implemented (often called the object language) are modelled as variables and functions in the implementation language (often called the meta language), i.e. Haskell. For a good explanation of this, see Morton Rhiger's paper A simple take on typed abstract syntax in Haskell-like languages at: http://www.brics.dk/~mrhiger/daimi-pub.html Hope this helps, -Paul ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Depth-First search problems
I'm not sure whether your program is correct, but it's easy to see why you're getting the type error. You define p(_, k) = empty k, but empty has type BinTree t - Bool, so clearly p has type (a, BinTree t) - Bool. However, you use p in until p f ([], Push CreateStack b). Since until has type (a - Bool) - (a - a) - a - a, this implies that p must have type ([a], Keller (BinTree t)) - Bool. So you need to either fix the definition of p or fix how it is used. By the way, you are missing the case (Bin _ _ _) == EmptyTree in the instance decl. Also, note that Keller t is isomorphic to [t], i.e. to the list data type. Specifically, CreateStack is [], Push is (:), top is head, and pop is tail. Hope this helps, -Paul Hudak -- Binary Tree structure data BinTree t = EmptyTree | Bin (BinTree t) t (BinTree t) left (Bin b1 _ _) = b1 right (Bin _ _ b2) = b2 value (Bin _ v _) = v empty EmptyTree = True empty (Bin _ _ _) = False -- Give the Binary Tree == instance Eq a = Eq (BinTree a) where (Bin b v c) == (Bin d w e) = (v == w) (b == d) (c == e) EmptyTree == EmptyTree = True EmptyTree == Bin _ _ _ = False -- Stack structure data Keller t = CreateStack | Push (Keller t) t top (Push s x) = x pop (Push s x) = s -- Depth-First search tiefensuche b = fst (until p f ([], Push CreateStack b)) where p(_, k) = empty k f(erg, k) | (top k) == EmptyTree = (erg, pop k) | otherwise = ([v] ++ erg, Push( Push( pop k) b2) b1) where (Bin b1 v b2) = top k The error message says that p has a wrong types Haskell thinks it is p :: (b, BinTree c) - Bool, instead of p :: ([a], Keller (BinTree a)) - Bool ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Fwd: F#]
Hey Simon et al at Micro$oft, when will there be an H#? (Ok, I'll settle for Haskell.NET :-) -Paul ---BeginMessage--- Title: Message Paul, I just saw this, and I think you and I were talking about using ML. Let me know if we need to follow-up on this further. Scott F# Sections UpF#FAQAboutF#DownloadF#F#ManualF#ComparedF#ToolSupportF#Performance Announcements A presentation on F# is now available (April 2002) Coming soon: The First F# Language Release (April 2002) A new version of the ILX reference manual is available. This is considerably updated from previous versions (January 2002) Version 0.5 of the AbsIL/ILX SDK is now available.(April 2002) F# is a mixed functional/imperative programming language based on the design of the functional language Caml and the .NET language C#. Combining the speed, safety and productivity of ML and Caml with the libraries, tools and cross-language working of .NET Mixed functional/imperative programming is a fantastic paradigm for many programming tasks. Languages such as OCaml and Standard ML provide excellent general purpose programming languages suited to medium-advanced programmers who want simple yet highly expressive tools that boost their productivity, primarily by reducing the error rate, increasing their productivity through type inference, and basically letting them focus on the difficult parts of their applications. You can access hundreds of .NET libraries using F#. F# is an implementation of the core of the Caml programming language for the .NET Framework, along with cross-language extensions. The aim is to have it work together seamlessly with C#, Visual Basic, SML.NET and other .NET programming languages. In particular it is the first ML language where all the types and values in an ML program can be accessed from some significant languages (e.g. C#) in a predictable and friendly way. The aim of F# is to have a mixed functional- imperative language that works together seamlessly with C# and other .NET languages. Purely functional languages like Haskell are excellent within certain niches, but many simple programming exercises can quickly turn into problems that require a PhD. to solve. Purely imperative programming languages like C or Pascal do not provide satisfying mechanisms for abstraction or data manipulation. Purely object oriented languages like Smalltalk are excellent for some dynamic applications but do not provide static guarantees. Typed class-based languages like C# and Java contain a very large number of constructs, and it can sometimes be difficult for programmers to choose how to model their problem, and sometimes result in very large amounts of code just to solve quite simple problems. In contrast, languages such as Caml provide a smaller number of simple, orthogonal constructs which work together to allow for succinct yet efficient solutions to programming problems. F# provides an implementation of a subset of the OCaml libraries as well as the ability to access .NET libraries. Using the .NET libraries is optional. F# provides a subset of the OCaml libraries, so you don't have to use .NET libraries if it is not appropriate. It is possible to write large applications that can be cross-compiled as either OCaml bytecode, OCaml native code or F# code, for example, the F# compiler itself is written this way. This lets you reuse the investment you make in the core of a project while letting you write some parts of your application as F# code that makes use of .NET extensions. The following links will let you learn more about F#: Basic programming in F# Using C# and other .NET libraries from F# Using F# libraries from C# Using the F# library To access .NET constructs, see the extra language features supported in this release. Learn how to write high-performance F# code F# also provides a simple, familiar set of tools: A simple command line compiler, supporting separate compilation, debug information and optimization.
Re: [Fwd: F#]
Hi Don -- Thanks for all the informative stuff regarding FP implementations on .NET. However I am a little surprised by one thing you say: ... But the only truly serious complications added by .NET itself are (a) the general problem of Haskell interop with imperative libraries, requiring you to reach for monads quite often (or to wrap the libraries yourself) and (b) ... IMHO problem (a) will always be the thing that stops Haskell becoming very very big. But then being non-imperative it's also its main selling point... Are you saying that Haskell users would reject this? (to which I would disagree, since that's what we would expect) Or new users? (to which I would say that the jury is out) I would think that the biggest impediment to Haskell.NET would be efficiency, in both the generated code (primarily because of lazy evaluation) and in compile time (at least with an optimizing compiler such as GHC). -Paul ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: Ex 9.9 in Paul Hudak's book
What I would like to know is how the 'fix' function could be used to find the fixed point of a function like ( \n - 2*n ). Olaf and Lennart said a little about least fixpoints, but little about what makes a fixpoint least. Olaf suggested looking up papers on domain theory or denotational semantics to understand it better. But the idea is really simple: just think of it as an ordering on information content. Bottom (_|_) contains NO information, and is thus the least value in any domain. The integers 1, 2, 3, etc. contain the same amount of information, but the information in each case is different -- thus these values are incomparable in the information ordering. So even though \n - n has all these values as fixpoints, the LEAST one is _|_. As for \n - 2n, even though 0 is a fixpoint, the LEAST one is _|_. And fix will find these for you, in the sense that fix applied to each of these functions leads to non-termination, and non-termination is equivalent to bottom, since it yields NO information. (The fact that in some implementations the stack or heap will blow up is an implementation artifact.) If it isn't possible, can someone explain the crucial difference between n! and (\n - 2*n) which allows n factorial to be found via the fix point method and not zero. fix is able to find the fixpoint of: \f - \n - if (n==0) then 1 else n*f(n-1) This fixpoint is a FUNCTION, not the factorial value itself. So they are very different. Which begs the question: can fix find fixpints that are not functions, and not bottom? Consider this well-known example: ones = 1 : ones We can write this as: ones = (\wons - 1 : wons) ones and thus: ones = fix (\wons - 1 : wons) Try this in Hugs, and see what happens when you type take 10 ones at the prompt. -Paul ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
