September 2008 - Haskell-Cafe

Red-Blue Stack
by Matthew Eastman 29 Sep '08

29 Sep '08

Hey guys, This is probably more of a question about functional programming than it is about Haskell, but hopefully you can help me out. I'm new to thinking about things in a functional way so I'm not sure what the best way to do some things are. I'm in a data structures course right now, and the assignments for the course are done in Java. I figured it'd be fun to try and implement them in Haskell as well. The part of the assignment I'm working on is to implement a RedBlueStack, a stack where you can push items in as either Red or Blue. You can pop Red and Blue items individually, but the stack has to keep track of the overall order of items. i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red, Red, Blue] All push and pop operations on the stack have to be done in O(1) time. It was easy to do in Java since you can just keep track of everything with a few pointers, but it took a while to get the Haskell version working. Maybe I'm just not used to the functional way of doing things. I originally had this: data RBSItem a = Red a | Blue a data RedBlueStack a = RBS { red :: [RBSItem a], blue :: [RBSItem a], overall :: [RBSItem a] } But there was no way to keep popping in O(1) time because I would have to walk through the overall list when removing items. I eventually came up with: data ShowColour = PlusRed | MinusRed | PlusBlue | MinusBlue data RedBlueStack a = RBS { red :: [a], blue :: [a], order :: [ShowColour] } popRed :: RedBlueStack a -> RedBlueStack a popRed (RBS (r:rs) b o) = RBS rs b (MinusRed : o) popRed rbs@(RBS [] _ _) = rbs -- As an aside here, would it be better to put "popRed = id" for the catch-all in popRed instead of what I have? -- I don't know proper Haskell coding style yet. remUseless :: [ShowColour] -> [ShowColour] remUseless order@(x:xs) | x == MinusRed = remShowColour PlusRed xs | x == MinusBlue = remShowColour PlusBlue xs | otherwise = order where remShowColour r (c:cs) | c == r = cs | otherwise = c : remShowColour r cs remShowColour _ [] = error "Incorrect Stack Order" So instead of walking through the overall list, I just have to add a MinusRed or MinusBlue to the order list. This makes the pop and push functions operate in O(1) time, but it seems a bit excessive, because whenever the overall order of the stack is needed (e.g. printing the stack) I need to clean up the order list. I was just wondering whether this is the best way to implement something like this, keeping track of changes made instead of making the changes. If anyone has any ideas for other ways of implementing this I'd love to see them. I didn't take into account that Haskell is lazy. Will that have any effect on the running time? Probably not for a simple program like this, but for larger ones and more complex data structures and algorithms, I'm guessing it would? Thanks, Matt

11 19

'par' - why has it the type a -> b -> b ?
by Henning Thielemann 29 Sep '08

29 Sep '08

What is the reason for implementing parallelism with 'par :: a -> b -> b'? Analogy to 'seq'? I thought parallelism would be introduced most naturally by a function which does two computations in parallel and puts together their results after completion. Say > par2 :: (a -> b -> c) -> (a -> b -> c) to be used like > par2 (+) expensiveComputationA expensiveComputationB I assume that par2 can be implemented this way: > par2 f x y = > f x (par x y) ?

6 11

announcing darcs 2.1.0pre2
by Eric Kow 29 Sep '08

29 Sep '08

Hi everybody, The second pre-release of darcs 2.1 (formerly known as 2.0.3) is now available at http://darcs.net/darcs-2.1.0pre2.tar.gz We have increased the version number since the last pre-release because we are adopting an important new behaviour: The darcs initialize command now creates darcs-2 format repositories by default This will help new repositories to benefit from the improved handling of duplicate patches and to avoid the exponential time conflicts problem. Upcoming release schedule ------------------------- 2008-10-03: darcs 2.1.0pre3 2008-10-10: darcs 2.1.0 Work remaining -------------- * http://bugs.darcs.net/issue971 (Petr Ročkai) When using hashed or repositories, allow darcs check to deal with filenames that differ only in case when run on a case-insensitive filesystem. Petr has done 90% of the work for this -- he has implemented this for darcs repair -- so this shall largely be a question of refactoring. * http://bugs.darcs.net/issue1003 Allow darcs-transfer mode to deal with a specific set of missing files (namely _darcs/format) so that users can benefit from ssh connection sharing even if the remote end uses an old-fashioned repository. In the meantime, a simple workaround is to touch the _darcs/format file in the remote repoistory * http://bugs.darcs.net/issue1078 Fix a corner case in paths handling that makes darcs overly cautious if the repository is a symbolic link * http://bugs.darcs.net/issue1026 Improve the error messages for 'bug in get_extra' errors, which can happen if darcs is fooled into thinking that two patches are the same. Changes since the last pre-release ---------------------------------- * User Experience: Do not allow users to add files to a darcs repository if their filenames would be considered invalid under Windows. This can be overridden with the --reserved-ok flag (issue53, Eric Kow) * Bug Fix: Do not leave behind a half-gotten directory if darcs get fails (issue1041, Vlad Dogaru, David Roundy) * User Experience: notice when you are trying to pull from a seemingly unrelated repository, that is one with a sufficiently different history. This can be overridden with the --allow-unrelated-repos flag (Dmitry Kurochkin, David Roundy) * Bug Fix: Fix hang after a user input error (for example, EOF) (Judah Jacobson) * Quality Assurance: Improvements to documentation and online help (Simon Michael) -- Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow> PGP Key ID: 08AC04F9

