- Haskell-Cafe - Haskell.org

Steven S. Skiena of "The Algorithm Design Manual", Second Edition, 2008 has sent me a message that if there is a Haskell page of algorithms he will link to it.
by Casey Hawthorne 28 May '10

28 May '10

Hi: Steven S. Skiena of "The Algorithm Design Manual", Second Edition, 2008 has sent me a message that if there is a Haskell page of algorithms he will link to it. So, is there such a page and/or is there some collection(s) of algorithms and data structures some where that I can massage into the shape of his book? :) -- Regards, Casey

3 3

Re: [Haskell] Re: [Haskell-cafe] Work on Video Games in Haskell
by Ketil Malde 28 May '10

28 May '10

<bf3(a)telenet.be> writes: > Or maybe this would be a nice research topic: how to generate C code > that looks like it’s human written… Nah, that's too easy: just add a sprinkling of buffer overflows, undefined behavior, and off-by one index errors. -k -- If I haven't seen further, it is by standing in the footprints of giants

5 5

ANNOUNCE: Haskell Communities and Activities Report (18th ed., May 2010)
by Janis Voigtländer 28 May '10

28 May '10

On behalf of the many, many contributors, I am pleased to announce that the Haskell Communities and Activities Report (18th edition, May 2010) is now available in PDF and HTML formats: http://haskell.org/communities/05-2010/report.pdf http://haskell.org/communities/05-2010/html/report.html Many thanks go to all the people that contributed to this report, both directly, by sending in descriptions, and indirectly, by doing all the interesting things that are reported. I hope you will find it as interesting a read as I did. If you have not encountered the Haskell Communities and Activities Reports before, you may like to know that the first of these reports was published in November 2001. Their goal is to improve the communication between the increasingly diverse groups, projects, and individuals working on, with, or inspired by Haskell. The idea behind these reports is simple: Every six months, a call goes out to all of you enjoying Haskell to contribute brief summaries of your own area of work. Many of you respond (eagerly, unprompted, and sometimes in time for the actual deadline ;-) to the call. The editor collects all the contributions into a single report and feeds that back to the community. When I try for the next update, six months from now, you might want to report on your own work, project, research area or group as well. So, please put the following into your diaries now: ---------------------------------------- End of October 2010: target deadline for contributions to the November 2010 edition of the HC&A Report ---------------------------------------- Unfortunately, many Haskellers working on interesting projects are so busy with their work that they seem to have lost the time to follow the Haskell related mailing lists and newsgroups, and have trouble even finding time to report on their work. If you are a member, user or friend of a project so burdened, please find someone willing to make time to report and ask them to "register" with the editor for a simple e-mail reminder in October (you could point me to them as well, and I can then politely ask if they want to contribute, but it might work better if you do the initial asking). Of course, they will still have to find the ten to fifteen minutes to draw up their report, but maybe we can increase our coverage of all that is going on in the community. Feel free to circulate this announcement further in order to reach people who might otherwise not see it. Enjoy! Janis Voigtlaender <hcar at haskell.org>

1 0

Optimizations and constant unboxed values
by Pierre-Etienne Meunier 28 May '10

28 May '10

