- Haskell-Cafe - Haskell.org

"Quantization" of computations, or step-wise termination, as an extension of Logic Monads
by Juan Casanova 12 Jul '19

12 Jul '19

Dear all, I just subscribed to this list so I'm not familiar with the usual way to go about things here. I hope you'll excuse any cultural mistakes I might make. I'll also try to keep this message as short as possible, but this is hard for me and it is a complex topic, so I will presumably fail. Apologies for that in advance. Short introduction. I'm a PhD student at University of Edinburgh. My research is not on programming languages itself, but during the course of it I ended up programming in Haskell and more particularly faced a problem that I developed a strategy (and eventually a library) for. After some discussions with my supervisors and with some more Haskell experienced people around university, they suggested that I looked into some existing work and also that I posted on this list, and here I am. Let me introduce the problem that I'm trying to solve itself. I have a particular (yet somehow typical) case of non-determinism (search) in the program that I have been writing. It is characterized by: - No joining back of branches ever. - Potentially infinite depth (this is usual). - Potentially infinite width. Meaning that at a single point I may have an infinite amount of possible paths to follow. - It is critical that the search is complete. After reading a bit, I have realized this is usually referred to as being a fair search order. For me this means that there can be many (infinite) valid solutions in the search space, and I want to find all of them (i.e. for every valid solution, the program will eventually output it). As I said, I developed my own (particular) approach to this, then generalized it in a library, and then, after talking to some people, realized this might be something quite interesting to share, but first had to check that it's not something that has already been done. Long story short, the most relevant piece of research I was pointed to was "Backtracking, interleaving and terminating monad transformers", by O Kiselyov, C Shan, DP Friedman and A Sabry, published in 2005. (https://dl.acm.org/citation.cfm?id=1086390) I also know that this approach is embodied in Haskell through the Control.Monad.Logic library. I read the paper and skimmed through some related work, and gave a try to the library. Indeed, it seems to be doing mostly what I need. In particular, it can deal with infinite breadth/infinite width searches through a process of what I call "diagonalization". That is, a combination of breadth-first and depth-first that ensures fairness. Note that the library actually does a lot more things that I didn't consider because they were not relevant for my problem, for instance cuts. However, I find that there is something that this library does not take into account, and after trying with the Haskell library I have verified that indeed it does not work, whereas my library does work. I am wondering if I have overlooked some work in which this is also taken into account or if I may be onto some useful extension of Control.Monad.Logic that hasn't been done yet. I still have to find a stable name for the feature that I am talking about, but I usually refer to it as "step-wise termination" or "quantization of computations". To understand it consider an example (that I have actually implemented): 1. Whenever I have a non-deterministic enumeration, I should have a way to output a fair search among that non-deterministic search (a list), following the properties that I indicated above. 2. I can make an enumeration that non-deterministically produces all multiples of a certain number. 3. I can make an enumeration that non-deterministically produces all powers of a certain number. 4. I can make a function that, given an enumeration, filters it through a boolean function. 5. I can monadically combine computations, so that I can, for instance, produce a computation that is the result of producing all multiples of a number, and for each of those, producing all their powers. 6. So what happens if I combine the three of them. In particular, what if I output all *odd* powers of all multiples of 1 (all naturals)? (multiples 1) >>= (\x -> filter odd (powers x))? If I do this using the Control.Monad.Logic library (and using the >>- operator provided there, of course), this does not produce a fair search. Specifically, it outputs 1 and then hangs up. The reason? The order in which the search is produced picks one value from each sublist at a time, but because there are no odd powers of an even number (say 2), it never finds any element in the sublist of powers of 2, and therefore never gets to even try with the powers of 3. My library can deal with this by "quantizing" computation, making sure that each individual step of a computation always terminates (in Haskell terms, I wrap things up in a way that I can guarantee that a single look-ahead on the list will always produce a head normal form in finite time, even if that is still a continuation of the computation). Therefore, while it keeps trying to find powers of 2 that are odd, this does not stop the search over all the other sublists. This mail is already quite long, but let me make a few precisions. You may stop reading here if you don't wanna get your hands dirty, I've said the most important bits. I know a bit of what I say here will be confusing if you don't think about it yourself, so skip it if it gets confusing. It's mainly to answer some questions/comments I can foresee. Of course, this only works if the embedding into the monad is terminating itself. So, when you do "pure x" for my monad, you need to guarantee that "x" will produce a head normal form in finite time). But as long as you guarantee this atomic notion and you only use the monadic transformation functions that are not labelled as "unsafe" (which are only the unnatural ones for the semantics that I am considering, such as appending in a list sense), then I can guarantee the search will always be fair. Also, a thing I've been thinking quite a bit is whether you can consider this notion of "quantization" of computation separately from the notion of an enumeration of a non-deterministic search space. Of course you can, but the interesting bit is to do this diagonalization over non-deterministic search spaces in a quantized way so that rabbit holes like the odd powers of 2 are not a problem. I tried to implement this in a generic way that you can later on "combine" with Control.Monad.Logic in a non-specific way, but it won't work, due to the particular reason that you'd need to do pattern matching over the structure of the logic monad, and there's no way to type check that for an arbitrary data type (because the pattern matching could give literally any potential sub-types). Implementing the quantization separately and then the combination individually as a one-of thing could be done, of course, but it would essentially be the same that I have right now. A different story would be had if ghci actually had monadic functions to enable the evaluation of *any* thunk one-step-at-a-time (that is, one function evaluation or one pattern match). This is absolutely not what seq does, because seq evaluates until it is a weak head normal form, which is not what I want. Precisely, bottom seq a = bottom, and my quantized computation does not fulfill this equation (and it should not). My library is not perfect now, and after having read and understood the Control.Monad.Logic library, I think the best thing would be to extend it, which is something I don't do right now. But still so, unless I have missed an already existing implementation of something like this, or I am seeing something in a really convoluted way. Please feel free to drop any questions or comments at all. I'm attaching an example of why Control.Monad.Logic does not work in the case that I said. It also includes an example using my library, which I am not attaching. This example works. Just comment it. I'm not attaching my library now because it's not "polished" and because it is a lot for people to randomly look at, but feel free to ask for it and I'll happily send it over, so that you can run the example with it. Again, any questions or comments are welcome. Lead me the right direction with this. ... And sorry for the wall of text. Thank you very much for all of your time and attention, Juan Casanova. -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.

2 3

Hidden types and scope
by Lana Black 11 Jul '19

11 Jul '19

Hello cafe, While writing some code, I stumbled upon quite an interesting behavior. See the code example below. ------------------------------------------------------------- {-# LANGUAGE ExistentialQuantification #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE RankNTypes #-} data Wrapper = forall m. Monad m => Wrapper { runAction :: forall a. m a -> IO a , someAction :: String -> m () } newtype MyIO a = MyIO { runIO :: IO a } deriving (Monad) ex :: Wrapper ex = Wrapper runIO (\s -> MyIO (putStrLn s)) {- This doesn't work -} --main :: IO () --main = do let Wrapper r a = ex -- r (a "Hello") {- This works -} main :: IO () main = case ex of Wrapper r a -> r (a "Hello") ------------------------------------------------------------- The idea is to hide the exact type `m` used in the wrapper, making the wrapper somewhat opaque to the user, while exposing some functionality and making sure that using `runAction` with the rest of the members of Wrapper is type-safe and `m` is always the same type within one instance of Wrapper. The problem that I ran into is that the first version of `main` doesn't compile with the following error: • Couldn't match expected type ‘p’ with actual type ‘forall a. m a -> IO a’ because type variable ‘m’ would escape its scope This (rigid, skolem) type variable is bound by a pattern with constructor: Wrapper :: forall (m :: * -> *). Monad m => (forall a. m a -> IO a) -> (String -> m ()) -> Wrapper, in a pattern binding at wildcards.hs:18:15-25 • In the pattern: Wrapper r a In a pattern binding: Wrapper r a = ex In the expression: do let Wrapper r a = ex r (a "Hello") This is repeated for every member of Wrapper that is matched in a let expression. However, if let expression is replaced with case, everything builds and works just fine. Is there a way to make it work with let expressions? That way the code is a lot cleaner, especially with RecordWildCards involved.

4 5

Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 191, Issue 6
by Information The FLOSS 11 Jul '19

11 Jul '19

Bu ileti The FLOSS Information'a gönderdiğiniz ileti sonucunda otomatik olarak oluşturuldu. Bu iletiye yanıt vermenize gerek yoktur. Bu iletiyi gönderdiğiniz için teşekkür ederiz. 4 gün içerisinde yanıtlamaya çalışacağız. Eğer 4 gün içinde yanıt gelmezse tekrar ileti gönderebilirsiniz. Sık Sorulabilecek Sorular: https://theflossinformation.gitlab.io/sik-sorulabilecek-sorular.html Hakkımızda: https://theflossinformation.gitlab.io/hakkimizda.html Bize Ulaşın: https://theflossinformation.gitlab.io/bize-ulasin.html Saygılarımızla, The FLOSS Information https://theflossinformation.gitlab.io/

1 0

[ldap-client] Project takeover initiation
by Brian C. Jones 10 Jul '19

10 Jul '19

Hello, I have attempted to contact the author via PR and direct email with no response in 3 weeks. This is my final attempt before engaging the Hackage admins. https://github.com/supki/ldap-client/pull/16 Brian Jones

1 0

Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 191, Issue 5
by Information The FLOSS 10 Jul '19

10 Jul '19

Bu ileti The FLOSS Information'a gönderdiğiniz ileti sonucunda otomatik olarak oluşturuldu. Bu iletiye yanıt vermenize gerek yoktur. Bu iletiyi gönderdiğiniz için teşekkür ederiz. 4 gün içerisinde yanıtlamaya çalışacağız. Eğer 4 gün içinde yanıt gelmezse tekrar ileti gönderebilirsiniz. Sık Sorulabilecek Sorular: https://theflossinformation.gitlab.io/sik-sorulabilecek-sorular.html Hakkımızda: https://theflossinformation.gitlab.io/hakkimizda.html Bize Ulaşın: https://theflossinformation.gitlab.io/bize-ulasin.html Saygılarımızla, The FLOSS Information https://theflossinformation.gitlab.io/

1 0

The GHC Committee welcomes its new members
by Joachim Breitner 10 Jul '19

10 Jul '19

Dear Haskell community, the GHC Steering committee welcomes its new two members, Sandy Maguire and Arnaud Spiwack. We are happy to see that there is continued interest in our work, and are looking forward to the insights and energy that are brought to the committee by Sandy and Arnaud. They take the seats of Ben Gamari and Manuel Chakravarty. A big thanks to Ben and Manuel for their contributions to GHC and the proposal committee. In particular Ben, who created the initials draft of the proposal process. We had four nominations in total, and I would like to preserve their privacy. Since we only had two seats to fill, we had to make a pick; nevertheless I am grateful for all nominations, and encourage everyone, including those who did not make it this time, to try again next time. Neither the committee nor its process is perfect, as the way two recent proposals went show, but we are constantly trying to refine and improve. Your feedback is always welcome, either at the committee mailing list, or in private communication with the Chairs (the two Simons), me, or any other member. On behalf of the committee, Joachim Breitner PS: Sandy and Arnaud, please subscribe to the mailing list at https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee -- Joachim Breitner mail(a)joachim-breitner.de http://www.joachim-breitner.de/

1 0

mapM and Control.Arrow
by Olaf Klinke 09 Jul '19

09 Jul '19

Dear cafe, consider the declaration mapM :: (SomeArrow a, Traversable t) => a b c -> a (t b) (t c) For the Arrow a = (->), the above mapM is just an over-constrained fmap, since Functor is a superclass of Traversable. For the arrow a = Kleisi m, the above mapM is the Control.Monad.mapM we know. Currently I fail to see how it could be defined with any of the existing sub-classes in Control.Arrow. One might say that fmap and mapM are on the same spectrum: If you specialize SomeArrow to (->) you can generalize Traversable to Functor, if you specialize Functor to Traversable you can generalize (->) to SomeArrow. Cheers, Olaf

2 3

Re: [Haskell-cafe] Haskell-Cafe Digest, Vol 191, Issue 4
by Information The FLOSS 09 Jul '19

09 Jul '19

Bu ileti The FLOSS Information'a gönderdiğiniz ileti sonucunda otomatik olarak oluşturuldu. Bu iletiye yanıt vermenize gerek yoktur. Bu iletiyi gönderdiğiniz için teşekkür ederiz. 4 gün içerisinde yanıtlamaya çalışacağız. Eğer 4 gün içinde yanıt gelmezse tekrar ileti gönderebilirsiniz. Sık Sorulabilecek Sorular: https://theflossinformation.gitlab.io/sik-sorulabilecek-sorular.html Hakkımızda: https://theflossinformation.gitlab.io/hakkimizda.html Bize Ulaşın: https://theflossinformation.gitlab.io/bize-ulasin.html Saygılarımızla, The FLOSS Information https://theflossinformation.gitlab.io/

1 0

parallel Haskell with limited sparks
by Henning Thielemann 09 Jul '19

09 Jul '19

When I read about parallel programming in Haskell it is always about manual chunking of data. Why? Most of my applications with parallelization benefit from a different computation scheme: Start a fixed number of threads (at most the number of available computing cores) and whenever a thread finishes a task it gets assigned a new one. This is how make -j, cabal install -j, ghc -j, work. I wrote my own package pooled-io which does the same for IO in Haskell and there seem to be more packages that implemented the same idea. Can I have that computation scheme for non-IO computations, too? With Parallel Strategies, monad-par etc.?

2 3

{-# SPECIALIZE foo @Bar #-} ?
by Johannes Waldmann 08 Jul '19

08 Jul '19

Dear Cafe, with pragma SPECIALIZE, I find it tedious to repeat the type declaration. (It's a burden for maintenance and readability.) Could we use type-application syntax instead? E.g., the example from here https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_ext… hammeredLookup :: Ord key => [(key, value)] -> key -> value {-# SPECIALIZE hammeredLookup :: [(Widget, value)] -> Widget -> value #-} would become hammeredLookup :: forall key value . Ord key => [(key, value)] -> key -> value {-# SPECIALIZE hammeredLookup @Widget #-} or {-# SPECIALIZE hammeredLookup @Widget @value #-} Cf. SPECIALIZE instance, where we already write the instantiation for the type variable(s). - J.W.

2 1