2 1

Re: Haddock + Hoogle == Javadoc on steroids
by Simon Michael 29 Sep '08

29 Sep '08

Taking this to haskell-cafe.. http://joyful.com/repos/darcs-sm/api-doc is a mashup of haddock, hoogle and hscolour (and darcsweb, darcs-graph - see http://joyful.com/repos) It's rough but quite useful - a few minutes here gave me a much better understanding of the big picture of darcs code. By alternating shift & enter in the contents pane I could browse quickly through all modules. Improvement: one could do a lot of useful magic with javascript. But it would be more powerful to improve the tools, eg I'd like if haddock had frames/no-frames built in and hoogle could be made to work in either case. I haven't had time to work on this, currently I hard-code the target in hoogle and munge the haddock output slightly (see recent patch in darcs-unstable). As you say it would be great to keep improving this area and baking it into our tools and infrastructure. Highly accessible and efficient docs and code browsing tools help a lot! On Sep 27, 2008, at 1:49 PM, Jason Dagit wrote: > Simon, > > I'm wondering if you could find a way to make it "trivial" for people using cabal to combine haddock and hoogle the way you have for darcs? > > Some ideas: > 1) Depend entirely on cabal for the auto setup of things > 2) Provide the framed interface on your webpage also has a layout in emacs (so people can use either web or emacs) > 3) Package it so that people just 'cabal install hoodock && hoddock ./src' and then they are done for 90% of cases > 4) Provide demos for darcs and something else large like GHC > > What do you think? If you need help with it, I'm sure there are tons of people on Haskell-Cafe that would really dig this and help you with it. > > Thanks, I love it! > Jason Thanks! -Simon

3 4

Re: [Haskell-cafe] Re: Version 0.4.3 of happs-tutorial is a HAppS job board, done in HAppS.
by Thomas Hartman 29 Sep '08

29 Sep '08

The executable needs the templates in the same directory to work correctly. Copy the happs-tutorial.tar.gz file from whereever cabal put it -- probably somewhere under .cabal if you're on linux. Untar it, cd into the directory, compile and run in there. Should work. I'll revise the tutorial instructions to make this clearer, thanks for the feedback. Thomas. 2008/9/29 Anton Tayanovskyy <anton.tayanovskyy(a)gmail.com>: > Hello Thomas, > > After doing > > sudo cabal install happs-tutorial > > I got HappS to build which is really a great improvement (about a year > ago I could not build HappS). It also installed happs-tutorial > executable. > > Now, the executable runs, but when I try to access the server over HTTP, I get: > > IO Error: Just "templates/base.st" -- does not exist > > Also, on my system I can't locate base.st nor hackInGhci.sh mentioned > in the online tutorial. Actually, I somehow fail to make sense of this > page: > > http://www.happstutorial.com/tutorial/run-tutorial-locally > > After the Cabal install, I'm lost. Maybe it's just me not seeing > something obvious, but in that case it still gives you a good sample > of your target audience, us webmonkeys :) > > If that helps, I'm on Fedora 9, GHC 8.3. > > Thanks. > > > --Anton > > > On Mon, Sep 29, 2008 at 5:25 PM, Thomas Hartman <tphyahoo(a)gmail.com> wrote: >> Someone on reddit pointed out that many firewalls block 5001 so I >> moved to vanilla http port 80. >> >> http://www.happstutorial.com >> >> >> >> 2008/9/29 Thomas Hartman <tphyahoo(a)gmail.com>: >>> Hello, world. >>> >>> In Version 4 of the ongoing self-demoing HAppS Tutorial, we implement >>> a HAppS job board using HAppS. >>> >>> demo: http://happstutorial.com:5001 >>> >>> install: sudo cabal install happs-tutorial >>> >>> darcs head: darcs get http://code.haskell.org/happs-tutorial >>> >>> There aren't any new lessons compared to the last release, but the >>> code is much cleaner, and... well... the web site actually does >>> something. >>> >>> Coming soon, lessons on form processing and HAppS State. >>> >>> Enjoy! >>> >>> Thomas. >>> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >

1 0

Re: [Haskell-cafe] Re: Haddock + Hoogle == Javadoc on steroids
by Sean Leather 29 Sep '08

29 Sep '08

> > Hi Neil.. my apologies, my nightly cron script clobbered it. Please try > now, same url: http://joyful.com/repos/darcs-sm/api-doc > It seems the "Contents" link embeds the outer frame into the right-hand side inner frame. Otherwise, it looks nice! Sean

1 0

The container problem
by Andrew Coppin 29 Sep '08

29 Sep '08

