- Haskell-Cafe - Haskell.org

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

Overload function application? (was: foldr (.) id)
by Greg Fitzgerald 28 Oct '12

28 Oct '12

Should library functions target Control.Category? We write for Num, IsString, and ListLike. Haskell overloads number literals and string literals, and awkwardly not List literals. Should Haskell overload function application too? How cool would it be to be able to leverage all of Haskell's libraries, and effectively none of the runtime, by implementing instances for literals and function application? Say, for example, to generate a call graph, or make the language strict, or target LLVM more directly. Anyone tried this? Thanks, Greg On Sat, Oct 27, 2012 at 11:39 AM, Greg Fitzgerald <garious(a)gmail.com> wrote: > > Alternatively: flip (foldr id) > > Very cool, but... > > Prelude> import qualified Data.Foldable as F > Prelude F> :t F.foldr id > F.foldr id :: F.Foldable t => b -> t (b -> b) -> b > > > {- Generalizing -} > > Prelude F> import qualified Control.Category as C > Prelude F C> :t F.foldr (C..) C.id > F.foldr (C..) C.id :: (F.Foldable t, C.Category cat) => t (cat b b) -> cat > b b > > > {- Sneaky type-specialization -} > > Prelude F C> :t F.foldr C.id > F.foldr C.id :: F.Foldable t => b -> t (b -> b) -> b > > > On Sat, Oct 27, 2012 at 3:09 AM, Ross Paterson <ross(a)soi.city.ac.uk>wrote: > >> On Fri, Oct 26, 2012 at 07:41:18PM +0100, Greg Fitzgerald wrote: >> > 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. >> >> Alternatively: flip (foldr id) >> >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > >

2 1

Sparse records/ADTs
by Jon Fairbairn 27 Oct '12

27 Oct '12

Is there a convenient way of handling a data structure with lots of fields of different types that may or may not be filled in? Something equivalent to data D = D {a::Maybe A, b::Maybe B, c::Maybe C, …} but with better space efficiency and a more convenient empty object. An easy alternative is data E = Ea A | Eb B | Ec C | … type R = [E] which has a straightforward empty object, but one then must define getA e = listToMaybe [a | Ea a <- e] for each field, which is tedious (and O(n)). Obviously Templates would help, but is there an alternative I’ve missed? -- Jón Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk

8 10

Type-directed functions with data kinds
by Paul Visschers 27 Oct '12

27 Oct '12

Hello everyone, I've been playing around with the data kinds extension to implement vectors that have a known length at compile time. Some simple code to illustrate: > {-# LANGUAGE DataKinds, GADTs, KindSignatures #-} > > import Prelude hiding (repeat) > > data Nat = Zero | Succ Nat > data Vector (n :: Nat) a where > Nil :: Vector Zero a > Cons :: a -> Vector n a -> Vector (Succ n) a > > class VectorRepeat (n :: Nat) where > repeat :: a -> Vector n a > > instance VectorRepeat Zero where > repeat _ = Nil > > instance VectorRepeat n => VectorRepeat (Succ n) where > repeat x = Cons x (repeat x) In this code I have defined a repeat function that works in a similar way to the one in the prelude, except that the length of the resulting vector is determined by the type of the result. I would have hoped that its type would become 'repeat :: a -> Vector n a', yet it is 'repeat :: VectorRepeat n => a -> Vector n a'. As far as I can tell, this class constraint should no longer be necessary, as all possible values for 'n' are an instance of this class. I actually really just want to define a closed type-directed function and would rather not (ab)use the type class system at all. Is there a way to write the repeat function so that it has the type 'repeat :: a -> Vector n a' that I've missed? If not, is this just because it isn't implemented or are there conceptual caveats? Paul Visschers

5 6

Enemy of the Mutable State
by Mark Lentczner 27 Oct '12

27 Oct '12

A Haskell poster I made that you all might enjoy: http://www.ozonehouse.com/mark/enemy/ - mzero

1 0

ANNOUNCE: pretty-tree
by Ivan Lazar Miljenovic 26 Oct '12

26 Oct '12

For a project I'm working on, I got sick of writing out trees by hand. Data.Tree has a drawTree function, but whilst it's better than nothing, I prefer a more top-down "traditional" approach to drawing trees. So I wrote a package to do just that: http://hackage.haskell.org/package/pretty-tree (I didn't think to check whether diagrams had capabilities to do so until after I finished, though in this case I prefer a textual approach anyway.) I'm more than happy to consider adding other forms of drawing trees (though off-hand I can't think of any), or of course you can send me patches since I'm taking advantage of the nice new shiny hub.darcs.net (thanks Darcs team!). I was going to put an example here but it only really comes out nicely if you're using a monospaced font, so have a look at the Haddock docs for the module once Hackage builds it (in hindsight, I should probably have come up with better labels before releasing the package... oh well :) -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

4 4