May 2017 - Haskell-Cafe

data mining, or something like it
by Dennis Raddle 31 May '17

31 May '17

I have a general computer science question first, and then I will ask if Haskell might be helpful for this. I'm researching "algorithmic music composition," the construction of musical compositions through choices made my algorithms. No piece of music is ever 100% human-composed or 100% algorithmic -- so to be more clear, I'm interested in researching "musical fitness functions" that produce good results when searching the music space. Anything the computer composes will be listened to by me, and only the most promising fitness functions will be explored in greater depth. So my general question is about the following idea -- So in the course of generating lots of musical examples, and rating them as "good" or "bad," I'll end up with a database that can perhaps be "mined" for new fitness functions. I would start with a question. A random example of a question would be "is there a pattern in the density of dissonance, such that more dissonance in certain places in the composition tends to make it better (or worse)?" I would suspect, out of pure intuition, that it does, but I may not know the exact details. For instance, I might not know if dissonance matters more in certain places within a measure. So I could code up something that looks for patterns among the good and bad musical examples in my database to see if it can find something specific. So is this called "data mining" or something else? Second, are there any Haskell libraries that can help with this task? Thanks, D

3 3

is 'stack ghci' really experimental?
by Dennis Raddle 31 May '17

31 May '17

I noticed that the stack docs say 'stack ghci' is experimental. I assume it's a common need (certainly is for me) to interpret my code while developing. Is it safe to use 'stack ghci' or is there another way that is more robust? D

3 3

ANN: network-2.6.3.2
by evan＠evan-borden.com 31 May '17

31 May '17