Take a look around you. Haskell provides several sorts of container. We have: Data.List Data.Set Data.Map Data.Hashtable Data.ByteString Data.Sequence Data.Array Data.Tree Data.IntSet Data.IntMap ... In other words, we have *a lot* of different data containers. And yet, each one provides its own unique API. To anybody used to OO languages, that sounds pretty crazy. In something like Java or Smalltalk or Eiffel, you have an abstract class that represents "container", and maybe a seperate one for "ordered container", and then concrete subclasses for each kind of container. Each one may add a few unique methods of its own, but basically all the containers have a uniform API, and you can write functions that work for any arbitrary [ordered] container. In Haskell, you can't do this. Why is that? To me, it seems that there are two sticking points: 1. Historical reasons. 2. The Haskell '98 type system. (1) is obviously solvable. (2) is harder. Some containers can contain *any* type of data. Haskell permits parametric polymorphism, so this is no problem: Data.List.map :: (a -> b) -> [a] -> [b] Other containers only support *one* type of data: Data.ByteString.Char8.map :: (Char -> Char) -> ByteString -> ByteString The type has a different kind, and the function parameter's type is more constrained. Yet still this poses no problem. However... now try writing a class that both of these functions could be methods of. Good luck with that, by the way... This is AFAIK also the reason why, e.g., Set is *not* an instance of Monad; you can't write a valid instance. The type checker won't have it. To ears accustomed to the OO way, all this makes it sound like Haskell's type system sucks. (Which is rich, because in half the OO languages, you can't write a type-safe container that works for arbitrary element types in the first place! Haskell is a Big Win here.) If I understand this correctly, to solve this problem you need either Functional Dependencies or Associated Types. Is that correct? I also gather that "FDs have problems" - although I have no idea what those problems are. Everybody's hoping that ATs will fix this, but ATs are still kinda new. (Are they even fully implemented in GHC yet?) Can anybody correct/expand on this state of affires? I just want to make sure I understand our position correctly...

17 38

[Haskell-cafe] Version 0.4.3 of happs-tutorial is a HAppS job board, done in HAppS.
by Thomas Hartman 29 Sep '08

29 Sep '08

Hello, world. In Version 4 of the ongoing self-demoing HAppS Tutorial, we implement a HAppS job board using HAppS. demo: http://happstutorial.com:5001 install: sudo cabal install happs-tutorial darcs head: darcs get http://code.haskell.org/happs-tutorial There aren't any new lessons compared to the last release, but the code is much cleaner, and... well... the web site actually does something. Coming soon, lessons on form processing and HAppS State. Enjoy! Thomas.

2 2

not able to compile Happy GLR examples
by brianalexander1＠cableone.net 29 Sep '08

29 Sep '08

2 1

ANNOUNCE: Graphalyze-0.1
by Ivan Miljenovic 29 Sep '08

29 Sep '08

I'd like to announce the initial release of my graph-theoretic analysis library, Graphalyze [1], the darcs repo for which is also available [2]. This is a pre-release of the library that I'm writing for my mathematics honours thesis, "Graph-Theoretic Analysis of the Relationships in Discrete Data". I'll also be releasing a tool that uses this library to analyse the structure of Haskell code, that I'm tentatively calling SourceGraph. As it stands, the library has a number of algorithms included, some of which I've developed from scratch (e.g. clique finder), and others are implementations of published algorithms (mainly the two clustering algorithms). The code is meant to be more readable than efficient, and I wanted to explore ways of developing algorithms that match more closely the way graphs work (which makes FGL a much nicer fit than matrix-based or list-based graph data structures). This library is only a pre-release, as whilst everything in there works (at least it does for me), I'd like to get some feedback from the community, especially since this is my first ever released solo piece of code (I've coded assignments, and worked on projects with others, but have never released anything that I've been solely responsible for before). In particular, have I written the .cabal file correctly? Also, I'd like advice on something else: the part of the library that I'd like to develop still is the reporting framework. The end goal of the library is for the user to specify which algorithms they want applied to their data, and then the library produces a document with the results. This document is _not_ meant to be machine readable. As such, I can think of three options: 1) Plain text, with graphs either in seperate image files (using graphviz) or else as plaintext (FGL's show function). 2) Generate LaTeX code. 3) Generate Pandoc [3] compatible Markdown, and let the user convert it into whatever format they prefer. I'm not a big fan of option 1), as it is probably the most unreadable in general. I'd like to use Pandoc, as it is theoretically possible to convert it to numerous other filetypes, however with inline linking there's still no way (at least I can find) to have images scaled to the correct size automatically. So unless I pre-scale the images, using option 3) and then converting to PDF via LaTex generation of the Markdown sources is probably out. As such, what would you all prefer to read as a documentation-style report of your software? 1) A PDF via LaTeX, which has the advantage of being printable and all in one file 2) HTML via Pandoc, which lets you have the images linked separately from the document, and thus no need to shrink them down (they can stay at the natively generated size, and thus easier to zoom in, etc.). Finally, I'll be giving my honours talk on this next Monday. So if you're in Brisbane on 6 October and interested, it'll be on at 2PM at the University of Queensland (where as part of it I'll be explaining to mathematicians why Haskell is a great language to use for mathematics... or at least trying to!). [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Graphalyze [2] http://code.haskell.org/Graphalyze/ [3] http://johnmacfarlane.net/pandoc -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

1 0