September 2011 - Haskell-Cafe

Any good topics for Master Thesis
by Haisheng Wu 04 Sep '11

04 Sep '11

Dear Haskellers, I'm a master student major of computer science and trying to find any topics for my master thesis. My mentor suggest me to find any topic I'm interested in. Therefore I'm thinking whether there are some topics related to FP and Haskell. Especially use such technology to solve problems rather than theory research. Appreciate any suggestions / ideas! -Simon

1 0

ANN: EclipseFP 2.1.0 released
by JP Moresmau 03 Sep '11

03 Sep '11

Hello Haskellers, Version 2.1.0 of the EclipseFP project (Eclipse plugins for Haskell development) has been released. Based mainly on the work Alejandro Serrano did for his GSoC project, this release features a lot of enhancements: - A package/module browser - Hoogle integration: select a identifier in your code and jump to its hoogle definitions - HLint integration: jump directly to HLint errors and warnings - Profiling graphs: run an executable with profiling flags and its the resulting graphs - SourceGraph: generate SourceGraph reports - Better auto completion information And of course some bug fixes. Please go to http://eclipsefp.github.com/, the new website Alejandro designed for more information and installation instructions. Feedback welcome! -- JP Moresmau http://jpmoresmau.blogspot.com/

5 4

Configuration Problem and Plugins
by M. George Hansen 03 Sep '11

03 Sep '11

Greetings, I'm a Python programmer who is relatively new to Haskell, so go easy on me :) I have a program that uses (or will use) plugins to render output to the user in a generic way. I'm basing the design of the plugin infrastructure on the Plugins library, and have the following interface: data Renderer = Renderer { initialize :: IO (), destroy :: IO (), render :: SystemOutput -> IO () } The program loads plugins at the start and runs the initialize function, and then enters the main loop where it repeatedly calls the render function with output to display. When the program exits the main loop, it calls the destroy function to clean up any resources used by the plugin. You can probably already see my problem: how do I pass initialization information created in the initialize function to the render function? I'm vaguely aware of some solutions to the typical "configuration problem", such as implicit arguments or explicitly passing the configuration data through the function call hierarchy. As far as I can tell, neither of these approaches would work because the program can't know at compile time what, if any, configuration data is used by the plugin. I suppose I could pass a Dynamic up the call chain and let the plugin decode it in the render function, but that seems a little kludgy to me. Any thoughts would be greatly appreciated. -- M. George Hansen

2 1

ANN: hledger-web 0.15.1 (& hledger 0.15)
by Simon Michael 02 Sep '11

02 Sep '11

I've made a bugfix release of the hledger-web package, to fix build problems. hledger-web 0.15.1: * web: add missing Hledger.Web.Options to cabal file * web: tighten up dependencies to reduce build problems And here's another new dependency I forgot to mention: flot, the js charting library. The rest of this mail is a repeat of yesterday's announcement, since that one seriously confused google groups, gmane, and perhaps your mailreader (pro tip: don't re-edit old announcements with Mail.app's cmd-shift-d. :) -Simon Date: 2011/9/1 Subject: ANN: hledger 0.15 I'm pleased to announce hledger 0.15! This release includes work by Trygve Laugstøl, Dmitry Astapov, Clint Adams, Johann Klähn and myself. hledger is a library and set of user tools for working with financial data (or anything that can be tracked in a double-entry accounting ledger.) It is a haskell port and friendly fork of John Wiegley's Ledger. hledger provides command-line, curses and web interfaces, and aims to be a reliable, practical tool for daily use. Given a plain text file describing transactions of money or any other commodity, it will print the chart of accounts, account balances, or just the transactions you're interested in. It can also help you record new transactions, or convert CSV data from your bank. Home: http://hledger.org IRC: irc://irc.freenode.net/#ledger Install: cabal update; cabal install hledger [hledger-web hledger-vty hledger-chart hledger-interest] Platform-specific binaries, which are time-consuming to make and support, are now provided on request to financial donors - a great way to give back and help pay hosting costs! Best, -Simon Release notes for 0.15: * hledger's options are now modal, providing better help (using cmdargs) * hledger now lists and runs any hledger-* add-ons found in the user's path * case insensitivity of filter patterns has been fixed * parsing: `alias`/`end aliases` directives, for renaming accounts, are supported, like ledger's but a bit more powerful; also an `--alias` option for renaming on the fly * parsing: the `account` directive now preserves posting type (normal/virtual/balanced virtual) * parsing: the `pop` directive is supported as an alias for `end tag`, like ledger * parsing: `P` (historical price) directives can contain a (ignored) numeric time zone, like ledger * parsing: the leading `!` in directives is now optional and deprecated, like ledger * parsing: entries with a negative amount in the first posting now infer the correct balancing amount * parsing: bad date checking is more accurate * balance: collapsing of boring accounts to one line can be disabled with `--no-elide` * balance: fix a wrong precision regression from last release * convert: standard input can be converted * convert: an alternate rules file can be specified with `--rules` * convert: `account2-field` can be used when the CSV file specifies both accounts * convert: `description-field` can have a custom format and combine multiple CSV fields * convert: `in-field` and `out-field` support CSV files that use two amount columns * convert: don't fail when there's no default journal file * web: the web interface has been overhauled/cleaned up * web: account register views are now transaction-based, like gnucash etc., and show accurate historical balances when possible * web: simple balance charts are displayed (using flot) * web: more expressive and consistent search patterns, using a new matching engine * web: add form uses currently focussed account as default, redirects to itself, formats status messages better * web: sidebar now shows empty/boring accounts too * web: now uses warp and a newer yesod * api simplifications * importable Hledger, Hledger.Web, Hledger.Vty and Hledger.Chart modules * the basic reports are now provided by hledger-lib for easier reuse * new api use examples: `equity.hs`, `uniquify.hs` * some old base 3 support has been dropped * the old -s flag has been dropped Stats: Release contributors: Simon Michael, Trygve Laugstøl, Dmitry Astapov, Clint Adams, Johann Klähn 132 days, 314 commits, 18 end-user features and 6 end-user bugfixes since last release. 210 unit & functional tests and 55% unit test coverage (hledger, hledger-lib packages). 7642 lines of code (all packages).