Announcing network-2.6.3.2 This release includes many improvements to documentation and infrastructure as well as a few API additions. As always a huge thank you to the network contributors. Version 2.6.3.2 * Zero memory of `sockaddr_un` if abstract socket [#220](https://github.com/haskell/network/pull/220) * Improving error messages [#232](https://github.com/haskell/network/pull/232) * Allow non-blocking file descriptors via `setNonBlockIfNeeded` [#242](https://github.com/haskell/network/pull/242) * Update config.{guess,sub} to latest version [#244](https://github.com/haskell/network/pull/244) * Rename `my_inet_ntoa` to avoid symbol conflicts [#228](https://github.com/haskell/network/pull/228) * Test infrastructure improvements [#219](https://github.com/haskell/network/pull/219) [#217](https://github.com/haskell/network/pull/217) [#218](https://github.com/haskell/network/pull/218) * House keeping and cleanup [#238](https://github.com/haskell/network/pull/238) [#237](https://github.com/haskell/network/pull/237)

1 0

Re: [Haskell-cafe] Type-level GCD [Instance Chains]
by J. Garrett Morris 31 May '17

31 May '17

[Apologies for breaking threading...] On Wed May 31, Anthony Clayden <anthony_clayden at clear.net.nz> wrote: > Leaving aside the question of backtracking on instance > non-match, > would anybody write a type-level GCD like this? Your question seems to be "would you use the standard recursive statement of Euclid's algorithm to demonstrate Euclid's algorithm?" This certainly seemed to be a reasonable idea in 2010. If your concern is efficiency, I suggest that not using Peano numerals at all is probably a more profitable direction. > (And Subt needs a nasty kludge in case you're trying to > subtract the larger: it returns Z.) What you call a nasty kludge, I call a standard operation on commutative monoids. [https://en.wikipedia.org/wiki/Monus] > I think these days (esp with TypeFamilies/Assoc types), You seem to be discovering that closed instance chains can be implemented by writing out truth tables. I discussed this transformation at length, and suggested that doing might make your code harder to write and to read, in my Haskell 2015 paper "Variations on Variants". Of course, you'll have an easier time of it if you limit yourself to only considering type-level definitions, and not the corresponding method definitions. But doing so rather misses the point of instance chains. /g -- Prosperum ac felix scelus virtus vocatur -- Seneca

1 0

Type-level GCD [Instance Chains]
by Anthony Clayden 31 May '17

31 May '17

I'm re-reading the Instance Chains paper. http://dl.acm.org/citation.cfm?id=1863596 [2010, so before Type Families got off the ground] And wondering about some of [*] their motivating examples. [Disclaimer: with a view to writing up something I think is better.] Leaving aside the question of backtracking on instance non-match, would anybody write a type-level GCD like this? We have the usual type-level Naturals and Booleans: > {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, > OverlappingInstances, EmptyDataDecls #-} > > data Z; data S n > > data T; data F And then: > class Gcd m n p | m n → p --p=gcd(m,n) > instance Gcd m m m -- OVERLAPPABLE OK > instance (Lte n m T, Subt m n m', Gcd m' n p) > ⇒ Gcd m n p > instance (Lte n m F, Subt n m n', Gcd m n' p) > ⇒ Gcd m n p Those latter two instances overlap (heads are identical) in an irresolvable way. (They're trying to distinguish the `m > n` vs `m < n` cases.) The code is closely following how you might write with Integers, I guess. But I'm not convinced it's such a good approach for Peanos. Class Lte compares two Peanos, tells which is the larger. Class Subt subtracts one from the other. They're both traversing the (S (S (S ... Z...))) nesting. (And Subt needs a nasty kludge in case you're trying to subtract the larger: it returns Z.) I think these days (esp with TypeFamilies/Assoc types), I'd write those latter two instances with a case helper. And a discriminator type fun `Diff` that provides the absolute diff, and tells which param is smaller. But to keep in the same style, I'll put `Diff` as a class: > instance (Diff m n d, GcdCase d m n p) > => Gcd m n p -- single 'catch all' instance > > class GcdCase d m n p | d m n -> p > instance (Gcd d' n p) > => GcdCase (T, d') m n p > instance (Gcd m d' p) > => GcdCase (F, d') m n p > > class Diff m n d | m n -> d > instance Diff Z (S n') (T, S n') > instance Diff (S m') Z (F, S m') > instance (Diff m' n' d) => Diff (S m') (S n') d Seems to me the code is more succinct, and easier to follow. (And by the way doesn't need egregious overlaps.) [*] Actually, I'm dubious about all of their examples. More to follow ... AntC

1 0

Re: [Haskell-cafe] [ghc-proposals/cafe] Partially applied type families
by Anthony Clayden 30 May '17

30 May '17

> On Mon May 15 16:20:09 UTC 2017, Richard Eisenberg wrote: > Lots to respond to! > Thanks Richard, phew! yes. Let's break it down a bit. > I do think think there's one overarching question/theme > here: Do we want functional dependencies or type-level > functions? Behind AntC's arguments, I see a thrust toward > functional dependencies. (Not necessarily their *syntax*, > but the idea of type improvement and flexible -- that is, > multidirectional -- type-level reasoning.) My dependent > types work pushes me toward type-level functions. Yes there is an overarching question. I don't think it's specifically FunDeps vs Type Functions. (Although I disagree the **Functional** Dependencies are somehow not "functional". Yes Mark Jones got the idea from Relational database theory. Where did Ted Codd get the idea from? Mathematical (binary) "relations", which are a set-theoretic account of, um, functions.) "Multidirectional type-level reasoning" is what all functional languages do: from Robinson's unification to Hindley-Milner to OutsideIn(X) to System F-subscript-superscript. There's been an example in Haskell's Prelude since ~1991: the `read` method's return type is 'demand-pulled' from context, not 'supply-pushed' from its parameter. Similarly if I write: > x :: Int > x = a + (b * c) We infer a, b, c must all be Int. Perhaps in another universe, Haskell had explicit type application from day 1, and insisted on giving type signatures for all vars (like nearly all procedural/OO languages). But we aren't in that universe, and I love Haskell/FP for being both type-safe and not pernickety in that way. > ... [big snip - I'll reply separately] > > I expect AntC would prefer disequality guards > over closed classes. Oh yes! I was about to say (repeating my earlier message): if we're going to ground type family instances in classes, then we need a way to distribute type instances as associated types, unless ... you're going to suggest something daft like closed classes. And then you did. > I would be interested to hear more from the > community on this choice -- they're really the same as > ordered equations under the hood, and it's just a choice > of syntax. Maybe we can even have both. > Yes please all chip in. There were strong views expressed 5~8 years ago. My two-penn'orth: I think we can mechanically translate closed equations to guards (equality and 'apart' tests). The example in my earlier post tried to show how. For class instances (with overlaps), I think there's also a mechanical translation, but only for 'well-behaved' sets of instances. (For Incoherent sets we don't have a chance.) And of course as soon as some imported instance overlaps, we have to start again to assess well-behavedness. > Now, on to individual points: > > ...the Hard Thought in order to be > backward compatible. (This backward compatibility > necessity is one of the reasons I love working with > Haskell. When adding a feature to the language, we just > can't take easy ways out!) > The backwards-compatibility I particularly want to preserve is "distributed instances". That is, putting the instance code close to type decls and other functions that build or consume that type. I also want to put explicitly *in the instance decl* the restraints on what types that instance applies for. Not implicit from where it appears in a closed but lengthy/voluminous sequence of equations. Yes there must be global coherence for the class/type instances. That's a mechanical check which compilers are good at, but humans not so much. > ... it was awkward to describe the overlap between two > branched instances. AntC might argue that, if we just had > disequality guards, it would all be much simpler. He might > be right. I'd argue it's simpler to understand each instance on its own grounds. Although a bunch of guards can get quite complex. (There was Andy A-M's example back in 2013.) The cumulative effect of the preceeding equations in the closed family is more complex. IMO. > > In retrospect, it would have been nice to have the > proposals process active when designing closed type > families; we might have come up with a better design. > There was a huge and rather repetitive (unfortunately) discussion in several rounds 2009~2012, somewhat prompted by trying to 'fix' the Haskell 2010 standard. So that we could include MPTCs in the standard. But you can't have MPTCs without FunDeps or Type Families, or without agreeing a position on overlaps. (good luck with that!) So although MPTCs were in both GHC and Hugs before 1998, they're still not 'official' >sigh<. MPTC's omission for Haskell2010 is what I meant by: > > we've lost 7~8 years of opportunity. > > My recollection at the time [of developing closed Families] > is that other approaches were > more functional-dependency-like in character. (To wit: > instance chains.) I wish Martin Sulzmann could have been more active at the time. (He occasionally expresses the intention of getting back into Haskell.) Instance guards are really a continuation of the CHR approach. So fit nicely into whole-of-program inference with type improvement. [I dislike the non-distributivity of instance chains for the same reason I dislike closed families. Although instance chains do have some nice features. Instance guards give me that feature more directly. Whereas closed type families don't give that feature at all.] > When I did the closed type family work, > I was thinking that type families were better than > functional dependencies; now, my view is much more nuanced > (leaning strongly toward fundeps instead of partial type > families). > I'm a little unsure what you mean at the top of the post about the "idea" of FunDeps vs their specific syntax. I can simulate FunDeps with superclass constraints using Type Funs and Equality constraints. This even achieves multi-directional improvement. Is that what you want to include? It took me a long time to realise this works out better than the FunDeps arrow business, especially with overlaps. The dreaded "Instances inconsistent with FunDeps" error is a devil to fiddle with. And often ends up breaking the coverage condition. [As Iavor frequently points out.] Martin pointed out that breaking coverage (using UndecidableInstances) is not as 'safe' as SPJ had been assuming. > > > I don't see what's so hard [about non-unifiability]. > > It's not nearly as hard from a fundep point of view. ... > ... [another big snip: thanks for the pointer to the paper.] > > I do have to say all this talk has made me think more > about apartness constraints in FC, at least. They might be > a touch simpler than the current story. > I think apartness is the criterion that's always applied to resolve instance selection under overlaps. The trouble is that the semantics for overlap has never been spelled out. (Nor, I suspect the criterion for a 'well-behaved' set of instances. I can volunteer that for you.) Apartness does not intrude inside constraints in the class/instance contexts, nor inside the body of a class instance/methods. It might help with instance selection wrt the rhs of type instance equations. AntC

3 3

Re: [Haskell-cafe] [ghc-proposals/cafe] Partially applied type families
by Anthony Clayden 30 May '17

30 May '17

> On Wed May 24 02:33:46 UTC 2017, Richard Eisenberg wrote: > ... > Thanks for getting me to think about all this > in a new way! Thanks Richard, yes I think we have large areas of agreement. So I'll cut to where we differ. > > > On May 15, 2017, at 9:26 PM, Anthony Clayden wrote: > > "Multidirectional type-level reasoning" is what all > > functional languages do: from Robinson's unification > > to Hindley-Milner to OutsideIn(X) > > to System F-subscript-superscript. > > I disagree here: the dependently typed languages don't > quite do this. Then I guess I remain to be convinced of the value of dependent typing within Haskell. > ...These languages still do multi-directional type inference, I guess you mean as needed for superclass constraints and instance constraints, so perhaps there's no practical difference. > > > > The backwards-compatibility I particularly > > want to preserve is "distributed instances". > > That is, putting the instance code > > close to type decls and other functions that > > build or consume that type. > > I think one other key difference between our viewpoints is > that I view the whole idea of "type instance" to be a bit > backward: I view type families as type-level functions. > Like other functions, I want the defining equations to be > all in one place. I'd like term-level functions to be more like instances. That is, with the equations distributed, see your example below. (Yes the set of equations must be coherent overall. That's something the compiler can check for me.) > > This isn't to argue that my viewpoint is right or that > other viewpoints are wrong. It's just a way to understand > why we both see things the way we do. Yes. > > > I'd argue it's simpler to understand each instance > > on its own grounds. > > Permit me to rewrite your sentence to something that > resonates better with me: > > > I'd argue it's simpler to understand each *equation* > > on its own grounds. > > I agree here, but it's a bit subtler. > We aren't confused when we see > > > f [] = False > > f _ = True Oh, yes I think a lot of people are confused. I think they expect the second equation is equivalent to: > f (x:xs) = True Maybe even > f ~(x:xs) = True But in the presence of bottom, that's a dangerous delusion. I'd say: if you want the True result to mean there's a non-empty list, then put that explicitly. And then we have two equations that are 'apart'. And they don't need to be sequential. Furthermore that delusion is doubly dangerous for type equations, because GHC knows nothing of closed Data Kinds. > > There was a huge and rather repetitive (unfortunately) > > discussion in several rounds 2009~2012, > > These dates might help to explain why I may be repeating > old arguments. I became active in the community somewhere > > in 2012. No, you're not repeating old arguments. Type Families, and esp. CTFs really came later. IIRC, at the time, there was a lot of suggestions, but not much push-back from anybody disagreeing. There was some doubt whether there could be a type-level disequality test. Chiefly GHC HQ just ignored the whole thing. Somebody at the time did try to write it up (viz. moi) https://ghc.haskell.org/trac/ghc/wiki/NewAxioms/DiscussionPage And someone from GHC HQ (viz. you) did acknowledge it rather later. > > I'm a little unsure what you mean at the top of the post > > about the "idea" of FunDeps vs their specific syntax. > > By "idea", I mean traits like multidirectionality and > attachment to classes. I maintain that the > function-application syntax of type families is better > than the relational syntax of fundeps. > OK I think you're saying that a class decl with superclass (~) constraints to type functions is preferable/more aesthetic. I agree. Furthermore overlap interferes with fundeps (or perhaps I mean v.v.) in horrible ways. > ...I'm not sure we need to allow ~ guards. > (I think allowing them would cause confusion, with > many people asking about the difference between an > equality constraint and an equality guard. Yes I can see the dangers of confusion. We could of course use a different operator. > ... They're different, but I think the equality guard is useless I see two main uses/benefits: 1. avoids the need for non-linear patterns in the head 2. visually points up the 'non-apartness' vs an, um. "apartness guard" (When I was figuring out Andy A-M's 2013 example, I rewrote the non-linear patterns with ~ guards, so I could figure out the apartness guards esp for the semi-apart instances. I posted the later workings to your blog https://typesandkinds.wordpress.com/2013/04/29/coincident-overlap-in-type-f… ) > [except as a type-level "let", I suppose].) No, they're not doing that: deliberately I don't allow guards to introduce new type vars. > ... partial type families ... > Of course, when you protect a > partial type family by a class constraint, then it's not > troublesome: that's the point of the Constrained Type > Families paper. Yes I got that loud and clear, and I agree. So the remaining issue is _how_ to protect them. > > > Sometimes I deliberately want there to be no instance > > for some specific pattern. > > Indeed yes. And now you can, with TypeError > (https://ghc.haskell.org/trac/ghc/wiki/Proposal/CustomType > Errors, which is now available in GHC 8). Ok thanks, yes that helps. Nevertheless it seems disergonomic to write an instance for a type-equal case, even with a helpful error message; when what you want is: no such instance. > > Bottom line: You win. I'm convinced. Apartness guards > (feel free to fight me on the name here -- I don't feel > strongly, but somehow I like "apartness guards" more than > "disequality guards") subsume OverlappingInstances (when > the author of the instances has a particular desired way > to resolve overlap) and closed type families. I think that > the syntax of closed type families is often what the user > wants, but I admit that CTFs don't cover all scenarios, > especially in the context of Constrained Type Families. So > I think we should keep CTFs (for now -- until Dependent > Haskell is here) but add this new syntax as well, which > would subsume the newly-proposed closed type classes. I've been (mostly in my head) calling them "Instance Guards", because I want both an eq guard and an apartness guard. > > Even better, I think apartness guards would be very easy > to implement. All the plumbing is already installed: we > basically just have to add a switch. > Yes that's what I guessed from your write-up of CTFs and "coincident overlap". What I can see will be awkward is backwards compatibility: can a class/type family with guards coexist with CTFs and with classes using overlap? > Next step: write a ghc-proposal. I'll support it. If I had > the time, I'd even implement it. I'll have a crack at the proposal. But implementing it is entirely beyond me. So thanks for saying "you win". But I'm not celebrating 'til something actually happens. (Been bitten too many times.) AntC

3 2

Re: [Haskell-cafe] Haskell performance when it comes to regex?
by Chris Dornan 30 May '17

30 May '17

Brandon Allbery allbery.b(a)gmail.com: > TDFA is pure Haskell and mostly exists for when you can't be certain that a faster C binding will support UTF8 > (most POSIX regex implementations do not, and PCRE only does so if someone built it with UTF8 support). > When it's usable, the C bindings will almost always be faster. I think we are in agreement, though I would generally recommend TDFA, unless you need the highest performance (as in this case) or Perl-style REs. But then again I like my REs plain and simple (and Posix) and packages with as few external dependencies as possible. Chris

2 1

Re: [Haskell-cafe] Haskell performance when it comes to regex?
by Chris Dornan 30 May '17

30 May '17

Hi Bram, Sorry for being a bit late to this -- I have been on the road. I have switched over you example to pre-compile the REs and use ByteString and can see 13x speedup on scan and a 9x speedup on mapping. Curiously, nearly all of that speedup seems to be gained by lifting the RE compilation out of the loop but I am pretty sure there are gains to be had from re-writing the loops. Do you have the Python code that was performing 80x better? Chris From: Alfredo Di Napoli <alfredo.dinapoli(a)gmail.com> Date: Monday, 22 May 2017 at 08:48 To: Bram Neijt <bneijt(a)gmail.com> Cc: Станислав Черничкин <schernichkin(a)gmail.com>, haskell-cafe <haskell-cafe(a)haskell.org>, Chris Dornan <chris(a)chrisdornan.com> Subject: Re: [Haskell-cafe] Haskell performance when it comes to regex? Hi Bram, you might be interested in the “regex” package from my colleague Chris Dornan: http://regex.uk/ I know some proper performance work still needs to be done, but I would be curious to hear your experience report ;) Alfredo On 19 May 2017 at 18:52, Bram Neijt <bneijt(a)gmail.com> wrote: Thank you! I already changed to Text instead, but I thought the regex was already memoized by GHC, so that should not be a problem. I'm trying regex-applicative now, maybe that will help, but it takes some time to figure out the syntax. I'll also try to see if precompilation helps. Greetings, Bram On Fri, May 19, 2017 at 1:17 PM, Станислав Черничкин <schernichkin(a)gmail.com> wrote: > Try to use Text or ByteString instead of strings. Try to use compile and > execute methods > (http://hackage.haskell.org/package/regex-tdfa-1.2.1/docs/Text-Regex-TDFA-By…) > make sure regex get compiled once. > > 2017-05-16 12:12 GMT+03:00 Bram Neijt <bneijt(a)gmail.com>: >> >> Dear reader, >> >> I decided to do a little project which is a simple search and replace >> program for large text files. >> >> Written in Haskell, it does a few different regex matches on each line >> and stores them in a leveldb key-value store to create a >> consistent/reviewable search-replace index. It should provide for some >> simple/brute-force anonymization of data and therefore I called it >> hanon (sorry, could not think of a better name). >> >> https://github.com/BigDataRepublic/hanon >> >> The code works, but I've done some benchmarking to compare it with >> Python and the code is about 80x slower then doing the same thing in >> Python, making it useless for larger data files. >> >> I'm obviously doing something wrong. >> >> Could you give me tips on improving the performance of this code? >> Probably mainly looking at >> >> https://github.com/BigDataRepublic/hanon/blob/master/src/Mapper.hs >> >> where the regex code lives? >> >> Greetings, >> >> Bram >> _______________________________________________ >> Haskell-Cafe mailing list >> To (un)subscribe, modify options or view archives go to: >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe >> Only members subscribed via the mailman list are allowed to post. > > > > > -- > Sincerely, Stanislav Chernichkin. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

4 4

Re: [Haskell-cafe] Haskell performance when it comes to regex?
by Saurabh Nanda 30 May '17

30 May '17

Sorry for jumping in. IIUC the largest speedup was delivered by moving a reger compilation expression out of a loop. If the regex compilation is a pure function, being passed the exact same arguments during every invocation of the loop, shouldn't the compiler be smart enough to optimise it? Isnt this the basic premise of pure FP? On 30-May-2017 2:20 AM, "Brandon Allbery" <allbery.b(a)gmail.com> wrote: On Mon, May 29, 2017 at 3:53 PM, Chris Dornan <chris(a)chrisdornan.com> wrote: > * I switched from Text.Regex.TDFA to Text.Regex.PCRE (as I think you > observed, judging by your commit messages), it seems to be somewhat > faster, at lease for these relatively small data sets; > TDFA is pure Haskell and mostly exists for when you can't be certain that a faster C binding will support UTF8 (most POSIX regex implementations do not, and PCRE only does so if someone built it with UTF8 support). When it's usable, the C bindings will almost always be faster. -- brandon s allbery kf8nh sine nomine associates allbery.b(a)gmail.com ballbery(a)sinenomine.net unix, openafs, kerberos, infrastructure, xmonad http://sinenomine.net _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

1 0