- Haskell-Cafe - Haskell.org

Segment Tree based Set
by Tony Morris 29 Oct '12

29 Oct '12

Hi, I was wondering if anyone knows of a package implementing a fast lookup for an element in ranges. For example, this operation: Ord a => a -> [(a, a)] -> Bool ...can be implemented: \a rs -> let s = Set.fromList rs in a `member` s This is not particularly efficient. A segment tree seems like a more appropriate data structure to store the ranges. Does such a library exist? -- Tony Morris http://tmorris.net/

5 6

Empirically comparing strict vs. lazy evaluation
by Kristopher Micinski 29 Oct '12

29 Oct '12

Hello Haskellers! I wonder if you know of benchmarks that attempt to compare, empirically, lazy vs. eager evaluation. Pointers to papers and/or code would be most appreciated. Our group (at UMD) is working on a paper that develops some technology for lazy programs, and we would like to choose benchmarks for evaluating it that span the gamut of computations that perform well when done lazily, vs. those that do not perform as well when evaluated lazily. Then we want to look at the best case and worst case for our technology WRT laziness, and see how it stacks up. Thanks in advance for any ideas you have! Kris Micinski

1 0

ICFP 2013: Call for workshops and co-located events
by David Van Horn 29 Oct '12

29 Oct '12

CALL FOR WORKSHOP AND CO-LOCATED EVENT PROPOSALS ICFP 2013 18th ACM SIGPLAN International Conference on Functional Programming September 22 - 28, 2013 Boston, Massachusetts, USA http://icfpconference.org/icfp2013/ The 18th ACM SIGPLAN International Conference on Functional Programming will be held in Boston, Massachusetts on September 22-28, 2013. ICFP provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. Proposals are invited for workshops (and other co-located events, such as tutorials) to be affiliated with ICFP 2013 and sponsored by SIGPLAN. These events should be more informal and focused than ICFP itself, include sessions that enable interaction among the attendees, and foster the exchange of new ideas. The preference is for one-day events, but other schedules can also be considered. The workshops are scheduled to occur on September 22-24 (the three days before ICFP) and September 28 (the day after ICFP). ---------------------------------------------------------------------- Submission details Deadline for submission: December 7, 2012 Notification of acceptance: January 7, 2013 Prospective organizers of workshops or other co-located events are invited to submit a completed workshop proposal form in plain text format to the ICFP 2013 workshop co-chairs (Patrik Jansson and Sam Tobin-Hochstadt), via email to icfp13-workshops(a)ccs.neu.edu by December 7, 2012. (For proposals of co-located events other than workshops, please fill in the workshop proposal form and just leave blank any sections that do not apply.) Please note that this is a firm deadline. Organizers will be notified if their event proposal is accepted by January 7, 2013, and if successful, depending on the event, they will be asked to produce a final report after the event has taken place that is suitable for publication in SIGPLAN Notices. The proposal form is available at: http://www.icfpconference.org/icfp2013/icfp13-workshops-form.txt Further information about SIGPLAN sponsorship is available at: http://acm.org/sigplan/sigplan_workshop_proposal.htm ---------------------------------------------------------------------- Selection committee The proposals will be evaluated by a committee comprising the following members of the ICFP 2013 organizing committee, together with the members of the SIGPLAN executive committee. Workshop Co-Chair: Patrik Jansson (Chalmers University of Technology) Workshop Co-Chair: Sam Tobin-Hochstadt (Northeastern University) General Chair : Greg Morrisset (Harvard University) Program Chair: Tarmo Uustalu (Tallinn University of Technology) ---------------------------------------------------------------------- Further information Any queries should be addressed to the workshop co-chairs (Patrik Jansson and Sam Tobin-Hochstadt), via email to icfp13-workshops(a)ccs.neu.edu

1 0

hsql-mysql encoding issues
by Johannes Waldmann 29 Oct '12

29 Oct '12

Hi. I am using hsql-(mysql-)1.8.2 When compiled with ghc-7.6, the resulting executable does not seem to be able to read strings from the DB correctly (umlauts do "vanish") while it worked with hsql-(mysql-)1.8.1 and ghc-7.4. the mysql server says (show variables) | character_set_client | latin1 | | character_set_connection | latin1 | | character_set_database | latin1 | | character_set_filesystem | binary | | character_set_results | latin1 | | character_set_server | latin1 | | character_set_system | utf8 | hsql is using type String all over the place, while it should be ByteString? Internally, Database.HSQL.Types.SqlBind uses Foreign.C.String.peekCStringLen . Did the behaviour of this function change? hsql is quite old, but so is my application. Assuming I find the time to rewrite my code (not likely) - what DB binding should I rather be using? Thanks - J.W.