1 0

type profiling not helpful
by Ozgur Akgun 02 Sep '11

02 Sep '11

Cafe, Using "prog +RTS -M1G -hy" for my program prog, I generate a heap profile as documented in [1]. There is one big block in the output graph labelled with "*" though, which is not very helpful. The star character isn't even mentioned in the documentation, I wonder what it represents. Thanks in advance, [1] http://www.haskell.org/ghc/docs/latest/html/users_guide/prof-heap.html#rts-… -- Ozgur Akgun

1 0

Fwd: job position
by Mario Blažević 02 Sep '11

02 Sep '11

For anybody interested in programming languages or markup languages, there is an open job position for a junior developer at Stilo (http://www.stilo.com/) Haskell is currently used only for prototyping, but there are plans to begin some major development in Haskell within a year. The job ad is attached.

1 0

Regular Expression Parsing via derivatives
by Alex Clemmer 02 Sep '11

02 Sep '11

Hi Haskell people, I've been snooping through various mailing lists and the current Haskell implementation of regular expressions and I was wondering if there has been a discussion about implementing regex parsing with derivatives. If so, I haven't seen it. If not, I'd like to have a discussion about it -- if for no other reason than to decide whether I should implement it as a library, or (to attempt to implement it) as a core feature. For those of you who don't know, recent work by Might and Darais<http://arxiv.org/abs/1010.5023>indicates that parsing CFGs can be done better ( *i.e.*, significantly faster) than more "traditional" approaches<http://swtch.com/%7Ersc/regexp/regexp1.html>. Might's presenting at ICFP later in September about it. I guess the first thing I should ask is, which mailing list is actually the right place to field this inquiry. I considered dropping it in the main haskell list, but wasn't sure how people would respond. -- Alex

5 5

Finger Tree without using Monoid
by Xinyu LIU 02 Sep '11

02 Sep '11

Hi, I was trying to implement MTF (move-to-front) algorithm, However, neither Array nor List satisfied all aspects. Array: Although the random access is O(1), However, move an element to front takes O(N) in average; List: Although move to front is O(1), However, random access takes O(N) in average; I dig out the paper [1] and find the Finger Tree solution. There is already good Finger Tree implementation in Haskell as Data.Sequence [2] based on [3]. I wrote a simple version based on the original paper, but avoid using Monoid when augment (or cache) the size of the tree. The idea is to wrap every element as a leaf of node. This idea is similar to the Chris Okasaki's binary random access list [4]. As one test case, I tested move to front with Finger Tree. Here is the code (sorry for a bit long): >>> module FingerTree where import Test.QuickCheck data Node a = Br Int [a] deriving (Show) -- size, branches data Tree a = Empty | Lf a | Tr Int [a] (Tree (Node a)) [a] -- size, front, middle, rear deriving (Show) type FList a = Tree (Node a) -- Auxiliary functions for calculate size of node and tree size :: Node a -> Int size (Br s _) = s sizeL :: [Node a] -> Int sizeL = sum .(map size) sizeT :: FList a -> Int sizeT Empty = 0 sizeT (Lf a) = size a sizeT (Tr s _ _ _) = s -- Auxiliary functions for building and unboxing node(s) wrap :: a -> Node a wrap x = Br 1 [x] unwrap :: Node a -> a unwrap (Br 1 [x]) = x wraps :: [Node a] -> Node (Node a) wraps xs = Br (sizeL xs) xs unwraps :: Node a -> [a] unwraps (Br _ xs) = xs -- Helper function for building tree tree :: [Node a] -> FList (Node a) -> [Node a] -> FList a tree f Empty [] = foldr cons' Empty f tree [] Empty r = foldr cons' Empty r tree [] m r = let (f, m') = uncons' m in tree (unwraps f) m' r tree f m [] = let (m', r) = unsnoc' m in tree f m' (unwraps r) tree f m r = Tr (sizeL f + sizeT m + sizeL r) f m r -- Operations at the front of the sequence cons :: a -> FList a -> FList a cons a t = cons' (wrap a) t cons' :: (Node a) -> FList a -> FList a cons' a Empty = Lf a cons' a (Lf b) = tree [a] Empty [b] cons' a (Tr _ [b, c, d, e] m r) = tree [a, b] (cons' (wraps [c, d, e]) m) r cons' a (Tr _ f m r) = tree (a:f) m r uncons :: FList a -> (a, FList a) uncons ts = let (t, ts') = uncons' ts in (unwrap t, ts') uncons' :: FList a -> ((Node a), FList a) uncons' (Lf a) = (a, Empty) uncons' (Tr _ [a] Empty [b]) = (a, Lf b) uncons' (Tr _ [a] Empty (r:rs)) = (a, tree [r] Empty rs) uncons' (Tr _ [a] m r) = (a, tree (unwraps f) m' r) where (f, m') = uncons' m uncons' (Tr _ (a:f) m r) = (a, tree f m r) head' :: FList a -> a head' = fst . uncons tail' :: FList a -> FList a tail' = snd . uncons -- Operations at the rear of the sequence snoc :: FList a -> a -> FList a snoc t a = snoc' t (wrap a) snoc' :: FList a -> Node a -> FList a snoc' Empty a = Lf a snoc' (Lf a) b = tree [a] Empty [b] snoc' (Tr _ f m [a, b, c, d]) e = tree f (snoc' m (wraps [a, b, c])) [d, e] snoc' (Tr _ f m r) a = tree f m (r++[a]) unsnoc :: FList a -> (FList a, a) unsnoc ts = let (ts', t) = unsnoc' ts in (ts', unwrap t) unsnoc' :: FList a -> (FList a, (Node a)) unsnoc' (Lf a) = (Empty, a) unsnoc' (Tr _ [a] Empty [b]) = (Lf a, b) unsnoc' (Tr _ f@(_:_) Empty [a]) = (tree (init f) Empty [last f], a) unsnoc' (Tr _ f m [a]) = (tree f m' (unwraps r), a) where (m', r) = unsnoc' m unsnoc' (Tr _ f m r) = (tree f m (init r), (last r)) last' :: FList a -> a last' = snd . unsnoc init' :: FList a -> FList a init' = fst . unsnoc -- Concatenation concat' :: FList a -> FList a -> FList a concat' t1 t2 = merge t1 [] t2 merge :: FList a -> [Node a] -> FList a -> FList a merge Empty ts t2 = foldr cons' t2 ts merge t1 ts Empty = foldl snoc' t1 ts merge (Lf a) ts t2 = merge Empty (a:ts) t2 merge t1 ts (Lf a) = merge t1 (ts++[a]) Empty merge (Tr s1 f1 m1 r1) ts (Tr s2 f2 m2 r2) = Tr (s1 + s2 + (sizeL ts)) f1 (merge m1 (nodes (r1 ++ ts ++ f2)) m2) r2 nodes :: [Node a] -> [Node (Node a)] nodes [a, b] = [wraps [a, b]] nodes [a, b, c] = [wraps [a, b, c]] nodes [a, b, c, d] = [wraps [a, b], wraps [c, d]] nodes (a:b:c:xs) = (wraps [a, b, c]):nodes xs -- Splitting splitAt' :: Int -> FList a -> (FList a, Node a, FList a) splitAt' _ (Lf x) = (Empty, x, Empty) splitAt' i (Tr _ f m r) | i < szf = let (xs, y, ys) = splitNodesAt i f in ((foldr cons' Empty xs), y, tree ys m r) | i < szf + szm = let (m1, t, m2) = splitAt' (i-szf) m (xs, y, ys) = splitNodesAt (i-szf - sizeT m1) (unwraps t) in (tree f m1 xs, y, tree ys m2 r) | otherwise = let (xs, y, ys) = splitNodesAt (i-szf -szm) r in (tree f m xs, y, foldr cons' Empty ys) where szf = sizeL f szm = sizeT m splitNodesAt :: Int -> [Node a] -> ([Node a], Node a, [Node a]) splitNodesAt 0 [x] = ([], x, []) splitNodesAt i (x:xs) | i < size x = ([], x, xs) | otherwise = let (xs', y, ys) = splitNodesAt (i-size x) xs in (x:xs', y, ys) -- Random access operations getAt :: FList a -> Int -> a getAt t i = unwrap x where (_, x, _) = splitAt' i t extractAt :: FList a -> Int -> (a, FList a) extractAt t i = let (l, x, r) = splitAt' i t in (unwrap x, concat' l r) setAt :: FList a -> Int -> a -> FList a setAt t i x = let (l, _, r) = splitAt' i t in concat' l (cons x r) -- move the i-th element to front moveToFront :: FList a -> Int -> FList a moveToFront t i = let (a, t') = extractAt t i in cons a t' -- auxiliary functions fromList :: [a] -> FList a fromList = foldr cons Empty toList :: FList a -> [a] toList Empty = [] toList t = (head' t):(toList $ tail' t) -- testing prop_cons :: [Int] -> Bool prop_cons xs = xs == (toList $ fromList xs) prop_snoc :: [Int] -> Bool prop_snoc xs = xs == (toList' $ foldl snoc Empty xs) where toList' Empty = [] toList' t = (toList' $ init' t)++[last' t] prop_concat :: [Int]->[Int]->Bool prop_concat xs ys = (xs ++ ys) == (toList $ concat' (fromList xs) (fromList ys)) prop_lookup :: [Int] -> Int -> Property prop_lookup xs i = (0 <=i && i < length xs) ==> (getAt (fromList xs) i) == (xs !! i) prop_update :: [Int] -> Int -> Int -> Property prop_update xs i y = (0 <=i && i < length xs) ==> toList (setAt (fromList xs) i y) == xs' where xs' = as ++ [y] ++ bs (as, (_:bs)) = splitAt i xs prop_mtf :: [Int] -> Int -> Property prop_mtf xs i = (0 <=i && i < length xs) ==> (toList $ moveToFront (fromList xs) i) == mtf where mtf = b : as ++ bs (as, (b:bs)) = splitAt i xs <<< It can be found at: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/datastruct/elementary/arra… [Reference] [1]. Jon Bentley, Daniel Sleator, Robert Tarjan, Victor Wei. "A locally adaptive data compression scheme." Communication of the ACM.1986. [2]. http://hackage.haskell.org/packages/archive/fingertree/0.0/doc/html/Data-Fi… [3]. Ralf Hinze and Ross Paterson, "Finger trees: a simple general-purpose data structure", *Journal of Functional Programming* 16:2 (2006) pp 197-217. http://www.soi.city.ac.uk/~ross/papers/FingerTree.html [4]. Purely Functional Random-Access Lists by Chris Okasaki. Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95. -- Larry, LIU Xinyu https://sites.google.com/site/algoxy/ https://github.com/liuxinyu95/AlgoXY

4 3

Is it a bug in haskell-src-meta package?
by bob zhang 01 Sep '11

01 Sep '11

Hi, all parseExp "(,) 3 4 " => Right (AppE (AppE (ConE GHC.Unit.(,)) (LitE (IntegerL 3))) (LitE (IntegerL 4))) where's GHC.Unit.(,) ? Many thanks best, bob

3 6

Pointed, but not Applicative
by Sönke Hahn 01 Sep '11

01 Sep '11

Hi! I was reading through the Typeclassopedia ([1]) and I was wondering which type could be an instance of Pointed, but not of Applicative. But I can't think of one. Any ideas? Sönke [1] http://www.haskell.org/haskellwiki/Typeclassopedia

8 16