January 2015 - Haskell-Cafe

Re: [Haskell-cafe] Negable constraints on boolean normal forms
by Oleg Grenrus 02 Jan '15

02 Jan '15

I’ll try to find time to experiment with API and make a PoC in the beginning of the next week. Currently I have no idea what the API could be. It would be nice if it will turn out so you could do `CNF a -> NNF a` and `DNF a -> NFF a` transformations without any restrictions on `a`. Yet you still need `Negable a` to do reversed transformations as well as `CNF a <-> DNF a` Let’s see how it turns out. I’ll try to come back with something before Epiphany (i.e. on Monday). > On 01 Jan 2015, at 18:04, Yitzchak Gale <gale(a)sefer.org> wrote: > > Yes, sounds great! > > In practice, what I really need right now is to be > able to convert between normal forms without > contraints on the value type. If that will do it - > I'm happy. > > But beyond that, this is a nice library that is > well thought out. Grounded in good theory, but > still easily understandable and usable. Any > further development in that direction would of > course be appreciated! > > In terms of specifics - would we need replacements > for CoBoolean and CoBoolean1 if we move to > a richer lattice-based organization of the types? > Or would we then be able to move to simpler API like > toLattice, fromLattice, toNormalForm, etc. for the > conversions, that would just work? > > Thanks, > Yitz > > On Thu, Jan 1, 2015 at 5:45 PM, Oleg Grenrus <oleg.grenrus(a)iki.fi> wrote: >> First of all: nice to hear that someone is using boolean-normal-forms! >> >> I totally feel your pain. Indeed there is >> “Monoid is used, where Semigroup would be enough” issue. >> >> `Boolean` is too strong class there.. I’d like to rework >> the classes to have hierarchy: >> Lattice => Boolean >> Complementable >> Maybe also `Heyting` and `Negable`. >> >> Then NNF would be free Lattice, and DNF and CNF are also just lattices. >> >> With more granular classes, the requirements for transformations could be >> more precise. >> >> How does this sound? >> >> Cheers, >> Oleg >> >>> On 01 Jan 2015, at 17:06, Yitzchak Gale <gale(a)sefer.org> wrote: >>> >>> I've been using Oleg Genrus' wonderful boolean-normal-forms >>> library lately, and enjoying it. However, I'm running into >>> some trouble with overly constrained conversions. >>> >>> In theory, it's possible to convert between any of the >>> normal forms without requiring a Negable instance on >>> the value type. But the conversion mechanism in the >>> library routes everything via the Boolean type class, >>> and that ends up slapping a Negable constraint on everything. >>> >>> You can work around that by embedding your value type >>> in the free Negable, conveniently provided by the library. >>> But in practice that causes a lot of trouble. You end >>> up being required to deal with Neg cases in your result type >>> that are actually impossible to occur and make no sense >>> in context. You have to throw bottoms into provably total >>> functions, or write code that produces meaningless results >>> that you promise in human-readable comments will never >>> happen in practice. You also make the code less efficient >>> by requiring extra passes over the data to "verify" that Neg >>> isn't there. It's similar to what happens when you try to use >>> a Monoid where a Semigroup is really needed by bolting on >>> an artificial "empty" constructor. >>> >>> One thing you can do to begin with is to remove the >>> Negable constraints on the NormalForm instances; >>> I don't see that constraint ever being used. But that still >>> doesn't solve the main issue. >>> >>> Perhaps one approach would be to define a >>> Boolean "bi-monoid" class, where a Boolean bi-monoid >>> is a like Boolean algebra except without negation. >>> All of the normal forms are instances of Boolean bi-monoid >>> even without a Negable constraint on the value type. >>> >>> If you then relax the constraints on the methods of >>> CoBoolean and CoBoolean1 to Boolean bi-monoid instead >>> of Boolean, all of the existing conversion implementations >>> work without modification and without requiring the Negable >>> constraint. >>> >>> I'm not sure if that creates other problems for some other >>> use cases of this library though. >>> >>> Any thoughts? >>> >>> Thanks, >>> Yitz >>> >> >

1 0

GHC(STG,Cmm,asm) illustrated for hardware persons
by Takenobu Tani 02 Jan '15

02 Jan '15

Dear Haskellers, I love haskell. I'm studying and playing around with Haskell, GHC, STG, Cmm, asm... When I started studying them, I wanted some figures. I've not have some mental models because I am a hardware person. So I am drawing few illustrations for hardware persons. Here is: GHC(STG,Cmm,asm) illustrated for hardware persons http://takenobu-hs.github.io/downloads/haskell_ghc_illustrated.pdf https://github.com/takenobu-hs/haskell-ghc-illustrated If there are some misunderstandings or errors, please teach me. I'll correct or remove them. Thank you :-) I wish you a happy new year, Takenobu

10 11

Re: [Haskell-cafe] Weird reachability issue with haskell.org my my Italian ISP (fastweb)
by Alfredo Di Napoli 02 Jan '15

02 Jan '15

I ended up using a machine running privoxy (using aws or similar) and that works, but I'm not sure I want to pay for the idiocity of my ISP. Happy new year all, anyway. Alfredo Di Napoli > On 01/gen/2015, at 11:53, Giacomo Cosenza <mimmo.cosenza(a)gmail.com> wrote: > > Same thing here too. few weeks ago there were no problems. > mimmo > >> On Tuesday, December 30, 2014 8:26:15 PM UTC+1, george watkins wrote: >> Lo stesso, same thing here . >> I am using this mirror if for hoogle it can help https://www.fpcomplete.com/hoogle. >> At the beginnig i thought it was my dns improperly configured or something wrong with my network >> >> Il giorno martedì 23 dicembre 2014 18:55:00 UTC+1, Alfredo Di Napoli ha scritto: >>> >>> Hello Cafè, >>> >>> let me start with the email I've sent to Rackspace, which will help you understand the context: >>> >>>> Hi there! >>> >>>> I'm trying to understand how come I can't reach www.haskell.org from my ISP here in Italy (fastweb). In order to troubleshoot the issue, I tried dig on it, revealing it's hosted by you: >>> >>>> dig haskell.org >>> >>>> >>>> ; <<>> DiG 9.8.3-P1 <<>> haskell.org >>>> ;; global options: +cmd >>>> ;; Got answer: >>>> ;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 63629 >>>> ;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0 >>>> ;; QUESTION SECTION: >>>> ;haskell.org.INA >>>> ;; ANSWER SECTION: >>>> haskell.org. 299 IN A 23.253.242.70 >>>> ;; Query time: 139 msec >>>> ;; SERVER: 8.8.8.8#53(8.8.8.8) >>>> ;; WHEN: Tue Dec 23 18:33:00 2014 >>>> ;; MSG SIZE rcvd: 45 >>> >>>> Trying a whois reveals the subnet is the entire 23.253.0.0 one: >>> >>>> Rackspace Cloud Servers RACKS-8-1387376775861482 (NET-23-253-80-0-1) 23.253.80.0 - 23.253.95.255 >>>> Rackspace Hosting RACKS-8-NET-15 (NET-23-253-0-0-1) 23.253.0.0 - 23.253.255.25 >>> >>>> If I try to ping the IP directly, it obviously doesn't work, so I have tried contiguous IP addresses in the same subnet to see if the subnet itself was reachable at all.. trying 23.253.89.73 indeed worked! It resolved to >>>> http://www.papamurphys.com/ >>>> This means my ISP can reach that subnet, but doesn't explain why it can't connect to 23.253.242.70. >>> >>> >>> That's very weird indeed, as every other website is reachable, only haskell.org is not! How funny my fate is! I'm one of the few Haskellers in Italy and yet I cannot access the website.. perhaps is the consequence of "Avoid success at all costs"?? :) :) >>> >>> Jokes aside, do you guys know (I'm asking mainly to Austin here) if rackspace uses some weird setup for their website deployment or if haskell.org is hosted "the usual way" and listening on port 80? >>> >>> Thanks in advance for the 1% who is concerned, for all the other 99%, merry Xmas ;) >>> >>> Alfredo

1 0

Porting setlocale to Windows
by Sven Bartscher 02 Jan '15

02 Jan '15

Greetings, A while ago I took over the packages setlocale. I now would like to make it portable to windows, but came across the problem that LC_MESSAGES isn't defined on mingw. I thought about these options, for solving this: - Not defining LC_MESSAGES, which would mean, every package using LC_MESSAGES wouldn't be portable to windows. - Defining LC_MESSAGES as some an error, which would basically have the same problem as above. I don't like either of these solutions, but don't know any better. I would be happy about suggestions. Regards Sven

2 5

Re; ordNub
by Doug McIlroy 01 Jan '15

01 Jan '15

> I think the following computable function shows that it is always > possible (it chooses an order during queries): > Maintain a table, initially emtpy > As soon as (a <= b) is requested, see if a and b are already in > the table (using the computatble equality function) , if so, use > their ordering in the table. If an element is not in the table, add it. > Hence the table gives a consistent total order (it depends on which > ordering queries are requested, but that is not relevant?) This method has more than Gedanken value. Amusingly, I used it in "A killer adversary to quicksort" [Software - Practice and Experience 29 (1999) 341-344, http://www.cs.dartmouth.edu/~doug/mdmspe.pdf] to drive essentially any quicksort (illustrated with the C standard sort interface) into quadratic behavior. Doug McIlroy

1 0

Re: [Haskell-cafe] ordNub
by oleg＠okmij.org 01 Jan '15

01 Jan '15

Tom Ellis wrote: > Is there a type with an Eq instance for which on Ord instance could not also > be provided (i.e. I'm interested in Clark's "converse")? Of course. One of the very many examples is Complex. One can say we can compare complex numbers, by their absolute value. That is true; however we end up in a position where compare x y returns EQ but x==y returns False. In general, Ord represents total order. There are many structures on which total order cannot be established. Take nodes in the tree, the Tree data type. One can compare nodes by taking a parent to be less than any of its children. But then two brothers are not comparable. Searching for "partial orders" and pre-orders gives many more examples.

4 16

Negable constraints on boolean normal forms
by Yitzchak Gale 01 Jan '15

01 Jan '15

I've been using Oleg Genrus' wonderful boolean-normal-forms library lately, and enjoying it. However, I'm running into some trouble with overly constrained conversions. In theory, it's possible to convert between any of the normal forms without requiring a Negable instance on the value type. But the conversion mechanism in the library routes everything via the Boolean type class, and that ends up slapping a Negable constraint on everything. You can work around that by embedding your value type in the free Negable, conveniently provided by the library. But in practice that causes a lot of trouble. You end up being required to deal with Neg cases in your result type that are actually impossible to occur and make no sense in context. You have to throw bottoms into provably total functions, or write code that produces meaningless results that you promise in human-readable comments will never happen in practice. You also make the code less efficient by requiring extra passes over the data to "verify" that Neg isn't there. It's similar to what happens when you try to use a Monoid where a Semigroup is really needed by bolting on an artificial "empty" constructor. One thing you can do to begin with is to remove the Negable constraints on the NormalForm instances; I don't see that constraint ever being used. But that still doesn't solve the main issue. Perhaps one approach would be to define a Boolean "bi-monoid" class, where a Boolean bi-monoid is a like Boolean algebra except without negation. All of the normal forms are instances of Boolean bi-monoid even without a Negable constraint on the value type. If you then relax the constraints on the methods of CoBoolean and CoBoolean1 to Boolean bi-monoid instead of Boolean, all of the existing conversion implementations work without modification and without requiring the Negable constraint. I'm not sure if that creates other problems for some other use cases of this library though. Any thoughts? Thanks, Yitz

1 0

ordNub
by Niklas Hambüchen 01 Jan '15

01 Jan '15

tldr: nub is abnormally slow, we shouldn't use it, but we do. As you might know, Data.List.nub is O(n²). (*) As you might not know, almost *all* practical Haskell projects use it, and that in places where an Ord instance is given, e.g. happy, Xmonad, ghc-mod, Agda, darcs, QuickCheck, yesod, shake, Cabal, haddock, and 600 more (see https://github.com/nh2/haskell-ordnub) I've taken the Ord-based O(n * log n) implementation from yi using a Set: ordNub :: (Ord a) => [a] -> [a] ordNub l = go empty l where go _ [] = [] go s (x:xs) = if x `member` s then go s xs else x : go (insert x s) xs and put benchmarks on http://htmlpreview.github.io/?https://github.com/nh2/haskell-ordnub/blob/1f… (compare `nub` vs `ordNub`). `ordNub` is not only in a different complexity class, but even seems to perform better than nub for very small numbers of actually different list elements (that's the numbers before the benchmark names). (The benchmark also shows some other potential problem: Using a state monad to keep the set instead of a function argument can be up to 20 times slower. Should that happen?) What do you think about ordNub? I've seen a proposal from 5 years ago about adding a *sort*Nub function started by Neil, but it just died. (*) The mentioned complexity is for the (very common) worst case, in which the number of different elements in the list grows with the list (alias you don't have an N element list with always only 5 different things inside).

23 49

Proposed change to a couple Data.Tree functions
by David Feuer 31 Dec '14

31 Dec '14

Since you folks seem to know a lot about Data.Tree, I thought maybe you could take a look at https://github.com/haskell/containers/pull/126 and give me your thoughts. Does it look correct? Might it be efficient? David Feuer

1 0