3 4

foldr (.) id
by Greg Fitzgerald 29 Oct '12

29 Oct '12

Hi Haskellers, I've recently found myself using the expression: "foldr (.) id" to compose a list (or Foldable) of functions. It's especially useful when I need to map a function over the list before composing. Does this function, or the more general "foldr fmap id", defined in a library anywhere? I googled and hoogled, but no luck so far. Thanks, Greg

10 13

Maximum bipartite matching: 24 lines
by Stefan Klinger 29 Oct '12

29 Oct '12

Hello. I have written a function that calculates maximum cardinality matchings on bipartite graphs. It's only 24 lines of code. It seems (tested, not proven) to run faster, use less memory, and scale better than using MaxFlow from FGL with constant weight and additional source and sink nodes. But it's not as good as Hopcroft–Karp would be. Attached is the module MaxMatching which also contains extensive documentation of the rationale behind its design. I would hope to get any feedback on this: What do you think about the approach? Did I oversee anything? Do you know of any other purely functional solution to this problem? Just as an exmaple, run `ghci MaxMatching.lhs` and then use matching $ S.fromList [(1,'a'),(1,'b'),(2,'a'),(2,'c'),(3,'b')] to calculate a maximum cardinality matching of the graph shown below. 1---a Note the somewhat awkward type of the matching \ / function, returning a Map instead of a Set, with the X edges being backwards! / \ 2 b matching :: (Ord b, Ord a) => S.Set (a, b) -> M.Map b a \ / X On my machine, it takes less than 2s on 10k edges / \ or 225 nodes. 3 c Comments are welcome! Thank you! Stefan -- Stefan Klinger o/klettern /\/ bis zum send plaintext only - max size 32kB - no spam \ Abfallen http://stefan-klinger.de

3 3

non-uniform recursive Trie
by Kazu Yamamoto 29 Oct '12

29 Oct '12

Hello cafe, I'm now studying Trie in Okasaki's "Purely Functional Data Structure". Attached is the program in its appendix. I cannot understand how to use "empty", "look" and "bind". For instance, if I type 'look "" empty', I got an error: > look "" empty <interactive>:2:1: No instance for (FiniteMap m0 [Char]) arising from a use of `look' Possible fix: add an instance declaration for (FiniteMap m0 [Char]) In the expression: look "" empty In an equation for `it': it = look "" empty I have no idea how to determine the parameter 'm'. Suggestions would be appreciated. --Kazu {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} class FiniteMap m k where empty :: m k v look :: k -> m k v -> Maybe v bind :: k -> v -> m k v -> m k v data Trie m ks v = Trie (Maybe v) (m (Trie m ks v)) instance FiniteMap m k => FiniteMap (Trie (m k)) [k] where empty = Trie Nothing empty look [] (Trie b _) = b look (k:ks) (Trie _ m) = look k m >>= look ks bind [] x (Trie _ m) = Trie (Just x) m bind (k:ks) x (Trie b m) = Trie b (bind k t' m) where t = case look k m of Just a -> a Nothing -> empty t' = bind ks x t

2 2

Building all possible element combinations from N lists.
by dokondr 28 Oct '12

28 Oct '12

