September 2012 - Haskell-Cafe

ANNOUCE: one-liner-0, SYB-like generics with constraint kinds
by Sjoerd Visscher 19 Sep '12

19 Sep '12

Hi all, I am pleased to announce the first release of One-Liner, a package for writing short and concise generic instances of type classes. It works a bit like Scrap-Your-Boilerplate, but it uses the new constraint kinds instead of the Typeable class. On hackage: http://hackage.haskell.org/package/one-liner-0 On github: https://github.com/sjoerdvisscher/one-liner For example, this is how to write generic equality (using the All monoid): eqADT :: (ADT t, Constraints t Eq) => t -> t -> Bool eqADT s t = ctorIndex s == ctorIndex t && getAll (mbuilds (For :: For Eq) (\fld -> All $ s ! fld == t ! fld) `at` s) The code works like this: "Constraints t Eq" means it requires that all subcomponents of type t have an Eq instance, and then values s and t are equal if they are built by the same constructor and each subcomponent is equal. The package is called One-Liner because the generic functions often end up as short as eqADT, especially if there's already an appropriate Monoid or Applicative functor available. Here are two more examples, generic put and get for the Binary package (after adding the missing Monoid instance for Put) putADT :: (ADT t, Constraints t Binary) => t -> Put putADT t = putWord8 (toEnum (ctorIndex t)) >> gfoldMap (For :: For Binary) put getADT :: (ADT t, Constraints t Binary) => Get t getADT = do ix <- fromEnum <$> getWord8 buildsA (For :: For Binary) (const get) !! ix Finally, to give a complete sense of what's involved, here's an example data type and its ADT implementation: data T a = A Int a | B a (T a) instance ADT (T a) where ctorIndex A{} = 0 ctorIndex B{} = 1 type Constraints (T a) c = (c Int, c a, c (T a)) buildsRecA For sub rec = [ (ctor "A", A <$> sub (FieldInfo (\(A i _) -> i)) <*> sub (FieldInfo (\(A _ a) -> a))) , (ctor "B", B <$> sub (FieldInfo (\(B a _) -> a)) <*> rec (FieldInfo (\(B _ t) -> t))) ] If you want to learn more, you can find an introductory blog post here: https://github.com/sjoerdvisscher/blog/blob/master/2012/2012-09-06%20constr… Some complete examples are here: https://github.com/sjoerdvisscher/one-liner/tree/master/examples Some more generic functions, including generic Show and Read: https://github.com/sjoerdvisscher/one-liner/blob/master/src/Generics/OneLin… -- Sjoerd Visscher https://github.com/sjoerdvisscher/blog

1 0

How to implement nested loops with tail recursion?
by sdiyazg＠sjtu.edu.cn 19 Sep '12

19 Sep '12

I need to implement fast two-level loops, and I am learning using seq to make calls tail-recursive. I write programs to compute main = print $ sum [i*j|i::Int<-[1..20000],j::Int<-[1..20000]] This program (compiled with -O2) runs twenty times slower than the unoptimized (otherwise the loop gets optimized out) C version. But it seems to run in constant memory, so I assume that it has been turned into loops. #include <stdio.h> int main(){ int s=0; for(int i=1;i<=20000;++i){ for(int j=1;j<=20000;++j){ s+=i*j; } } printf("%d\n",s); return 0; } Then I write main = print $ f 1 where f i = let x = g 1 in x `seq` (x + if i<20000 then f (i+1) else 0) :: Int where g j = let x = i*j in x `seq` (x + if j<20000 then g (j+1) else 0) :: Int This version runs out of memory. When I scale the numbers down to 10000, the program does run correctly, and takes lots of memory. Even if I change the seqs into deepseqs, or use BangPatterns (f !i =... ; g !j = ...), the situation doesn't change. A monadic version import Control.Monad.ST.Strict import Control.Monad import Data.STRef.Strict main = print $ runST $ do s <- newSTRef (0::Int) let g !i !j = if (j<=10000) then modifySTRef s (+1)>>(g i (j+1)) else return () let f !i = if (i<=10000) then g i 1>>(f $ i+1) else return () f 1 readSTRef s also runs out of memory. So how can I write a program that executes nested loops efficiently?

