May 2011 - Haskell-Cafe

How unique is Unique
by Emil Axelsson 30 May '11

30 May '11

Hello! Lacking a proper blog, I've written some notes about Data.Unique here: http://community.haskell.org/~emax/darcs/MoreUnique/ This describes a real problem that makes Data.Unique unsuitable for implementing observable sharing. The document also proposes a solution that uses time stamps to generate symbols that are "more unique". Does anyone have any comments on the proposed solution? Are there any alternatives available? Thanks! / Emil

6 10

Re: [Haskell-cafe] Haskell School of Expression (graphics)
by John Lato 30 May '11

30 May '11

> > From: michael rice <nowgate(a)yahoo.com> > I think this is fixed in the gtk2hs source tree, have you tried building from the repo? > cabal install gtk2hs-buildtools > darcs get --lazy http://code.haskell.org/gtk2hs/ > cd gtk2hs > chmod +x bootstrap.sh > ./bootstrap.sh John Lato > Is this worth chasing down? I loaded the Haskell Platform, which I assume > has some graphics capability (Cairo?). Maybe my time would be better spent > getting familiar with that? > > Michael > --- On Sun, 5/29/11, Andrew Coppin <andrewcoppin(a)btinternet.com> wrote: > > From: Andrew Coppin <andrewcoppin(a)btinternet.com> > Subject: Re: [Haskell-cafe] Haskell School of Expression (graphics) > To: haskell-cafe(a)haskell.org > Date: Sunday, May 29, 2011, 9:45 AM > > On 28/05/2011 08:06 PM, michael rice wrote: > > > /tmp/glib-0.11.22906/glib-0.11.2/Gtk2HsSetup.hs:190:70: > > Couldn't match expected type `[PackageDB]' > > with actual type `PackageDB' > > Expected type: PackageDBStack > > Actual type: PackageDB > > In the sixth argument of `registerPackage', namely `packageDb' > > In the expression: > > registerPackage > > verbosity installedPkgInfo pkg lbi inplace packageDb > > cabal: Error: some packages failed to install: > > cairo-0.11.1 failed during the configure step. The exception was: > > ExitFailure 1 > > There's some sort of glitch with Gtk2hs (on which SOE depends) that causes > it to not build with GHC 7.x (?) unless you hand-edit some of the files (!) > > http://hackage.haskell.org/trac/gtk2hs/ticket/1203

2 1

Detecting overlay-ed signal patterns
by Dmitri O.Kondratiev 30 May '11

30 May '11

