Re: [Haskell-cafe] GHCi and State
Hi Corentin, Interesting. Have you thought about following the example of XMonad instead? The analogy could goes as follows: XMonad's configuration file (~/.xmonad/xmonad.hs) <=> Your rules. XMonad's state <=> Your state. Editing the config file <=> Changing the rules. Of course you normally edit the config file while XMonad is running, and in theory XMonad could do funny things to your Emacs, i.e. require you to vote before letting any edit-command through. When you change your configuration file, you send a specific key-sequence to XMonad (Alt-q is the default), and XMonad serializes it's state into a string, compiles the new config file, and then replaces itself with the new instance, handing over it's state. No mutable-state-in-IO trickery necessary. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How easy is it to hire Haskell programmers
> A better test might be if they really understood Applicative and > Traversable, or if they knew how to use hsc2hs; Talk about unboxing and when > to apply strictness annotations, finger trees, stream fusion, purely > functional data structures or ways to implement memoization in a purely > functional setting, or how to abuse side effects to do so in a less pure > way. Those are the kinds of things you get exposed to through actually using > Haskell, rather than through reading a monad tutorial. Sonuds good. And please don't ask about specific GHC compiler flags. (I had to answer such questions once. Fortunately the other bits of the Haskell parts of the interview were more relevant.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why does `flip` cause function type so different ?
> Every question is welcome on haskell-cafe . The goal of > haskell-beginners is to encourage answers that are tailored to > beginners, i.e. no scary existential multi-parameter category theory > type class monads there. :) Do you get warm fuzzy existential multi-parameter category theory type class things there? Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange typing?
Hi Ozgur, Perhaps you can have a look at what discussion there was about non-empty lists. Seems (slightly) related to me. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] STM Skip list implementation
Hi Peter, Interesting. Your skip lists do not need re-balancing, but they do destructive updates. I wonder which factor outweighs the other in practise. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hackaton: A roof to stay
> im planing on going to the hackaton, but the prices in Zurich are unusually > high for my tight budget, so i was wondering if there is anyone here that > lives there and would allow me to sleep on their couch or on the floor > during the hackaton. > Is there ? Just a suggestion: Have you tried one of the couch surfing sites on the web? Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell course, training
>> I think I've reached the point where I need some tutoring, so provided >> I've got money for travel and course fees, and time, where do I get it? I'm >> not a student so some courses aren't available to me. > > How about visiting our Haskell meeting in Leipzig, June 4th? Which I can only recommend! It has been nice last year. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Books for "advanced" Haskell
> A shining example are Dan Piponis blog posts. Not his fault, mind. All I see > is that there is something powerful. I also notice that the big brains > construct monads in many different ways and thus giving them entirely > different capabilities. An example of this is some techniques turn CBV to > CBN or CBL while other techniques null this. What are CBV, CBN and CBL? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A small oversight
> Also, constructions like > > sortBy (compare `on` foo) > > must surely be very common. Just as a data point: I use constructions like the above very often. (Perhaps someone more enlightened than me can point out the connection to arrows?) Data.Function.on is surprisingly useful in some other contexts, too. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
> But, isn't it the case that you can transform any linear inequality into a > linear equality and a slack (or excess) variable? That's actually what you > *need to do* to turn the problem into the canonical form, so that simplex > can handle it. Yes. The simplex is usually implemented in this form. If you just want to play around with linear programming in Haskell, you could try write an FFI wrapper aruond SCIP (http://scip.zib.de/). (Though the licence of scip is probably not what you want. But there are other solvers available, too.) The domain specific language (and compiler of the same name) ZIMPL may be worth a look for linear programming. (http://zimpl.zib.de/) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
The trick is to use only non-negative variables for the equations. (That's considered OK in linear programming. Though you may consider it cheating.) By the way, linear programming over rational numbers is in P. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linear programming in Haskell
> As far as I can see, you'd use that for systems of linear equalities, but > for systems of linear inequalities with a linear objective function, it's > not suitable. I may be wrong though :) There's a linear [1] reduction from one problem to the other and vice versa. [1] The transformation itself is a linear function, and it takes O(n) time, too. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: How many "Haskell Engineer I/II/III"s are there?
> It might be big for SoC but perhaps there's some well-defined subset, > like fix some blocking issue? Good idea. By the way, do all SoC projects have to be single-contributor projects, or could someone get together with a friend and work together on a somewhat larger project? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: How many "Haskell Engineer I/II/III"s are there?
Implementing an alternative RTS for GHC seems like a viable Google Summer of Code project to me. What do you think? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If monads are single/linearly threaded, doesn't that reduce parallelism?
Perhaps if you search for Abelian Monad or so, you will find interesting things in the category theory literature. Some of them may be transplantable to Haskell --- but you probably don't want a completely commutative structure. Arrows seem to express the dependencies between operations more fine-grained than the sequencing that Monads require. (I meant to look into arrows for ages..) Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How many "Haskell Engineer I/II/III"s are there?
> I think this has a lot to do with the fact that > web programming is very much a "let's go shopping" kind of > discipline -- no point in troubling oneself over correctness > when the users haven't weighed in on the worth of your site. > Of course this attitude leads to a long maintenance phase of > Crazy Stuff®, like writing a PHP compiler; but by then you > have piles of money to throw at the problem! Such is the > theory, anyways. Or have sold your startup to some other company. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How many "Haskell Engineer I/II/III"s are there?
I used Haskell for some Research & Development work at Deutsche Bahn, earlier. (But my program was not integrated with their other systems.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Navigating Graphs
Using something like zippers it is easy to navigate an acyclic graph in O(1) operations per arc you follow. Inspired by Chris Okasaki's work on queues I wondered if there is a similar approach to navigating cyclic graphs. If the graph you are navigating is static (i.e. does not have to support addition or removal of vertices in any reasonable amount of time), I guess you can get away with "Tying the know" (http://www.haskell.org/haskellwiki/Tying_the_Knot). But is there a technique that allows navigation, insertion and removal at focus in (at least amortised) O(1) operations each? As a generalisation being able to have multiple points of focus (in an acyclic graph for a start) would also be interesting. Any thoughts? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] If monads are single/linearly threaded, doesn't that reduce parallelism?
Monads are not commutative. A structure that would tell the compiler that it's commutative, would give it more leeway for optimization (and parallel execution). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
Dear Dušan, You can also find an algorithm in everyone's favourite book in combinatorial logic "To Mock a Mockingbird" (http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird). Cheers, Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Job opportunities at Citrix Systems (Cambridge, UK)
Hi folks, I have recently started working for Citrix in Cambridge. We are working on the open source software in Ocaml. Admittedly Ocaml is only a second best compared to Haskell ;o) and I hope my post does not count as too off-topic here. But Ocaml is still a decent language. My experience was primarily with Haskell and I only started working with Ocaml in earnest at Citrix. (So I hope that showing a way to transplant Haskell skills to the real world --- via the roundabout route of Ocaml --- justifies my posting.) So --- if you are looking for a job in Cambridge that involves functional programming, free software [1] and free beer [2], please feel free to drop me a line. I have included our original advert to the Ocaml mailing list for those who want more information first. Cheers, Matthias. [1] As in free speech. LGPL [2] As in free beer. We also get other perks, like snacks and a pool table. -- Forwarded message -- From: Dave Scott Date: 2010/1/18 Subject: [Caml-list] [jobs] Citrix Systems (Cambridge, UK) To: "caml-l...@yquem.inria.fr" , "ocaml-j...@inria.fr" Dear fellow OCaml users, Summary: We (Citrix Systems) are looking for OCaml programmers to join our team in Cambridge, UK. We use OCaml extensively in the "xapi tool-stack": the control-plane used in the Xen Cloud Platform[1] on which the widely used XenServer server virtualisation product[2] is based. XCP aims to provide a complete open-source cloud infrastructure platform with a powerful management stack based on standards-based APIs, support for multi-tenancy, SLA guarantees and detailed metrics for consumption based charging. We are looking to recruit top-class engineers to work on the tool-stack; applicants must have a good knowledge of data structures and algorithms, experience of programming in the context of large systems and general aesthetic good taste when it comes to code and architecture. Our code base is significant and varied: over 130,000 lines of OCaml, solving problems ranging from the low-level (Xen hypercalls) to the high-level (resource pool management), to the compiler-driven (generating language bindings for our Xen datamodel). Our ideal candidate will have: * significant experience of applications programming in high-level languages (such as OCaml :-) * an aptitude for implementing (and reasoning about) complex concurrent, distributed systems * the skills required to contribute to both the architectural design and day-to-day development of a large code-base * strong communication skills and problem solving ability * a determination to deliver great products that perform brilliantly and meet our customers' needs So if you want to tackle interesting and challenging programming problems and contribute to an innovative, fast-growing product that is already used by tens of thousands of customers across the world, please don't hesitate to send me your CV. [1] http://www.xen.org/products/cloudxen.html [2] http://www.citrix.com/English/ps2/products/feature.asp?contentID=1686939 Thanks, -- Dave Scott ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Typed Configuration Files
Hi Sebastian, You might also want to look at how xmonad handles it's configuration. Basically the configuration file is the main-file that produces the executable and takes in the rest of xmonad as a library. This works out quite well, but you need a compiler to update the configuration. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Language simplicity
> All Lisps have "special forms" which are evaluated uniquely and differently > from function application and are therefore reserved words by another name. > For example, Clojure has def, if, do, let, var, quote, fn, loop, recur, > throw, try, monitor-enter, monitor-exit, dot, new and set!. Yes, but the special forms are not distinguishable from user defined macros --- and some Lisp-implemantations special forms are another implementations macros. E.g. you can choose to make `if' a macro that expands to `cond' or vice versa. I do not know whether you are allowed to shadow the name of special-forms. > If you count reserved tokens, I guess Lisp reserves parentheses and > whitespace? Not if you are using Common Lisp. There you can install reader-macros that act on characters in the input-stream. (Most macros act on stuff in the already parsed syntrax tree.) Forth is also a remarkably flexible language in this regard. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] General Advice Needed ..
Hi, it may be a bit too late for you, but in general working through Smullyan's "To Mock a Mockingbird" (http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird) may help in coming to grips with some of the theory (and intuition) behind functional programming. The "Real World Haskell" book is also a good choice, completely orthogonal to Smullyan's book, and much more practical. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell for Physicists
> _So my strong opinion that solution is only DSL not EDSL_ Why do you think they will learn your DSL, if they don't learn any other language? And if your DSL includes general purpose stuff, like functions, control structures, data structures, you'll re-invent the wheel. Probably porly. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] I miss OO
> When OO is about constructing a "machine" and talking about objects, > and FP is about making little algebraic languages, what would C or > Pascal be like? In these languages, you don't think about objects, but > you don't think about an algebra either? It's been a very long time > since I worked with these languages, but as far as I recall, I started > thinking about data structures and procedures operating on these data > structures, which sounds a look like making ADTs and > functions/operations on these... So this sounds odd, because it would > mean that C and Pascal are in a sense closer to FP than OO is? You are working with state all the time in C and Pascal. Perhaps a C with a garbage collector would be closer to FP, because you could construct new structures all the time without worrying about memory leaks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] I miss OO
> It would be fantastic to have a little practical real-world challenge > (like building a simple music system, or a simple multi-channel sound > mixer), and work this out in an imperative language, an > object-oriented language, a functional language, and maybe other > languages too, like logic languages or constraint languages (does the > latter exist?) There are some constraint languages. But I do not know whether they are general purpose (or even Turing complete). I have used ZIMPL, which is a language for specifying mixed integer linear optimization problems (which is somewhat related to constraint programming). Though it would not be useful for a music system. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Card games
Hi Tom, Did you make any progress on your Dominion quest? I guess you could start by modeling `Big Money' and add the other cards (and interaction) from there. Also I guess there is a common baseline of things that are inherent in a lot of card games --- mechanics that cards support: Shuffling, having two sides, hiding one of two sides, picking a random card from a subset (or at least one where you can only see one side), placing cards in constellations on a table (with one side up). I guess with a bit of type system trickery you can even make sure that strategies don't look at the sides of the cards they are not supposed to look at --- without having to do any other information hiding like only providing access by getter functions. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Ord k => Data.Set.Set k -> (k->v) -> Data.Map.Map k v
I feel that Data.Set and Data.Map should be working together more closely. For example you can already get the keyset of a Map, but the `other way' is not built-in. I mean a function with a signature like Ord k => Data.Set.Set k -> (k->v) -> Data.Map.Map k v You can implement it in O(n): > assoc :: (a->b) -> [a] -> [(a,b)] > assoc f = map (\x -> (x, f x)) > mapToMap :: Ord k => (k -> v) -> Data.Set.Set k -> Data.Map.Map k v > mapToMap f = Data.Map.fromAscList . assoc f . Data.Set.toAscList The name assoc alludes to the assoc-lists of Lisp. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Card games
Hi Felipe, Interesting idea. But I guess you should clarify what kind of card games you want to support. E.g, a DSL for trick taking games like Bridge, Skat or Doppelkopf might be different from one that's good for Canasta or Rummy. Or do you aim at Solitaire? I'd suggest starting with a very small scope of the domain for a very first version. Good luck writing a `solver' for Doppelkopf! Cheers, Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Simple quirk in behavior of `mod`
> Round-to-even means x.5 gets rounded to x if x is even and x+1 if x is > odd. This is sometimes known as banker's rounding. OK. That's slightly unusual indeed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Simple quirk in behavior of `mod`
> Couldn't the same be said for round-to-even, instead of rounding down > like every other language? I doubt any beginners have ever expected > it, but it's probably better. What do you mean with round-to-even? For rounding down there's floor. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
> What is the use case(s) for this function? I often want to take one more element than takeWhile does, or only start checking the predicate after taking the first element for sure. Or both. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generalizing takeWhile
Thanks to Jason and Felipe. I'll try that approach. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Generalizing takeWhile
I need to take some elements from the front of a list. However the criteria are somewhat complex. > walk f [] = [] > walk f (x:xs) = case f x > of Just g -> x : walk g xs >Nothing -> [] For each item the `predicate' f either returns Nothing, when it thinks we should not take any more elements, or return Just another `predicate' to apply to the next element. However the type system does not like my function. How can I mollify it? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] can there be (hash-table using) O(n) version of this (I think currently) n log n algo?
However you can use the wider idea of hashing: A nesting of two finite maps. One fast, but approximative map. And one slow, but exact map. The quintessential example is an array indexed with some hash function for the first map. And linked lists of (key,value) pairs as the latter. In Haskell you might want to use IntMap and a the mentioned list of pairs (combined with the lookup functions from Data.List). Of course you need to supply a function to hash your keys to Int for the IntMap. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Plot data reconstruction reading pixel colors from image files
If you don't find anything more specific, I suggest taking a look at Data.Binary and reading a simple format like BMP or so. (You can convert your file to BMP with an external program before.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
I tried using your original code and stuffing it into a profiler. But all I get is a triangle of linearly increasing resource usage, and then it breaks for lack of stack. I guess I am just to ignorant about retainer profiling and such stuff. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] laziness blowup exercise
Thomas, if you did no know, where to look for `lazy-memory-hole', say in your first example, how would you go about solving that puzzle systematically with a Profiler (or other tools)? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Jane Street
If one of you knows something about working at Jane Street, I'd be happy to have exchange some mails. I am considering applying there. Thanks! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Python vs Haskell in tying the knot
> BTW, after a -O2 compilation, fib' is apparently as fast a fib. The compiler is your friend. :o) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Debugging methods for haskell
> By the way, does Hat - the Haskell Tracer? Please append: "still work". ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Debugging methods for haskell
By the way, does Hat - the Haskell Tracer? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell Zippers on Wikibooks: teasing! :)
> doesn't make much sense to me yet, although I suspect I can read the mu as a > lambda on types? Not really. The mu has more to do with recursion. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] RE: Haskell as a first language?
> It maybe be that Haskell is harder to learn as your *second* language > because you have to unlearn things. Especially if your first language > was something like C or Python. Python is not too bad. You can nearly use it a as a strict functional programming language. While this is not the idiomatic style to use python in, it sure eases transition to a real functional language (compared to say, C). Also Python has no pointers, but does have garbage collection. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] What to say about Haskell?
Dear Gergely, Okasaki's "Purely Functional Data Structures" is a treasure trove of interesting things to demonstrate Haskell on. Especially the data structures based on numerical representations (skew binary numbers and so on) appealed to my mathematical side. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] haskell.org: what can be improved causing what efforts?
>> Nice idea. Perhaps use a merge sort, because that is actually useful, >> because it does not degenerate for large lists. > > Great idea if we want to keep Haskell community compact :))) Or stay with quicksort --- which is treesort. :o) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] haskell.org: what can be improved causing what efforts?
> I like the quicksort example at > http://www.haskell.org/haskellwiki/Introduction very much; it shows how much > time you can save when you use Haskell. Nice idea. Perhaps use a merge sort, because that is actually useful, because it does not degenerate for large lists. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] haskell.org: what can be improved causing what efforts?
> code snippet: no hello world please. That's not a way to judge a > language! But: a random haskell one line snippet with explanation would > be cool. Perhaps a solution to a problem like the ones you can find on Project Euler (http://projecteuler.net/index.php?section=problems). Of course you can't take an actual problem from Project Euler, because they do not like solutions to be posted in the wild. But you can get your inspiration from there. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: excercise - a completely lazy sorting algorithm
Thanks. I heard about the hylo-, ana- and catamorphisms before, but never explicitly used them. Time to get started. And yet another question: One can get the median in deterministic linear time. For quicksort choosing the median as pivot keeps the O(n log n) average running time and brings down the expected worst case, too. Do you know of a (natural) way to combine selecting the median and doing the quicksort, so that you don't compare unnecessarily? The way to de-randomize quickselect is to calculate medians of medians. I.e. solve the problem for smaller instances first. I suspect if we follow this strategy with the reified quicksort call-trees, the de-randomized quicksort will look a lot like mergesort. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: excercise - a completely lazy sorting algorithm
Interesting. Can you make the definition of quicksort non-recursive, too? Perhaps with help of a bootstrapping combinator like the one implicit in the approach I have given earlier? > treeSort = bootstrap partitionOnMedian > bootstrap f = Fix . helper . f > where helper = fmap (Fix . helper . f) > partitionOnMedian :: forall a. (Ord a) => (S.Seq a) -> BTreeRaw a (S.Seq a) Extra points if you can give 'bootstrap' or an equivalent in terms of existing Haskell combinators. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell Platform on Ubuntu
> One problem I see is the binary-only distribution of packages. This makes > cabal-install incompatible with most distributions except, maybe, gentoo. > The automation process would have to run through hackageDB tracking > dependencies and compiling each needed library. Pretty hard stuff... Yes. The sanest approach for any distribution would seem to install are bare bones ghc + cabal (cabal install) and let the cabal package system do the hard work directly. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing Compiler for the ICFP 09 contest's VM
Since I have two readers now, I guess I'll have to start blogging. :o) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell Platform on Ubuntu
> Karmic (9.10) will have GHC 6.10.3, possibly 6.10.4. It currently spots 6.10.3, in the alpha release I run here. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Las Vegas algorithms in Haskell
>> What I wondered was, if one could hid the random plumbing in some data >> structure, like the state monad, but less linear. > > This problem cries for a State monad solution - but you don't need to > do it yourself, there's already a Random monad defined for you. Yes, but I only need the random values inside splitOnMedia. The rest is just non-linear plumbing. We do not know beforehand how many random values a branch quicksort will consume --- neither do we ware about the state of the random generator at the end. Do you consider the RandomMonad the best fit? Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: excercise - a completely lazy sorting algorithm
> So, a tree like Matthias implements it is the way to go. Basically, it > reifies the recursive calls of quicksort as a lazy data struture which > can be evaluated piecemeal. Yes. I wonder if it is possible to use a standard (randomized quicksort) and employ some type class magic (like continuations) to make the reification [1] transparent to the code. Matthias. [1] I reified reify. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Implementing Las Vegas algorithms in Haskell
Dear Hector, Yes, I thought of a similar scheme. Say we want to implemented randomized quicksort. Passing a list of random numbers would destroy laziness and linearise the algorithm --- because the right recursion branch would need to know at least how many random numbers where consumed by the left branch. So for the example of quicksort I thought of passing an infinite binary tree of random numbers. > data RandomTree v = Node (RandomTree v) v (RandomTree v) > splitOnMedian :: Ord a => SomeRandomType -> [a] -> ([a],a,[a]) > quicksort :: RandomTree (SomeRandomType) -> [a] -> [a] > quicksort _ [] = [] > quicksort _ [a] = [a] > quicksort (Node left here right) s > = let (l,median,r) = splitOnMedian here s > in quicksort left l ++ median ++ quicksort right r Of course one would need a special data structure for each recursion scheme with this approach. For a number of algorithms something like the rose trees of Data.Tree should work, though. What I wondered was, if one could hid the random plumbing in some data structure, like the state monad, but less linear. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Implementing Las Vegas algorithms in Haskell
A Las Vegas algorithm, like randomized quicksort, uses a source of randomness to make certain decisions. However its output is unaffected by the randomness. So a function > f :: RandomGen g => g -> a -> b implementing a Las-Vegas-Algorithm 'looks' like a pure function, ignoring its first argument and depending solely on its second argument. What is an idiomatic way to implement such a function? I believe, Monads are too linear and strict. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
The "sorted array of bags of unsorted input" is a nice idea. However, you have to use the data structure in a single-threaded [1] fashion to obtain the claimed bounds. Here's a pure solution that uses amortization and laziness. > import qualified Data.Sequence as S > import Data.Sequence ((><)) > import Data.Foldable > import Data.Monoid Suppose we have a function to find the the median of a list, and partition it into three sublists: Smaller than the median, equal to the media, larger than the median. That function should run in linear time. > partitionOnMedian :: forall a. (Ord a) => (S.Seq a) -> BTreeRaw a (S.Seq a) where the following data structure holds the sublists and some bookkeeping information: > data BTreeRaw a m = Leaf > | Node {cmp::(a->Ordering) > , lN :: Int > , less::m > , eq :: (S.Seq a) > , gN :: Int > , greater::m > } where 'lN' and 'gN' are the length of 'less' and 'greater'. We can make BTreeRaw a functor: > instance Functor (BTreeRaw a) where > fmap f Leaf = Leaf > fmap f (Node c lN l e gN g) = Node c lN (f l) e gN (f g) Now using a fixed-point construction we can bootstrap a sorting algorithm from partitionOnMedian: > data Fix m = Fix {unfix :: (m (Fix m))} > type BTree a = Fix (BTreeRaw a) > treeSort :: forall a. (Ord a) => S.Seq a -> BTree a > treeSort = Fix . helper . partitionOnMedian > where helper = fmap (Fix . helper . partitionOnMedian) Now treeSort produces the thunk of a balanced binary search tree. Of course we can get a sorted list out of it (forcing the whole structure): > flatten :: BTree a -> S.Seq a > flatten (Fix Leaf) = S.empty > flatten (Fix (Node _ lN l e gN g)) = flatten l >< e >< flatten g > mySort = flatten . treeSort But we can also get elements efficently, forcing only a linear amount of comparisions in the worst case: > index :: BTree a -> Int -> a > index (Fix Leaf) _ = error "tried to get an element of Leaf" > index (Fix (Node lN l e gN g)) i | i < lN > = index l i > | i - lN < S.length e > = S.index e (i-lN) > | i - lN - S.length e < gN > = index g (i - lN - S.length e) > | i - lN - S.length e - gN >= 0 > = error "index out of bounds" Although we do have to force comparisions only once every time we touch the same element in the tree, we do still have to traverse the tree (in logarithmic time). If you want linear time access on first touch of an element and constant time access afterwards us toArray: > toArray :: (IA.IArray a t) => Fix (BTreeRaw t) -> a Int t > toArray tree = IA.listArray (0,maxI) (map (index tree) [0..maxI]) > where size (Fix Leaf) = 0 > size (Fix (Node lN _ e gN _)) = lN + S.length e + gN > maxI = size tree - 1 [1] Single-Threaded in the sense of Okasaki's use of the word. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
> It seems to me, that you just need a selection algorithm which works in > O(n * k) time for k arbitrary elements. If you combine O(n*k) selection > algorithm with any O(n * lg n) sort, you furfil your time constrain. I guess, we also want the list to be sorted in O(1) after having selected every element. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
> If someone can translate my algorithm into a non-side-effecting one, > I'd appreciate it, but I think that like disjoint set/union, this is > probably inherently side-effecting. Yes, yes, we could use functional > arrays, but short of that I don't see a way to avoid side effects to > take care of my amortized work. I am just working on a side-effect-free version. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] excercise - a completely lazy sorting algorithm
Interesting problem. I have been toying with the same problem for some time. To solve the problem in theory, I'd concentrate on getting the number of comparisons into the required O(n) resp. O(n log n) ranges. Afterwards we can think about building the infrastructure to keep the number of all operations (book keeping..) in those bounds, too. Anyway, I'll give a solution to the problem using a randomized quicksort, soon. Later we can replace the randomized pivote-picking with a deteministic linear-median algorithm. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] simple state monad exercises? (besides labeling trees)
> Can someone give some simple common scenarios where the state monad is > useful, besides labeling trees? Emulating the VM given in this years ICFP programming contest was also a good application of the state monad. Of course you interprate much simpler language imperative languages, too. (However that might feel a bit forced as an exercise.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Optimizing Compiler for the ICFP 09 contest's VM
The byte code for the virtual machine of this years ICFP specified a language with single assignment per simulation step. Interestingly most memory locations get overwritten each simulation step before they are read. That means, those locations don't have to be remember between steps. Also locations that never get overwritten (e.g. location associated with Noops), are constant. Thus the variables state of the simulation is orders of magnitude smaller than the naive 2^16 * 32 bit + 1 bit. I wrote a small program that analyses the dataflow of a byte code program (and initial memory setup) for the VM. After analyzing my program emits Haskell code to run the given byte code. If anyboby is interested, I can document my program and put it online somewhere. I also made pretty graphs of the dataflow with graphviz. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Cont, ContT and IO() - Code on hpaste
P.P.S. Strange it does not seem to work with the paste. So here comes the solution by mail: module Consolidator.BusinessLogic.ConflictsResolved (consolidateDuplicates) where import System.FilePath import System.Directory import Control.Monad (filterM) import Control.Exception (throwIO) import System.Environment import Data.Maybe import Control.Monad import Control.Monad.Trans newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) } instance (Monad m) => Monad (MaybeT m) where (>>=) tmb_v f = MaybeT (runMaybeT tmb_v >>= \b_v -> case b_v of Nothing -> return Nothing Just v -> runMaybeT $ f v ) return = MaybeT . return . return instance MonadTrans MaybeT where lift mon = MaybeT (mon >>= return . Just) abort :: String -> MaybeT IO a abort reason = do lift . putStrLn $ reason MaybeT (return Nothing) {- The traversal is one directory deep only. I try to find out if every immediate subdirectory contains exactly one "*.gdr" file, and collect the path names in a list, sgls. Afterwards I append the contents of each such file to another file. I want to abort the whole process as soon as I encounter a directory that does not include exactly one *.gdr file. Currently I'm throwing exceptions but I'd prefer to rewrite this code to use continuations. -} consolidateDuplicates :: FilePath -> MaybeT IO () consolidateDuplicates fp = do dirs <- lift (getDirectoryContents fp) recs <- lift (filterM doesDirectoryExist $ map (fp ) $ filter (not . flip elem [".", ".."]) dirs) sgls <- mapM checkForSingle recs let cpy = fp "Korrigiert.gdr" lift (copyFile (fp "Konsolidiert.gdr") cpy) lift (mapM_ (\sgl -> do str <- readFile sgl appendFile cpy str) sgls) checkForSingle :: FilePath -> MaybeT IO FilePath checkForSingle fp = do cnt <- lift (getDirectoryContents fp) let fltr = filter ((== ".gdr") . takeExtension) case fltr cnt of [] -> abort ("The directory " ++ fp ++ " is empty") [f] -> return (fp f) _ -> abort ("There is more than one file in the directory " ++ fp) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Cont, ContT and IO() - Code on hpaste
P.S. See http://en.wikibooks.org/wiki/Haskell/Monad_transformers for some documentation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Cont, ContT and IO() - Code on hpaste
Hi Günther, here is a solution with the Maybe Monad: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=6515#a6515 Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cont, ContT and IO()
>> process' = foldl op True files >> op True file = doit file >> op False _ = False Please pardon me. 'doit' should surely be able to do some IO: > import Data.Foldable > import System.IO > process' = foldlM op True files > op True file = doit file > op False _ = return False were DoIt has the type FilePath -> IO Bool ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cont, ContT and IO()
> process [] = return () > process (file:files) = do x <- doit file > if x>0 then process files > else return () Or use a fold: > process' = foldl op True files > op True file = doit file > op False _ = False ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
> you will find it there but it's written in German. Yes. But at least there's an English abstract. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List spine traversal
> As a side note, (allowing seq and unsafePerformIO if necessary) is it > possible to implement a map that preserves cycles (instead of > transparently replacing them with infinite copies? Not horribly > useful, but would be quite cute. Baltasar Trancon y Widemann gave a talk on a generalized version of this problem at HaL4. Short answer: The problem is tractable in theory, but you need heavy math. Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Another question about unsafePerformIO
> Adding 'unsafePerformIO' will work, but a better idea might be to > understand why your solver has IO in its type signature. Is this because > of FFI calls? You can remove IO in FFI calls if they are free from side > effects as well. My solver has IO in the type signature, because I said so. :o) The solve function is defined like this: > solve :: Constraints -> IOMayfail Solution > solve constraints = do { solString <- scip (genZimpl constraints); >parseSol nfnrs solString;} > scip :: String -> IOMayfail String > scip zimplCode = do {lift $ writeFileAtomic zplFile zimplCode; > exitCode <- lift $ system (command zplFile solFile); > case exitCode of ExitSuccess -> lift (readFile solFile) > ExitFailure n -> fail ("Calling Scip > failed with code "++ show n ++".\n");} > command inFile outFile = "./scip -c 'read \"" ++ inFile ++"\"' -c 'optimize' " > ++"-c 'write solution \""++outFile++"\"' -c 'quit'" (I added {}; because I some mail clients use variable width fonts and mess up layout. Eg mine does.) The solver SCIP also offers a FFI interface. But I was too lazy to use that, yet. So I use a temp-file (which should really use openTempFile instead of a fixed name) for communication. So because of my lazyness there are still things in it that look like side-effects, but they are not so in principal. (Also I am the only user of my code, so I can get away with deferring true FFI.) Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Another question about unsafePerformIO
I have a program that optimizes train schedules. It employs an external solver for Integer Linear Programs. The solve function has the following type: > solve :: Constraints -> IO (Maybe Solution) And this works. However, my external solver also behaves like a pure function from input to output. I wonder whether this guarantee should be reflected in the type system. I'd also appreciate if the compiler would be able to eliminate some calls to the solver. > solvePure :: Constraints -> Maybe Solution > solvePure = unsafePerformIO . solve Is this a good idea? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] combining monads with IO
Thanks. Can I add something like fail? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] combining monads with IO
By the way, how would one write the following with Monad Transformers? > newtype IOMayfail a = IOMayfail (IO (Maybe a)) > instance Monad IOMayfail where > return = IOMayfail . return . return > (>>=) a f = IOMayfail (bind (run a) (run . f)) > fail s = trace s (IOMayfail $ return Nothing) > run :: IOMayfail a -> IO (Maybe a) > run (IOMayfail a) = a > bind :: IO (Maybe a) -> (a -> IO (Maybe b)) -> IO (Maybe b) > bind a f = do r <- a > case r of Nothing -> return Nothing > Just r' -> f r' > Lift :: IO a -> IOMayfail a > lift f = IOMayfail (f >>= return . return) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] slow code
> Still, a fast and general way to output primitive data types would be > quite welcome. Naive question: Can't we just ask C to do it for us? (With a foreign function call.) Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Purely logical programming language
>>> Mercury also has type classes and other Haskellisms, so if you're >>> interested in "doing Prolog the Haskell way", you should definitely >>> have a look at it. >> >> I have to admit that I am not very familiar with Mercury. But if you are >> looking for "doing Prolog the Haskell way" you can also have a >> look at Curry. Curry is a lazy functional logic programming >> language that has a Haskell like syntax (http://www.curry-language.org/). > > You forgot to mention, that you will give a talk about Curry soon, where > Matthias might want to attend: > http://iba-cg.de/hal4.html Indeed. Studying in Magdeburg, I already heard about that workshop and considered attending, but I did not read the agenda in detail. Now I'll definitely attend. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Purely logical programming language
> Mercury also has type classes and other Haskellisms, so if you're > interested in "doing Prolog the Haskell way", you should definitely > have a look at it. Thanks. I'll have a look. (I also just found Mercury on my own: After I posed my original question, I tried another web search, and found what I was looking for. I haven't read the articles, yet, so I am grateful for your summary.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Purely logical programming language
There are a number of ways to marry purely functional programming languages with IO. To name just two possibilities: Clean uses linear types, threading exactly one "World" through functions, Haskell uses Monads. The model in Prolog, however, looks more like the model used in most strict functional languages. It uses impure predicates to affect the outside world. Do you know of any attempt to do for logic programming what Monads did for functional programming? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The Computer Language Benchmarks Game: pidigits
Hi, By the way: Would it be considered good style to include QuickTest properties into the pidigit submission? Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ICFP Participation
> Registration will be open soon. Thanks. (I could have written an Experience Report about how I am using Haskell at Deutsche Bahn, but that deadlines had already passed.) Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ICFP Participation
Hello, Please pardon my naive question: Is there a way to sign on for ICFP 09? The homepage (http://www.cs.nott.ac.uk/~gmh/icfp09.html) only seems to mention how to submit papers. Is there a way to attend as a mere participant? Thanks, Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pretty printing a tree
Hello, Or --- if you just want pretty trees and you are not confined to the command line: You can generate GraphViz code and use that program to draw your tree in PostScript. (There is also a GraphViz-package, but generating the code yourself is easy.) Matthias. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe