- Haskell-Cafe - Haskell.org

[Haskell-Cafe] Constructive Probability Theory and RandProc's σ-algebras
by Edward Kmett 07 Jul '11

07 Jul '11

On Sun, Jul 3, 2011 at 11:05 AM, David Banas <dbanas(a)banasfamily.net> wrote: > v0.4 of `RandProc` has just been posted to Hackage: > http://hackage.haskell.org/package/randproc [NB: I transfered this discussion from haskell to haskell-cafe, and started another thread] I have been spending some time exploring constructive probability theory in Haskell, and I have a couple of observations about working with random processes in a constructive setting: Necessarily because you are working in Haskell, a constructive setting, your σ-algebras can't be actual σ-algebras! =/ Notably, they aren't closed under *countable* union/intersection/complement, but merely finite union/intersection/complement, and Gray and Davisson's horrified objections from the bottom of page 39 on Random Processes applies: If a class of sets is only a field rather than a σ-field, that is, if it > satisfies only (3.1) and (3.2), then there is no guarantee that the class > will contain all limits of sets. Hence, for example knowing that a class of > sets contains all half-open intervals of the form (a,b] for a and b finite > does not ensure that it will also contain points or singleton sets! In fact, > it is straightforward to show that the collection of all such half-open > intervals together with the complements of such sets and all finite unions > of the intervals and complements forms a field. The singleton sets, however, > are not in the field. (See exercise 3.4) > Thus if we tried to construct a probability theory based on only a field, > we might have probabilites defined for events such as (a,b) meaning "the > output voltage of a measurement is between a and b" yet not have > probabilities defined for a singleton set {a} meaning "the output voltage is > exactly a." By requiring that the event space be a σ-field instead of only a > field, we are assured that all such limits are indeed events. This limitation, while from some perspective annoying is intrinsic to tackling the problem intuitionistically. Practically, this means you need to be careful when rederiving most of the later results, because you are limited to what you can prove in a constructive measure theory. In particular the approaches of YK Chan, Brian Weatherson, and Glenn Shafer to intuitionistic probability theory are probably appropriate reading. Personally, I don't think this is all that bad, we get some nice properties by being in a constructive setting. Weatherson noted that your measure becomes additive without problems from Dutch book arguments in an intuitionistic setting, because P(A v not A) is not necessarily 1! You may recall that recall that additivity would imply that P(A v B) = P(A) + P(B), given that A and B are disjoint, but that it tends to fall apart in classical probability theory. Intuitionistically, however, this is fine. That is to say that if you placed bets that payed out with market rate interest at a rational booking agent on both whether P = NP and P /= NP, it isn't just as good as having placed a bet on truth, because intuitionistically it is possible that neither of those bets may ever pay out, but in a classical setting P (P = NP v P /= NP) = P(True) = 1, so we lose additivity to gain the excluded middle. The cost of additivity is giving up or refining a lot of results from that text that talk about the limit of a random process. That and that the "σ-fields" in question are mere fields. ;) I am interested in exploring the consequences of this further. -Edward

2 1

Re: [Haskell-cafe] NLP libraries and tools?
by wren ng thornton 07 Jul '11

07 Jul '11

On 7/6/11 8:46 PM, Richard O'Keefe wrote: >> I've been working over the last year+ on an optimized HMM-based POS >> tagger/supertagger with online tagging and anytime n-best tagging. I'm >> planning to release it this summer (i.e., by the end of August), though >> there are a few things I'd like to polish up before doing so. In >> particular, I want to make the package less monolithic. When I release it >> I'll make announcements here and on the nlp@ list. > > One of the issues I've had with a POS tagger I've been using is that it > makes some really stupid decisions which can be patched up with a few > simple rules, but since it's distributed as a .jar file I cannot add > those rules. How horrid. I assume the problem is really that the trained model is in the jar and you can't do your own training? Or is this a Brill-like tagger where you really mean to add new rules? If an HMM-based tagger is amenable, you could try switching to Daniël de Kok's Java port of TnT: https://github.com/danieldk/jitar The tagger I'm working on does support being hooked up to a Java client (i.e., consumer of tagging info), but it's fairly ugly due to Java's refusal to believe in IPC. -- Live well, ~wren

1 0

Haskell Weekly News: Issue 189
by Daniel Santa Cruz 07 Jul '11

07 Jul '11

Welcome to issue 189 of the HWN, a newsletter covering developments in the Haskell community during the week of June 26 to July 2, 2011. It seems that it was a pretty quiet week in the mailing list. There were no significant announcements made, and the number of threads was low by comparison. Hope everyone is having a great week! You can find the HTML version at: http://contemplatecode.blogspot.com/2011/07/haskell-weekly-news-issue-189.h… Quotes of the Week * iwtu: [#haskell] is a good channel. Really. People are helpful and don't deserve killing or eating * [Cale] Finite dimensional vector spaces over a field F are algebras for the monad of F-linear combinations of elements of a set. [ivanm] oooohhhhh.... _now_ I get you! * [quicksilver] C++ templates can embed arbitrary computation at compile time [quicksilver] that alone tells you something about the complexity of the compiler [edwardk] yeah. they were accidentally turing complete. (whoops!) ;) [quicksilver] edwardk: OOPS I ACCIDENTALLY THE WHOLE TARPIT * bos: other companies use expensive firewalls and crypto hardware to protect their intellectual secrets. edwardk uses category theory! * ManuelChakravarty: After all, you can import any C function with a pure type which also allows you to wreak arbitrary havoc. We enable the user to disguise arbitrary machine code as a Haskell function of essentially arbitrary type. In comparison, `unsafePerformIO' seems angelic. * NihilistDandy: The best part of Haskell is that 80% of module names can be turned into clever blog titles. * AlanPerlis: We will never run out of things to program as long as there is a single program around. Top Reddit Stories * Here be dragons: advances in problems you didn't even know you had Domain: serpentine.com, Score: 78, Comments: 8 On Reddit: http://goo.gl/4RC1W Original: http://goo.gl/Pc0nd * A Gentle Introduction to Category Theory Domain: citeseerx.ist.psu.edu, Score: 33, Comments: 25 On Reddit: http://goo.gl/nb6yJ Original: http://goo.gl/ItUef * Step-wise evaluation of simple Haskell code to hpaste (via Stepeval) Domain: chrisdone.com, Score: 33, Comments: 4 On Reddit: http://goo.gl/VaPXN Original: http://goo.gl/NhWLC * Debugging compilers with optimization fuel Domain: blog.ezyang.com, Score: 30, Comments: 1 On Reddit: http://goo.gl/uUEct Original: http://goo.gl/tSk0e * Fully-Funded PhD Studentship in Functional Programming Domain: cs.nott.ac.uk, Score: 23, Comments: 5 On Reddit: http://goo.gl/Xa231 Original: http://goo.gl/zIvZe * Using Snap in Production! Domain: cdsmith.wordpress.com, Score: 21, Comments: 20 On Reddit: http://goo.gl/KgKxY Original: http://goo.gl/kZ5hp * Monads from Comonads Domain: comonad.com, Score: 19, Comments: 1 On Reddit: http://goo.gl/1yxKe Original: http://goo.gl/R9PyX * Haskell plugin for IntelliJ IDEA Domain: code.google.com, Score: 18, Comments: 7 On Reddit: http://goo.gl/DUiWy Original: http://goo.gl/H1goQ * Barnes & Hut simulator in Haskell! Domain: mortenlysgaard.com, Score: 16, Comments: 4 On Reddit: http://goo.gl/qTKlT Original: http://goo.gl/a5EAb * How do you deal with "long" function bodies? Domain: self.haskell, Score: 12, Comments: 29 On Reddit: http://goo.gl/sRQy0 Top StackOverflow Questions * Bentley-Ottmann Algorithm in Haskell? votes: 31, answers: 1 Read on SO: http://goo.gl/wyJNY * Haskell approaches to error handling votes: 22, answers: 3 Read on SO: http://goo.gl/I2dVG * is point free code more efficient, or just terser? votes: 16, answers: 2 Read on SO: http://goo.gl/em3uu * Are distinct open and close delimiters syntactically necessary? votes: 9, answers: 7 Read on SO: http://goo.gl/roNWE * How to persist large data for efficient deserialization in Haskell votes: 8, answers: 1 Read on SO: http://goo.gl/ixalr * Building with runtime flags using cabal and ghc votes: 6, answers: 1 Read on SO: http://goo.gl/UyrBs About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://www.reddit.com/r/haskell/comments/ic3qx/here_be_dragons_advances_in_… 2. http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-probl… 3. http://www.reddit.com/r/haskell/comments/icogq/a_gentle_introduction_to_cat… 4. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.7317&rep=rep1&t… 5. http://www.reddit.com/r/haskell/comments/iezj6/stepwise_evaluation_of_simpl… 6. http://chrisdone.com/posts/2011-07-02-stepeval-hpaste.html 7. http://www.reddit.com/r/haskell/comments/iacth/debugging_compilers_with_opt… 8. http://blog.ezyang.com/2011/06/debugging-compilers-with-optimization-fuel/ 9. http://www.reddit.com/r/haskell/comments/ie6by/fullyfunded_phd_studentship_… 10. http://www.cs.nott.ac.uk/~gmh/phd-advert.html 11. http://www.reddit.com/r/haskell/comments/iby54/using_snap_in_production/ 12. http://cdsmith.wordpress.com/2011/06/28/im-using-snap-in-production/ 13. http://www.reddit.com/r/haskell/comments/iao3l/monads_from_comonads/ 14. http://comonad.com/reader/2011/monads-from-comonads/ 15. http://www.reddit.com/r/haskell/comments/ib4zu/haskell_plugin_for_intellij_… 16. http://code.google.com/p/ideah/ 17. http://www.reddit.com/r/haskell/comments/idlza/barnes_hut_simulator_in_hask… 18. http://mortenlysgaard.com/wordpress/?p=17 19. http://www.reddit.com/r/haskell/comments/icelh/how_do_you_deal_with_long_fu… 20. http://stackoverflow.com/questions/6487632/bentley-ottmann-algorithm-in-has… 21. http://stackoverflow.com/questions/6537766/haskell-approaches-to-error-hand… 22. http://stackoverflow.com/questions/6494443/is-point-free-code-more-efficien… 23. http://stackoverflow.com/questions/6542724/are-distinct-open-and-close-deli… 24. http://stackoverflow.com/questions/6556042/how-to-persist-large-data-for-ef… 25. http://stackoverflow.com/questions/6505648/building-with-runtime-flags-usin…

1 0

Re: [Haskell-cafe] NLP libraries and tools?
by wren ng thornton 07 Jul '11

07 Jul '11

On 7/6/11 9:27 AM, Dmitri O.Kondratiev wrote: > Hi, > Continuing my search of Haskell NLP tools and libs, I wonder if the > following Haskell libraries exist (googling them does not help): > 1) End of Sentence (EOS) Detection. Break text into a collection of > meaningful sentences. Depending on how you mean, this is either fairly trivial (for English) or an ill-defined problem. For things like determining whether the "." character is intended as a full stop vs part of an abbreviation; that's trivial. But for general sentence breaking, how do you intend to deal with quotations? What about when news articles quote someone uttering a few sentences before the end-quote marker? So far as I'm aware, there's no satisfactory definition of what the solution should be in all reasonable cases. A "sentence" isn't really very well-defined in practice. > 2) Part-of-Speech (POS) Tagging. Assign part-of-speech information to each > token. There are numerous approaches to this problem; do you care about the solution, or will any one of them suffice? I've been working over the last year+ on an optimized HMM-based POS tagger/supertagger with online tagging and anytime n-best tagging. I'm planning to release it this summer (i.e., by the end of August), though there are a few things I'd like to polish up before doing so. In particular, I want to make the package less monolithic. When I release it I'll make announcements here and on the nlp@ list. > 3) Chunking. Analyze each tagged token within a sentence and assemble > compound tokens that express logical concepts. Define a custom grammar. > > 4) Extraction. Analyze each chunk and further tag the chunks as named > entities, such as people, organizations, locations, etc. > > Any ideas where to look for similar Haskell libraries? I don't know of any work in these areas in Haskell (though I'd love to hear about it). You should try asking on the nlp@ list where the other linguists and NLPers are more likely to see it. -- Live well, ~wren

5 6

(no subject)
by Ian Childs 06 Jul '11

06 Jul '11

Suppose I have two terms s and t of type "a" and "b" respectively, and I want to write a function that returns s applied to t if "a" is an arrow type of form "b -> c", and nothing otherwise. How do i convince the compiler to accept the functional application only in the correct instance? Thanks, Ian

3 7

Arrow instance of function type [a] -> [b]
by Markus Läll 06 Jul '11

06 Jul '11

Hi! Is it possible to define an Arrow instance of list to list functions? Something like import Control.Arrow import Control.Category type X a b = [a] -> [b] instance Category X where id = map Prelude.id g . f = g Prelude.. f instance Arrow X where arr f = map f first f = unzip >>> first f >>> uncurry zip The problem is that it's not allowed to use partially applied type synonyms. It is however possible to define a type synonym which value is a partially applied type, but I haven't been able to figure out if I could somehow use that fact in defining the X... Is it at all possible, or is a newtype the only way to do it? -- Markus Läll

4 3

Automatic Reference Counting
by Thomas Davie 06 Jul '11

06 Jul '11

Hi guys, Apple recently announced a new static analysis in Clang called ARC (Automatic Reference Counting). The idea is to provide what GC provides (zero memory management code by the programmer), but not to incur the runtime penalty of having to have the GC run. It seems to be extremely effective in objective-C land. I was wondering if any of the compiler gurus out there could comment on the applicability of this kind of analysis to Haskell. Dropping the GC and hence stopping it blocking all threads and killing parallel performance seems like nirvana. The one major problem that's still left with ARC is that it does not solve the retain cycle problem of reference counting. Programmers must insert a "weak" keyword to break cycles in their data graphs. Could even this analysis be automated statically? Could we put up with a language extension that added this annotation? I'd love to hear some comments from people more-experienced-than-I on this. Thanks Tom Davie

7 8

How to ensure code executes in the context of a specific OS thread?
by Jason Dagit 06 Jul '11

06 Jul '11

Hello, I'm trying to get some GUI code working on OSX and numerous forums around the internet keep reiterating that on OSX to correctly handle GUI events you need to use the original thread allocated to your process to check for events and to call the Cocoa framework functionality. Specifically, using a secondary thread (even a bound thread) is not sufficient with the Cocoa framework. I looked at the threading documentation in Control.Concurrent for GHC and it's not clear to me if this is even possible with GHC without restricting to the non-threaded RTS. This means that using the GUI library from GHCI is not an option and using multiple OS threads in the final application is also not possible. This means that some FFI libraries will be unusable. My main question is, is there a way around this so that I could, for example, use the library from GHCI? My second question is, if there is no current workaround then how can we remedy this situation? It seems like there could be an api function like: runOnOriginalThread :: IO a -> IO a This function would be similar to runInBoundThread except it would be guaranteed to run on the original thread allocated to the ghc/ghci process. I believe the above primitive would be sufficient. I'll worry about filing a bug or making a libraries proposal after I have a better understanding of what must be done. Thanks, Jason

6 13

Re: [Haskell-cafe] How to ensure code executes in the context of a specific OS thread?
by John Lato 06 Jul '11

06 Jul '11

Message: 23 > Date: Wed, 06 Jul 2011 10:14:56 +0100 > From: Simon Marlow <marlowsd(a)gmail.com> > Subject: Re: [Haskell-cafe] How to ensure code executes in the context > of a specific OS thread? > To: Jason Dagit <dagitj(a)gmail.com>, cvs-ghc(a)haskell.org, Haskell > Cafe > <haskell-cafe(a)haskell.org> > Message-ID: <4E142790.8090009(a)gmail.com> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > > On 05/07/2011 20:33, Ian Lynagh wrote: > > On Tue, Jul 05, 2011 at 08:11:21PM +0100, Simon Marlow wrote: > >> > >> In GHCi it's a different matter, because the main thread is running > >> GHCi itself, and all the expressions/statements typed at the prompt > >> are run in forkIO'd threads (a new one for each statement, in fact). > >> If you want a way to run command-line operations in the main thread, > >> please submit a feature request. I'm not sure it can be done, but > >> I'll look into it. > > > > We already have a way: -fno-ghci-sandbox > > Aha, I'd forgotten about that! Thanks Ian. > > Simon > IIRC a lot of people have had trouble running GUI apps from within GHCi on OS X, whether they're GLUT, Gtk2hs, WxHaskell, or native, and several users consider this a large obstacle. I know that I haven't been successful with gtk2hs. However, at this suggestion I just tried running a gtk2hs app I'm developing with the -fno-ghci-sandbox flag, and it worked perfectly. Thanks very much, Ian. John L.

1 0

Re: [Haskell-cafe] function terms
by oleg＠okmij.org 06 Jul '11

06 Jul '11

Ian Childs wrote: > I have a function that returns a witness to 's :: Term a' and 't :: > Term b' having the same type, if they do, but I am wondering how to > extend this to the first argument of an arrow type. Basically you have to write the deconstruct that takes (TRepr a), the witness for type a, and returns either Nothing or Just (exists b1 b2. (EQ a (b1->b2), TRepr b1, TRepr b2)) That is, if the type a is indeed an arrow type, you return the triple: the witnesses for the argument and the result types and the witness for the equality of a and b1->b2. Problems like these often occur in type-checking (or in de-serialization of a typed term from an untyped representations). The following page discusses two (GADT and GADT-less) solutions: http://okmij.org/ftp/tagless-final/course/course.html#type-checking Specifically, http://okmij.org/ftp/tagless-final/course/Typ.hs defines such an arrow witness, names `AsArrow'. Both approaches are essentially equivalent -- and both are quite complex. It really takes a couple of hours to explain either of them. I don't believe a simple solution exists.

1 0