Hello, I am trying to detect signal patterns in a system with numerous signals overlaying each other in time. I am aware that there is a whole class of problem solving methods for this task, yet trying my own algorithm, that may be wrong of course :) Next I use a simple example to describe the problem and my algorithm. Maybe someone will find this problem interesting enough to comment. Thanks in advance! In the following example signals from varying sources are represented by chars - unique signal = unique char. Examples of signal patterns (Pk) to detect: P1 = abcd P2 = 12345 Examples of a mixture of signals (pattern signals are underscored): M1 = s s n a_b_c_d_ r t 6 1_ 2_ 3_ 4_ 5_ 8 7 k l t M2 = g h a_ r 1_ w e 2_ j k b_ c_ l m p 3_ d_ 4_ e r 5_ v x M3 = ... MN = ... In the above examples two patterns P1 and P2 are interleaved with each other and other patterns. All mixtures are recorded for 24 hours for 12 month. One mixture corresponds to one 24 period (day). To find signal patterns in all these mixtures (M1, M2) my algorithm goes through these steps: 1) For every day: For every signal 'Y' create a list of 'weight pairs' such as: (Y, X1, 1), (Y, X2, 1), .. (Y, XN, 1) where X1, X2, ... XN are signals 'accessible from' (or following) signal 'Y' during this day So, for example, given the sequence: "abcde", chars in a left column of a table can access a list of chars in the right column: a | b c d e b | c d e c | d e d | e 2) For every signal sum all its 'weight pairs' for all days of the year: W(Y) = Sum((Y, Xk, 1), j=1... 364) For the above example, M1+ M2 will double the value of weight pairs in patterns: P1 = abcd P2 = 12345 such as: (a,b,2) (a,c,2) (a,d,2) (b,c,2) (b,d,2) (b,e,2) (c,d,2) (c,e,2) (d,e,2) and also: (1,2,2) (1,3,2) (1,4,2), (1,5,2) (2,3,2) (2,4,2) (2,5,2) etc... On the other hand, after summation M1+M2, weight pairs for other char sequences, that do not form patterns of often repeated signals, will not increase much. To demonstrate: M_1 and M_2 are sequences with repeating patterns being removed: M_1 = s s n r t 6 8 7 k l t M_2 = g h r w e j k l m p e r v x Here most pair weights will be small, same as before addition: (s,s,2) (g,h,1), (w,e, 1) ... 3) Compute weight of all possible chains in this year. Each chain consists of chars that can be accessed from one to another. Chars are examined, proceeding from the beginning of the sequence to its end, and never in the opposite direction. Going always in one direction and being bound with sequence end, makes chains finite. Chains for 'abcde' example will be: abcde, acde, ade, ae, bcde, bde, be, cde, cd, ce, de Weight of the chain is computed as a sum of its pairs: W(Ci) = Sum(Pj, j=1,..R) where R is a number of pairs that this chain is built from. For example for chain a 'acde' the weight will be: W('acde') = W(a,c)+ W(a,d) + W(a,e) 4) Split chains in groups by its length 5) For each group select chains with maximum weight. With pattern P1 = 'abcd' spread over some signal mixture, my algorithm will find (I hope) the following 4 classes of chains with maximum weight: 1) abcde, acde, ade, ae, 2) bcde, bde, be, 3) cde, cd, ce, 4) de In the same way, chains for pattern P2 = 12345 should be found. Thus, grounding on the idea of 'signal precedence' found in repeating pattern of several signals, and using pair 'weights' to mark signal chains - patterns are detected. Summation of pair weights allows to stress out, or highlight the repeating patterns. Inserting other signals inside a 'pattern pair' does not obscure it because in a long run (after many summations) its weight will make such pair stand out of the crowd. I have not yet fully developed this algorithm and have not tested it on big enough training sets. I hope it will work on training sets exhibiting some regularities - which in this case means repeating patterns. Of course it will not work on randomly generated data, where all pairs have approximately the same weight. Working with pairs and chains will allow for natural parallelism in processing huge sequences of events, I hope. It would be nice to use some analog of Hadoop map-reduce for this task. Any experience with Haskell analog of Apache Hadoop cluster (http://hadoop.apache.org/mapreduce/)? Does such thing exist in Haskell world at all? I would be happy to get criticism of my algorithm and comments on 'route-cause analysis' algorithms in general, thanks! Dmitri

1 0

Please help with double recursion
by Dmitri O.Kondratiev 30 May '11

30 May '11

Hello, I am trying to solve a simple task, but got stuck with double recursion - for some reason not all list elements get processed. Please advice on a simple solution, using plane old recursion :) *** Task: >From a sequence of chars build all possible chains where each chain consists of chars that can be accessed from one to another. For example, given the sequence: "abcde" In table below chars in a left column can access a list of chars in the right column: a | b c d e b | c d e c | d e d | e Then chains for this example will be: abcde, acde, ade, ae, bcde, bde, be, cde, cd, ce, de *** My incomplete result, which I get running my program (see at the end of this message): ('a','b'),('b','c'),('c','d'),('d','e'), -- abcde, ('c','e'), -- ce, ('b','d'),('d','e'), -- bde, ('b','e') -- be, ('a','c'),('c','d'),('d','e'), -- acde ('c','e'), ('a','d'),('d','e'), -- ade, ('a','e') -- ae Sequence 'abcde' contains 'bcde', 'cde', 'cd', 'de'. How to add all these sub-sequences as a separate sequences in my output? And I have 'ce' sequence duplicated, which I don't need. Also, how to output chains as a list of lists? Such as: [[abcde, acde, ade, ae,] [bcde, bde, be,] [cde, cd, ce,] de]] *** my code test = chains testPairs 'a' [] testPairs = pairs testSeq testSeq = "abcde" -- From a list of '((from,to),1)' pairs build char chains -- Char chain is a list of chars: [from1, to1 = from2, to2 = from3, to3 = from4, ...] -- 'pairList' - a list of pairs chains pairList from chainList = chainWrk (nextTo pairList from) from chainList where chainWrk [] from chainList = chainList chainWrk (to:tos) from chainList = chainWrk tos from (chains pairList to (chainList ++ [(from,to)])) -- Find direct neighbors for 'from' nextTo pairList from = toList (findPairs pairList from) [] -- From a list of '((from,to),1)' pairs build a list of 'to'-s toList [] tos = tos toList (((from,to),len):ps) tos = toList ps (tos ++ [to]) -- From 'pairList' find elements with 'from' equal to 'start' -- 'pairList' is a list of '((from,to),1)' pairs findPairs pairList search = filter (flt search) pairList where flt search ((from, to), len) = search == from -- From a sequence of chars buid a list of '((from,to),1)' pairs pairs [] = [] pairs (x:xs) = pairWrk x xs [] ++ pairs xs pairWrk hd [] pairLst = pairLst pairWrk hd (x:xs) pairLst = pairWrk hd xs (pairLst ++ [((hd,x),1)])

4 7

ANN: dtd-types 0.0.0.1
by Yitzchak Gale 30 May '11

30 May '11

The dtd-types package provides types for processing XML DTDs in Haskell. These types are intended to be compatible with and extend the set of types provided by John Millikin's xml-types package. This is a very preliminary first version, pending discussion by the community on the web-devel list about integration with xml-types, and any other issues that might come up. Hackage: http://hackage.haskell.org/package/dtd-types/ Darcs: http://code.haskell.org/dtd/dtd-types Enjoy, Yitz

1 0

Efficient object identity (aka symbols as data)
by Jacek Generowicz 30 May '11

30 May '11

[ TLDR: How do you do Lisp symbols in Haskell? ] What is the Haskell approach to efficient comparison and lookup of objects by their identity? Maybe a toy example would help to explain what I mean. Imagine that I want to use Haskell to maximize happiness in a situation where a bunch of people have to be assigned to certain groups according to their preferences, and some constraints on the group sizes. Conceptually my input data might be structured as follows: data Group = Group GroupName MaxGroupSize data Person = Person Name Group Group Group The program should partition the people into groups, attempting to get everyone into their most favoured groups. Whatever algorithm I choose to use for the optimization, will have to do lots of comparisons of Groups and Persons where their *identity* is all that matters: you don't need to look inside the objects. On the other hand, sometimes we will have to look inside the objects, for example in order to answer queries such as "Which group did Johnny get and how far down his list of choices did that group feature?". I should be able to run the program on data that becomes available at run time. The lisper in me is crying out for (lisp-like-)symbols which I can create from the input data at run time and on which some extra information can be hung. How would I organize something like this in Haskell? Thanks.

10 15

Iteratee stack-consumption
by Tony Morris 30 May '11

30 May '11

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I have written iteratees on the JVM, which does not include tail-call in its instruction set. They incur a stack frame per iteratee input, which can be expensive and unable to scale beyond a few thousand. Is there some trick to permitting this? Some sort of chunking the enumeratee or something? I was unable to find any good general hints in any of the hackage libraries. Thanks for any pointers. - -- Tony Morris http://tmorris.net/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk3jNHEACgkQmnpgrYe6r63QcACfSeZvvy+iYVisZ3e/dhWQd3D6 790AnRZCjJT6eCY21XlsVqcpTuamfuXY =ADo5 -----END PGP SIGNATURE-----

1 0

Re: [Haskell-cafe] State Machine and the Abstractions
by Chuzzle Guevero 29 May '11

29 May '11

For one, you have a kind error. You use Mission as a Monad when it only has kind *. I don't know much of arrows, but I suggest writing the combinators you want to have with specialized types, and see where that takes you. If it happens to lead to an implementation of Arrow, yay. If it doesn't, then you at least still have something that functions. > Message: 13 > Date: Fri, 27 May 2011 21:06:10 +0200 > From: Yves Par?s<limestrael(a)gmail.com> > Subject: [Haskell-cafe] State Machine and the Abstractions > To: Haskell-Cafe<haskell-cafe(a)haskell.org> > Message-ID:<BANLkTikVb-zhyTVR=jT03hFiBAKrERxsLQ(a)mail.gmail.com> > Content-Type: text/plain; charset="iso-8859-1" > > Hello, > > For the purposes of a simple strategy game, I'd like to build an EDSL that > expresses missions. A mission could be represented as a state machine. > With basic bricks such as actions (MoveTo, ShootAt...) or tests > (EnemiesAround, LowHealth...), I could (ideally dynamically) build some > strategic behaviors for the units. > I will take the example of a patrol. Applied to a unit (or a group of > units), it dictates : go from point 1 to point 2 and then go back and > repeat. But when you detect an enemy near, leave the patrol path, destroy it > and then resume your patrol where you left it. > > So if I consider my mission as a monad: > data Mission = MoveTo Point | ShootAt Unit > > patrol = do > MoveTo point1 > MoveTo point2 > patrol > > So far so good, but there, the only advantage to use a monad instead of a > list of MoveTo's is the do-notation. > And I lack the expression of tests. Using a GADT it could be: > > data Mission a where > MoveTo :: Point -> Mission () > ShootAt :: Unit -> Mission Bool -- If we have destroyed it or not > EnemiesAround :: Mission [Unit] -- The enemies that are maybe in sight > LowHealth :: Mission Bool -- If I should retreat > ... > > -- (Monad Mission could be nicely expressed using Heinrich Apfelmus' * > operational* package) > > patrol = do > MoveTo point1 > MoveTo point2 > enemies<- EnemiesAround > mapM_ ShootAt enemies > patrol > > Aaaaaaaand... here comes the trouble: the actions are done *sequentially*. > My units will move and then look at enemies, they will not monitor their > environment while they move. > So I need a way to say: A is your action of patrolling. B is your action of > surveillance. Do both in parallel, but B is preponderant, as if it successes > (if enemies are there) it takes over A. So, it is as if I was running two > state machines in parallel. > Moreover, the last line (the recursive call to patrol) is wrong, as it will > restart the patrol from the beginning, and not from where it has been left. > But this could be corrected by addind a test like "which point is the > closest". > > So I thought about Arrows, as they can express sequential and parallel > actions, but I don't know if it would be a right way to model the > interruptions/recoveries. > What do you think about it? Do you know of similar situations and of the way > they've been solved?

3 2

Utrecht Summer School in Applied Functional Programming
by João Paulo Pizani Flor 29 May '11

29 May '11

Hi dear Haskellers! I'm a senior undergraduate Computer Science student in Brazil, and have always loved Haskell and wrote most of my lab assignments and course projects in it. Haskellers are a very rare species here in Brazil, but I always tried my best to motivate people around me presenting some seminars, writing some tutorials, etc. My personal Haskell project: http://launchpad.net/presto What joy I had then last Friday, when I found out I've been accepted to participate in the Utrecht Summer School 2011, in the course "Applied Functional Programming in Haskell" (http://www.utrechtsummerschool.nl/index.php?type=courses&code=H9) In fact, I got a scholarship from Utrecht University that covers tuition fees and housing, but not the plane tickets to/from the Netherlands. That's the point where I need your advice: without some sort of financial support I won't be able to buy the tickets and travel to Utrecht. I am already searching from grants here in Brazil, but I think it will be hard to find something, not to say impossible. So, do you know any program/fund/foundation to which I can apply and get the needed financial support? Best regards, João Paulo Pizani Flor joaopizani(a)gmail.com Computer Science Federal University of Santa Catarina - Brazil

1 0

Escaping of string literals
by Michael Snoyman 28 May '11

28 May '11

Hi all, I'm working on a program right now that will involve embedding some static files inside my Haskell program as bytestrings. I've done this in the past with file-embed[1]. In this case, I have a strange requirement: I need to be able to modify the embedded data after the compiler has run. In general, I've gotten the code to work (and will soon be following up with a blog post explaining). But in this process, I ran into something I found interesting. If I run this program: {-# LANGUAGE TemplateHaskell #-} import Data.ByteString.Unsafe (unsafePackAddressLen) import Language.Haskell.TH.Syntax import qualified Data.ByteString as S main = do fromAddr <- unsafePackAddressLen 7 $(return $ LitE $ StringPrimL "123\0\&456") print fromAddr let fromStr = S.pack $ map (toEnum . fromEnum) $(return $ LitE $ StringL "123\0\&456") print fromStr I get the result: "123\192\128\&45" "123\NUL456" My understanding is that GHC is automatically escaping the non-ASCII characters in the strings. When I use StringL, GHC also automatically unescapes the bytes, so everything works as expected. In the case of StringPrimL, there is no point at which the unescaping occurs. I haven't been able to find the rules on how this escaping functions. Can anyone point it out to me? Also, for my case, it would be very useful to be able to bypass the escaping. I can easily do so with a post-process on the executable to embed raw bytes, but I'm wondering if there's some way to convince StringPrimL not to do any escaping. Thanks, Michael [1] http://hackage.haskell.org/package/file-embed

2 2