3 6

ANNOUNCE: som-1.0
by Amy de Buitléir 19 Sep '12

19 Sep '12

Do you have some data that you'd like to understand better? I'm happy to announce a new package called som that may help: http://hackage.haskell.org/package/som https://github.com/mhwombat/som/wiki (wiki) A Kohonen Self-organising Map (SOM) maps input patterns onto a regular grid (usually two-dimensional) where each node in the grid is a model of the input data, and does so using a method which ensures that any topological relationships within the input data are also represented in the grid. This implementation supports the use of non-numeric patterns. In layman's terms, a SOM can be useful when you want to discover the underlying structure of some data. I have a brief tutorial in the wiki, which I hope to expand over the next few weeks.

1 0

ANNOUNCE: grid-2.0
by Amy de Buitléir 19 Sep '12

19 Sep '12

I'm happy to announce a new major release of the grid package: http://hackage.haskell.org/package/grid https://github.com/mhwombat/grid/wiki (wiki) WHAT'S NEW: The GridMap module provides ordered maps from tiles on a grid to values. This module is a wrapper around Grid and Map, in order to combine the functionality of grids and maps into a single type. This may be of interest to anyone developing a game based on a grid. ABOUT GRID: Grid provides tools for working with regular arrangements of tiles, such as might be used in a board game or self-organising map (SOM). Grid currently supports triangular, square, and hexagonal tiles, with various 2D and toroidal layouts. If you need a tile shape or layout that isn't currently provided, please let me know. See Math.Geometry.Grid for an example of how to use the package. Suggestions for improvement are welcome.

1 0

Choosing color of the track
by Manish Trivedi 18 Sep '12

18 Sep '12

Hi Folks, I am trying to plot two tracks with different colors. Following is my input file, ------ 2012-09-18 00:10:48,166 @CurrentPerHour13057 Red 2012-09-18 00:10:48,166 =CurrentPerHour13057 0.0 2012-09-18 00:10:58,155 =CurrentPerHour13057 0.0 2012-09-18 00:11:08,203 =CurrentPerHour13057 0.0 2012-09-18 00:11:18,166 =CurrentPerHour13057 0.0 2012-09-18 00:11:28,159 =CurrentPerHour13057 0.0 2012-09-18 00:11:38,170 =CurrentPerHour13057 0.0 2012-09-18 00:11:48,175 =CurrentPerHour13057 0.0 2012-09-18 00:11:58,174 =CurrentPerHour13057 0.0 2012-09-18 00:12:08,216 =CurrentPerHour13057 0.0 2012-09-18 00:12:18,218 =CurrentPerHour13057 0.0 2012-09-18 03:58:28,159 @PacingReqPerHr13057 Blue 2012-09-18 03:58:28,159 =PacingReqPerHr13057 2375.0534412521242 2012-09-18 03:58:38,161 =PacingReqPerHr13057 2375.383005739316 2012-09-18 03:58:48,175 =PacingReqPerHr13057 2375.713057258422 2012-09-18 03:58:58,160 =PacingReqPerHr13057 2376.0422443063935 2012-09-18 03:59:08,192 =PacingReqPerHr13057 2376.3730727321126 2012-09-18 03:59:18,207 =PacingReqPerHr13057 2375.9038854561304 2012-09-18 03:59:28,168 =PacingReqPerHr13057 2376.2324444615497 2012-09-18 03:59:38,156 =PacingReqPerHr13057 2376.5619853019184 2012-09-18 03:59:48,160 =PacingReqPerHr13057 2376.892145685344 2012-09-18 03:59:58,160 =PacingReqPerHr13057 2377.222265743067 ----- tplot -o /root/color.png -or 1024x768 -k 'CurrentPerHour' 'lines' -k 'PacingReqPerHr' 'lines' -if /root/color.input -tf 'date %Y-%m-%d %H:%M:%OS' I cant get to print plots in different color. Could anyone point out what am I doing wrong? Thanks, Manish