Hi all, I am looking for the algorithm and code better then the one I wrote (please see below) to solve the problem given in the subject. Unfortunately I finally need to implement this algorithm in Java. That's why I am not only interested in beautiful Haskell algorithms, but also in the one that I can without much pain implement in procedural PL like Java :( {-- Build all possible element combinations from N lists. Valid combination consists of k <= N elements. Where each element of a single combination is taken from one of the N lists. When building combination any list can give only one element for this combination. In other words you can not take more then one element from one and the same list when building current combination. Thus combinations between elements from the same input list are not allowed. Yet when building next combination you can use any of the lists again. Order of elements in combinaton does not matter. For example: input = [ [["a"],["b"]], [["1"],["2"]], [["<"],[">"]] ] output = [ ["a"],["b"],["1"],["2"], ["a","1"],["a","2"],["b","1"],["b","2"], ["<"],[">"], ["a","<"],["a",">"],["b","<"],["b",">"], ["1","<"],["1",">"],["2","<"],["2",">"], ["a","1","<"],["a","1",">"],["a","2","<"],["a","2",">"], ["b","1","<"],["b","1",">"],["b","2","<"],["b","2",">"] ] (see bigger example at the end of the code) Current implementation is based on the idea of using combinations accumulator. After first run accumulator contains: 1) All elements from the first two lists. These two lists are taken from the input list of lists. The elements of these first two lists are put in accumulator as is. For example: ["a"],["b"],["1"],["2"] 2) All combinations of these elements: ["a","1"],["a","2"],["b","1"],["b","2"] Note: Combinations between elements from the same input list are not allowed Next, on each run we add combinations built from accumulator elements together with next list taken from the input list of list. --} input = [ [["a"],["b"]], [["1"],["2"]], [["<"],[">"]], [["X"],["Y"]] ] addAll :: [[[a]]] -> [[a]] addAll [] = [] addAll (x:[]) = x addAll (x:y:[]) = accum x [y] addAll inp = accum (initLst inp) (restLst inp) initLst inp = fstLst ++ sndLst ++ (addLst fstLst sndLst) where fstLst = inp !! 0 sndLst = inp !! 1 restLst inp = (tail . tail) inp accum :: [[a]] -> [[[a]]] -> [[a]] accum xs (r:rs) = accum (xs ++ r ++ addLst xs r) rs accum xs _ = xs addLst :: [[a]] -> [[a]] -> [[a]] addLst (x:xs) ys = addOne x ys ++ addLst xs ys addLst _ [] = [] addLst [] _ = [] addOne :: [a] -> [[a]] -> [[a]] addOne x (y:ys) = [x ++ y] ++ addOne x ys addOne x [] = [] {-- For example: input = [ [["a"],["b"]], [["1"],["2"]], [["<"],[">"]], [["X"],["Y"]] ] output = [ ["<"],[">"], ["a"],["b"],["1"],["2"], ["a","1"],["a","2"],["b","1"],["b","2"], ["a","<"],["a",">"],["b","<"],["b",">"], ["1","<"],["1",">"],["2","<"],["2",">"], ["a","1","<"],["a","1",">"],["a","2","<"],["a","2",">"], ["b","1","<"],["b","1",">"],["b","2","<"],["b","2",">"], ["X"],["Y"], ["a","X"],["a","Y"],["b","X"],["b","Y"], ["1","X"],["1","Y"],["2","X"],["2","Y"], ["a","1","X"],["a","1","Y"],["a","2","X"],["a","2","Y"], ["b","1","X"],["b","1","Y"],["b","2","X"],["b","2","Y"], ["<","X"],["<","Y"],[">","X"],[">","Y"], ["a","<","X"],["a","<","Y"],["a",">","X"],["a",">","Y"], ["b","<","X"],["b","<","Y"],["b",">","X"],["b",">","Y"], ["1","<","X"],["1","<","Y"],["1",">","X"],["1",">","Y"], ["2","<","X"],["2","<","Y"],["2",">","X"],["2",">","Y"], ["a","1","<","X"],["a","1","<","Y"],["a","1",">","X"],["a","1",">","Y"], ["a","2","<","X"],["a","2","<","Y"],["a","2",">","X"],["a","2",">","Y"], ["b","1","<","X"],["b","1","<","Y"],["b","1",">","X"],["b","1",">","Y"], ["b","2","<","X"],["b","2","<","Y"],["b","2",">","X"],["b","2",">","Y"] ] --}

4 6

Gaussian Distribution
by Frank Recker 28 Oct '12

28 Oct '12

Hi, at work, I often need the values the cumulative distribution function of the Gaussian distribution. The code for this function in haskell, erlang and perl and the corresponding mathematical paper can be found at git://github.com/frecker/gaussian-distribution.git . Regards, Frank

1 0

Auto-termination and leftovers in Conduits
by Myles C. Maxfield 28 Oct '12

28 Oct '12

Hey, Say I have a stream of Data.Text.Text objects flowing through a conduit, where the divisions between successive Data.Text.Text items occur at arbitrary boundaries (maybe the source is sourceFile $= decode utf8). I'd like to create a Sink that returns a tuple of (the first line, the rest of the input). My first attempt at this looks like this: sink = do out1 <- CT.lines C.=$ CL.head out2 <- CL.consume return (out1, T.concat out2) However, the following input provides: runIdentity $ CL.sourceList ["abc\nde", "f\nghi"] C.$$ sink (Just "abc","f\nghi") But what I really want is (Just "abc", "\ndef\nghi") I think this is due to the auto-termination you mention in [1]. My guess is that when CT.lines yields the first value, (CL.head then also yields it,) and execution is auto-terminated before CT.lines gets a chance to specify any leftovers. How can I write this sink? (I know I can just use CL.consume and T.break (== '\n'), but I'm not interested in that. I'm trying to figure out how to get the behavior I'm looking for with conduits.) Thanks, Myles [1] http://hackage.haskell.org/packages/archive/conduit/0.5.2.7/doc/html/Data-C…

2 2