Hi Cafe, Profiling a function that I thought ultra simple revealed that it consumed more than half the execution time of my code. After noticing that GHC did not unbox all I thought it did, I rewrote it with primitive types, and it did a little better, but not much. Then, examining the core (with of course -O3 on) revealed things like : (GHC.Prim.*## (GHC.Prim.-## 1.0 (GHC.Prim.**## 2.0 -53.0)) (GHC.Prim.**## 2.0 1024.0)) or case GHC.Prim.<## x_aB9 (GHC.Prim.**## 2.0 -1021.0) of _ {... Then I wondered if this was really the last stage of GHC's optimizations, as constants are not yet propagated. Or maybe GHC does not propagate constants, in which case I'd really like to write my 1-2^53 and 2^-1021 once and for all in my program. But since unsafeCoerce# does not work between doubles and words ( there is a trac ticket about it : http://hackage.haskell.org/trac/ghc/ticket/4092 ), I do not even think this is possible (and of course, specifying a double in decimal notation with ## is not precise enough for this program). Any clue about how to do it ? Thanks, PE

2 1

Turn off verbose template haskell output
by Michael Snoyman 28 May '10

28 May '10

Hi all, Is there a GHC flag to turn off all of the "Loading package..." messages from Template Haskell? Thanks, Michael

1 0

Chuch encoding of data structures in Haskell
by Günther Schmidt 28 May '10

28 May '10

Hi all, I'm exploring the use of church encodings of algebraic data types in Haskell. Since it's hard to imagine being the first to do so I wonder if folks here could point me to some references on the subject. I'm looking for examples of church encodings in Haskell a little bit beyond Church Booleans and Church Numerals. Günther

11 14

Re[2]: [Haskell-cafe] Re: Unicode vs. System.Directory
by Bulat Ziganshin 28 May '10

28 May '10

Hello Andy, Friday, May 28, 2010, 1:05:59 AM, you wrote: > Looks my file-manager: > http://farm5.static.flickr.com/4027/4584389024_782b1e09ee_o.png can you please share windows and linux executables and source code? > I have finish all necessary GIO APIs at > http://patch-tag.com/r/AndyStewart/gio-branch/home > I will try to merge those APIs to next release version of gtk2hs when i > have spare time. it seems that i can just merge these sources into my program for a while. but what is the license? believe it or not, but i have commercial project on the march -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 1

Announce : New haskell-llvm mailing list.
by Erik de Castro Lopo 28 May '10

28 May '10

Hi all, I have set up a mailing list for discussion of haskell and LLVM related topics. All discussion on using Haskell with LLVM is relevant. That includes the haskell-llvm bindings on Hackage, custom LLVM bindings and directly generating LLVM IR code from haskell and passing that through the LLVM tools. In particular, this list is a place to share code, information, techniques and user experiences. The subscription page is here: http://projects.haskell.org/cgi-bin/mailman/listinfo/haskell-llvm Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

2 1

Multidimensional generalization of the vector package
by Gregory Crosswhite 27 May '10

27 May '10

Hey everyone, I have been thinking about how to generalize the vector package to multiple dimensions, and I'd like to share my ideas with you all in the hope of having people smarter than me share their thoughts on how it could be improved --- *especially* regarding how to make it efficient! The standard way to represent a memory layout is to use a stride vector --- i.e., a vector which lets you get the (flat) index in memory of a given element by dotting the stride vector with the multidimensional index vector. This has the advantage that one can efficiently manipulate it to represent views with arbitrary slices, subranges, subranges plus striping (i.e., take every k-th element), and transpositions. Basically the only thing it can't do is represent a weird view where we, say, take every index along a particular dimension that is a prime number. Having said this, it might be useful to abstract the memory layout in order to preserve generality. Thus, I was thinking that the layout of the multidimensional vector could be represented as a type class with an associated type family: class MemoryLayout layout where type LayoutIndex layout :: * indexOf :: layout -> (LayoutIndex layout) -> Int firstIndex :: layout -> (LayoutIndex layout) -> Int lastIndex :: layout -> (LayoutIndex layout) -> Int withinBounds :: layout -> (LayoutIndex layout) -> Bool ... etc. It is important that we be able to iterate through the array efficiently. One way that this could be done is through the use of cursors. class MemoryLayout layout where ... type LayoutCursor layout :: * ... getCursorAt :: layout -> (LayoutIndex layout) -> (LayoutCursor cursor) getFirstCursor :: layout -> (LayoutCursor cursor) getLastCursor :: layout -> (LayoutCursor cursor) indexOfCursor :: layout -> (LayoutCursor cursor) -> Int advanceCursor :: layout -> (LayoutCursor cursor) -> (LayoutCursor cursor) In general these unfortunately cannot be integers because integers don't contain enough information to tell us about where we need to go next inside a non-contiguous array. The alternative is to use a data structure, but then we may potentially have lots of potentially wasteful allocations, deallocations, and copying going on unless we can somehow cause the cursor to be updated destructively. Fortunately, much of the time our array will be contiguous, so we can have a special case fast-path for this case: class MemoryLayout layout where ... layoutIsContiguous :: layout -> Bool layoutIsContiguousWhenTraversedInRowMajorOrder :: layout -> Bool layoutIsContiguousWhenTraversedInColumnMajorOrder :: layout -> Bool Then we know that we can just iterate through the array in the order of the indices. It turns out that it is not hard to compute whether a layout is contiguous efficiently. For example, in the code that implements cuts and slicing we can actually check to see if the new view is still contiguous and simply cache this in the layout. For restricted cases of layouts (when there aren't transpositions) it isn't too hard to just scan through the layout and see if it is contiguous. Another way to iterate through the array is to provide this capability by constructing functions that traverse through the array for us and call some user-supplied function on each element. This actually can be a lot more efficient (since by using recursive algorithms it can store the information that it needs on the stack rather than using heap allocations) but it is much more restrictive, and it requires special cases for traversing multiple arrays in parallel. Probably the most general way to sum/fold/etc. over particular dimensions (i.e., given a 4D vector, sum over the first and third dimensions leaving the second and fourth dimensions) is simply to generalize the notion of cursors, so that rather than iterating over elements we are iterating over views of the array. class (MemoryLayout layout1, MemoryLayout layout2) => MemoryLayoutSubviewable layout1 layout2 where type MemoryLayoutViewSetSlicer layout1 layout2 :: * type MemoryLayoutViewSet layout1 layout2 :: * getViewSet :: (MemoryLayoutViewSetSlicer layout1 layout2) -> layout1 -> (MemoryLayoutViewSet layout1 layout2) advanceViewSet :: (MemoryLayoutViewSet layout1 layout2) -> (MemoryLayoutViewSet layout1 layout2) currentView :: MemoryLayoutViewSet layout1 layout2 -> layout2 This way we can hand getViewSet some "slicer" that selects some dimensions to be reduced but not others and get back a set of views that we can iterate over, providing a generalization of the sum and fold functionality provided by repa. Although these framework allows us to stay general, in practice working with shapes that are fixed-length vectors (I personally would prefer the Vec package over the hand-rolled one in repa) tends to be easiest, because it allows one to write recursive algorithms employing type families that can define views for arrays with arbitrary dimensions. Also, in practice one can construct type aliases any helper functions such as i1 a = a :. () i2 a b = a :. b :. () i3 a b c = a:. b:. c:. () . . . type I0 = () type I1 = Int : I0 type I2 = Int :. I1 . . . etc. so that we construct values via (i2 x y) rather than (x :. y :. ()). Any thoughts? Cheers, Greg

1 0

Unicode vs. System.Directory
by Arie Peterson 27 May '10

27 May '10

After upgrading to haskell-platform-2010.1.0.0, with the improved unicode support for IO in ghc-6.12, I hoped to be able to deal with filenames containing non-ascii characters. This still seems problematic, though: $ ls m×n♯α $ ghci GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help Prelude> :m +System.Directory Prelude System.Directory> getDirectoryContents "." >>= mapM_ putStrLn .. mÃnâ¯Î± . I hope this passes through the various email systems unharmed; on my terminal, the output of 'ls' contains shiny unicode characters, while 'ghci' garbles up the filename. (My locale is en_GB.utf8.) Similar problems arise with functions such as 'copyFile', which refuses to handle filenames with non-ascii characters (unless wrapping it with encoding functions). Is this a known problem? I searched ghc's trac, but there are no relevant bugs for the component 'libraries/directory'. I have parts of a unicode-aware layer on top of System.Directory laying around somewhere. I was rather hoping to ditch it, but I can polish it and put it on hackage, if people are interested. Kind regards, Arie

5 4