2 4

ANNOUNCE: MFlow-0.1.5
by Alberto G. Corona 18 Sep '12

18 Sep '12

Hi haskellers and specially the web developers. http://hackage.haskell.org/package/MFlow-0.1.5.3 MFlow is a is a Web framework with some unique, and I mean unique, characteristics that I find exciting: - It is a Web application server that start and restart on-demand stateful web server processes (not request.-response) This means that all the page navigation can be coded in a single procedure. This increases readability of the programmer code. I woul call it a anti-node.js. Buit usual request-response (stateless) server processes are also allowed - When the process is invoqued as result of an URL request, the Web app server not only restart the process but also recover its execution state. The enclosing Workflow monad provides the thread state persistence. There are state timeouts and process timeouts defined by the programmer. Processes with no persistent state (transient) are possible. -The user interface is made of widgets. They are formlets with added formatting, attributes, validations, modifiers and callbacks, that are composable, so the pieces are reusable and return type safe responses to the calling process. Even the links are part of widgets and return back type safe inputs at compile time to the calling server process. Tho glue these components, ordinary applicative combinators and other extra combinators are used. - The widgets and the communication don´t make assumptions about the architecture, so it can be adapted to non-web environments. This versions has interface for WAI-warp, Hack, Text.XHtml (xhtml) , and Haskell Server Pages. -The widget rendering can be converted to ByteStrings automatically with special combinators. A mix of widgets with different formats can be combined in the same source file. For example Text.Html and HSP (Haskell server pages) -These widgets can be cached, to avoid widget rendering on every interaction. -To handle the back button, and because the processes are stateful, they can run backwards until the response match. This is transparent for the programmer, thanks to the embedded FlowM monad. -All the code is in pure Haskell. No deployment, special scripts, formats etc are necessary. -Besides automatic state persistence, TCache provides transactions and user data persistence, that can be configured for SQL databases. Default persistence in files permit very rapid prototyping. Just code and run it with runghc. -Has AJAX support All of this sounds very complicated, but really it is simple!. Most of these things are transparent. The resulting code is quite readable and has very little plumbing! There is a non trivial example that some of these functionalities embedded here that you can run: http://hackage.haskell.org/packages/archive/MFlow/0.1.5.3/doc/html/MFlow-Fo… Take a look and tell me your opinion. I hope that you find it as exciting as me. I´m looking for people to collaborate in the development of MFlow. Although still it is experimental, it is being used in at least one future commercial project. So I have te commitment to continue its development. There are many examples in the documentation and in the package. Alberto

1 0

Type error with Type families
by Marco Túlio Pimenta Gontijo 18 Sep '12

18 Sep '12

Hi. I cannot make this program type check: {-# LANGUAGE TypeFamilies, FlexibleContexts #-} import qualified Data.ListLike as LL class LL.ListLike full (Item full) => ReplaceOneOf full where type Item full :: * replaceOneOf :: [Item full] -> full -> full -> full replaceOneOf from to list | LL.null list = list | x `element` from = LL.concat [to, replaceOneOf from to $ LL.dropWhile (`element` from) xs] | otherwise = LL.cons x $ replaceOneOf from to xs where x = LL.head list xs = LL.tail list element :: Item full -> [Item full] -> Bool The error message is: Line 9: 1 error(s), 0 warning(s) Could not deduce (Item full0 ~ Item full) from the context (ReplaceOneOf full) bound by the class declaration for `ReplaceOneOf' at /home/marcot/tmp/test_flymake.hs:(4,1)-(15,45) NB: `Item' is a type function, and may not be injective Expected type: [Item full0] Actual type: [Item full] In the second argument of `element', namely `from' In the expression: x `element` from I have tried using asTypeOf, but it did not work: {-# LANGUAGE TypeFamilies, FlexibleContexts, ScopedTypeVariables #-} import qualified Data.ListLike as LL class LL.ListLike full (Item full) => ReplaceOneOf full where type Item full :: * replaceOneOf :: Item full -> [Item full] -> full -> full -> full replaceOneOf xt from to list | LL.null list = list | (x `asTypeOf` xt) `element` from = LL.concat [to, replaceOneOf xt from to $ LL.dropWhile (`element` from) xs] | otherwise = LL.cons x $ replaceOneOf xt from to xs where x = LL.head list xs = LL.tail list element :: Item full -> [Item full] -> Bool Can someone point me to a solution? Greetings. -- marcot http://marcot.eti.br/

4 4

cost-centre names
by Marco Túlio Pimenta Gontijo 18 Sep '12

18 Sep '12

Hi. I have a question about cost-centre names, as shown on .hp files produced by +RTS -hc. They have the form A/B/C/D/E/F/G/... Usually, it seems that it means A, called by B, called by C, etc, but that's not the case sometimes. I have a case here (called with -L200): replaceOneOf’/clean/tagsText/anyTag/dropTagClose/parseObservations/specificTagText/tagText/parseOab/dropTagText/dropTill/tag/tagOpen... tagsText calls clean which calls replaceOneOf', but anyTag does not call tagsText. parseObservations calls dropTagClose which calss anyTag, but specificTagText does not call parseObservations. They seem to be grouped by three. Is this correct? How should I interpret it? Greetings. -- marcot http://marcot.eti.br/

2 2

Either Monad and Laziness
by oleg＠okmij.org 18 Sep '12

18 Sep '12

> I am currently trying to rewrite the Graphics.Pgm library from hackage > to parse the PGM to a lazy array. Laziness and IO really do not mix. > The problem is that even using a lazy array structure, because the > parser returns an Either structure it is only possible to know if the > parser was successful or not after the whole file is read, That is one of the problems. Unexpected memory blowups could be another problem. The drawbacks of lazy IO are well documented by now. > The behaviour I want to achieve is like this: I want the program when > compiled to read from a file, parsing the PGM and at the same time > apply transformations to the entries as they are read and write them > back to another PGM file. Such problems are the main motivation for iteratees, conduits, pipes, etc. Every such library contains procedures for doing exactly what you want. Please check Hackage. John Lato's iteratee library, for example, has procedure for handling sound (AIFF) files -- which may be very big. IterateeM has the TIFF decoder -- which is incremental and strict. TIFF is much harder to parse than PGM.

5 7

Dynamic Programming with Data.Vector
by Myles C. Maxfield 18 Sep '12

18 Sep '12

Hello, I've been writing dynamic programming (dp) algorithms in imperative languages for years, and I was thinking recently about how to use it in a Haskell context. In particular, I want to write a function that takes an ordered collection of items and produces a new item to insert into the ordered collection. The most straightforward way to do this would be to use a list, something like the following: recurse :: [Integer] -> [Integer] recurse l = newValue : recurse (take (length l + 1) infiniteList) where newValue = ... infiniteList :: [Integer] infiniteList = initialList ++ recurse initialList where initialList = ... solution :: Integer solution = infiniteList !! 5 I'm assuming that this can run fast because I'm assuming the 'take' function won't actually duplicate the list ([1] doesn't actually list the running time of 'take') Is this a correct assumption to make? Secondarily, and most importantly for me, I'm curious about how to make this fast when the computation of 'newValue' requires random access to the inputted list. I'm assuming that I would use Vectors instead of lists for this kind of computation, and [2] describes how I can use the O(1) 'slice' instead of 'take' above. However, both of Vector's cons and snoc functions are O(n) which defeats the purpose of using this kind of algorithm. Obviously, I can solve this problem with mutable vectors, but that's quite inelegant. Overall, I'm looking for a function, similar to Data.Vector's 'generate' function, but instead of the generation function taking the destination index, I'd like it to take the elements that have previously been constructed. Is there such a function? If there isn't one, is this kind of function feasible to write? If such a function doesn't exist and is feasible to write, I'd be happy to try to write and contribute it. [1] http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#g… [2] http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vect…

2 4