Re: [Haskell-cafe] scheduling an alarm
Brian Denheyer bri...@aracnet.com writes: doEvent f usDelay = forkIO $ threadDelay usDelay doEvent f usDelay f There's a missing 'do' here, right? Infinite loop? yes, that is what you wanted. Memory gobbling? Why would you think that? Why would I think that ? doEvent f usDelay = do forkIO $ threadDelay usDelay doEvent f usDelay f Are you sure this isn't interpreted as: doEvent f usDelay = do (forkIO $ threadDelay usDelay) doEvent f usDelay f I.e. just forking off processes that only does a delay, never even getting to 'f'? I interpreted Thomas's code to mean: doEvent f usDelay = forkIO $ (do threadDelay usDelay doEvent f usDelay f) Which appears to work nicely here. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linguistic hair-splitting
Daniel Fischer daniel.is.fisc...@web.de writes: It has been known to call such things 'computations', I think actions has been used, too, but perhaps mostly for things in IO and similar monads? as opposed to 'values', and even to separate the categories of types and expressions which deliver the two. As usual, that only works part of the time. [1,4,15,3,7] is not a computation, it's a list of numbers. A plain and simple everyday value. But isn't a value of (IO String) equally plain and simple? I think I prefer (as somebody suggested) monadic value, so that (if you want to stress this aspect of its use) the list is a monadic Int value in the [] monad, while getLine is a monadic String value in the IO monad, and so on. Maybe. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] scheduling an alarm
Brian Denheyer bri...@aracnet.com writes: doEvent f usDelay = forkIO $ threadDelay usDelay doEvent f usDelay f There's a missing 'do' here, right? Yes - I said that in a later e-mail but it doesn't fix me violating my own peeve about non-functional code snippits on -cafe. Infinite loop? yes, that is what you wanted. Memory gobbling? Why would you think that? Why would I think that ? doEvent f usDelay = do forkIO $ threadDelay usDelay doEvent f usDelay f Are you sure this isn't interpreted as: doEvent f usDelay = do (forkIO $ threadDelay usDelay) doEvent f usDelay f The full code I ran and thought we were talking about (more or less) is inline here. For clarity - yes I know they are different in that one executes 'f' before the first sleep and the other does not. - START CODE - import Control.Concurrent import Control.Monad (forever) import System.IO (hFlush, stdout) doEvent f usDelay = forkIO $ do threadDelay usDelay doEvent f usDelay f doEvent2 f usDelay = do forkIO f threadDelay usDelay doEvent2 f usDelay main = do doEvent func 100 forever (threadDelay maxBound) main2 = do doEvent2 func 100 forever (threadDelay maxBound) func = putStr . hFlush stdout --- END CODE --- I.e. just forking off processes that only does a delay, never even getting to 'f'? The version you referenced is a little weird but so long as you fix the indentation it should be fine (drop forkIO $ f to the next line). Cheers, Thomas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] ANNOUNCE: ThreadScope 0.1
Johan, Thanks for the (mostly) positive news about ThreadScope on Mac OS-X: that's great news. I plan to add a few more Save As... image options in ThreadScope 0.2 plus the ability to turn transparency on/off for PNG files. So hopefully one of the Save As formats might work. I don't think it is a bug in ThreadScope (although I will double check) - it is probably the port of Gth2Hs (but let me check before I say anything too slanderous). Now, how on earth do I track down a Mac OS-X machine at Microsoft ??!??!?!? :) Cheers, Satnam From: haskell-cafe-boun...@haskell.org [mailto:haskell-cafe-boun...@haskell.org] On Behalf Of Johan Tibell Sent: 28 January 2010 01:16 To: Haskell Cafe Subject: Re: [Haskell-cafe] ANNOUNCE: ThreadScope 0.1 On Wed, Jan 27, 2010 at 8:51 AM, Satnam Singh satn...@microsoft.commailto:satn...@microsoft.com wrote: I've just released ThreadScope version 0.1 on Hackage. Threadscope is a graphical utility for viewing profiling information about Haskell threads. It was written jointly with Simon Marlow and Donnie Jones. It uses Gtk2HS so it works under Windows and the L-word operating system although there seem to be problems making it work with OS-X (due to Gtk2Hs issues I think). This is great news! ThreadScope was very useful when I was debugging threading issues in the new I/O manager [1] Bryan and I have been working on. I managed to get it to work on OS X after building gtk2hs from source. Once I got it to build the only problem I had is that it crashes when I try to save to an image file. Cheers, Johan 1. http://github.com/tibbe/event ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
Dear cafe, Could anyone provide a link to some paper/book (electronic version of both preferred, even if not free) that describes an algorithm of translation of untyped lambda calculus expression to a set of combinators? Preferably SKI or BCKW. I'm either feeding google with wrong question or there is no link available now... Thanks, Dušan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
See, for example, slide 119 and onwards in the slides at http://www.cl.cam.ac.uk/teaching/0809/FFuncProg/FoFP_2009_slides.pdf The slides covers SKI and BCSKI. Cheers, Max 2010/1/28 Dušan Kolář ko...@fit.vutbr.cz: Dear cafe, Could anyone provide a link to some paper/book (electronic version of both preferred, even if not free) that describes an algorithm of translation of untyped lambda calculus expression to a set of combinators? Preferably SKI or BCKW. I'm either feeding google with wrong question or there is no link available now... Thanks, Dušan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
Also see http://www.haskell.org/haskellwiki/Super_combinator Wiki page. Fixed set of combinators gives you complexity of translation that is more than linear of the length of lambda expression. The length of output string is O(3^length(lambdaExpression)) for SK combinator pair. 2010/1/28 Dušan Kolář ko...@fit.vutbr.cz: Dear cafe, Could anyone provide a link to some paper/book (electronic version of both preferred, even if not free) that describes an algorithm of translation of untyped lambda calculus expression to a set of combinators? Preferably SKI or BCKW. I'm either feeding google with wrong question or there is no link available now... Thanks, Dušan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] scheduling an alarm
Thomas DuBuisson thomas.dubuis...@gmail.com writes: Yes - I said that in a later e-mail but it doesn't fix me violating my own peeve about non-functional code snippits on -cafe. I guess we're spoiled by the type checker catching all our mistakes. Since I recently discovered the new and wonderful world of C-c C-l in haskell-mode, I wonder if it'd be hard (or if anybody already done so!) to incorporate this for literate-style Haskell in email? Wouldn't it be great if I could, just prior to sending a message, hit C-c C-l to load the *message* buffer in a Haskell process to check that it indeed works as expected, and if you, on reading it, could hit the same key combination to do the same? The birdstep-style might cause difficulties given the same mark's use as standard quoting indicator. And of course, most people use more pedestrian, Turing-inhibited MUAs these days... -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
Hi Dušan The Ester shell written in Clean compiles via the SKI combinators. It is describe in the paper - 'A Functional Shell that Operates on Typed and Compiled Applications' by Arjen van Weelden and Rinus Plasmeijer which is available here: http://www.st.cs.ru.nl/papers/2004/plar2004-Esther_AFP.pdf Ester is part of the Clean 2.2 distribution, but I've had a quick look at it now and I suspect it has diverged a bit from the version described in the paper. The paper references Antoni Diller's 'Compiling Functional Languages' (Wiley - ISBN 0 471 92027 4) as the source of the algorithms they use. This book is long out of print but it is good and comprehensive. I got my copy second-hand from an affiliate on Amazon UK a few years ago after reading the Ester paper. Amazon UK currently has quite a few copies available - the £8+postage price is pretty cheap, the sellers will post internationally (caveat - I've no experience with any of the affiliates listed). There is a full implementation (in Pascal) in the appendix. Diller references David Turner's paper A New Implementation Technique for Applicative Languages (1979 Software - Practice and Experience, vol 9, pp 31-49). If you have a university affiliation you should be able to source this, I haven't seen it myself. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Will Ness wrote: Heinrich Apfelmus writes: (Just for historical reference, credit for the data structure that works with infinite merges goes to Dave Bayer, I merely contributed the mnemonic aid of interpreting it in terms of VIPs.) yes, yes, my bad. GMANE is very unreliable at presenting the discussion threads in full. :| I saw it first on the Haskellwiki page though, and it was your code there, that's the reason for my mistake. :) No worries, doesn't count as mistake for none intended. :) In fact, I'm flattered. ;) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] UTF-16 to UTF-8
Hi, is there a library which converts from utf-16 to utf-8? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] UTF-16 to UTF-8
iconv? Günther Schmidt wrote: Hi, is there a library which converts from utf-16 to utf-8? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] UTF-16 to UTF-8
Günther Schmidt gue.schm...@web.de writes: is there a library which converts from utf-16 to utf-8? The text library can (you can also choose between big and little endian UTF-16). Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Map unionWith generalization
On 28 Jan 2010, at 03:09, Twan van Laarhoven wrote: For example, in Map String Integer (sparse representation of monomials) compute the minimum value of all associative pairs with the same key (the gcd); if only one key is present, the absent should be treated as having value 0. So unionWith min xs ys will not work, because unionWith will always apply the identity to the remaining value when one key is missing, whereas it should be sent to 0. If missing keys represent 0, then wouldn't this work? intersectionWith min xs ys Yes, that works for the gcd function using min. Thank you - this function is used a lot, so it is good to have it simple. For the general problem, one still needs a better interface. For (-), though missing keys represent 0, if the first is missing, the second should be negated. And if both are present, one should filter out keys with 0 value. Right now, this is a combination of negate, (+), and filter (/= 0). Hans ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] UTF-16 to UTF-8
Hi Ivan, thanks for the tip, but how do I use the library? I can't really make out how to feed it UTF-16 and get String (UTF-8) back. Günther BTW: I need this function because I'm using HDBC-ODBC with MS Access and in MS Access apparently every string is in UTF-16. Am 28.01.10 12:47, schrieb Ivan Lazar Miljenovic: Günther Schmidtgue.schm...@web.de writes: is there a library which converts from utf-16 to utf-8? The text library can (you can also choose between big and little endian UTF-16). Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] UTF-16 to UTF-8
Hello Gunther, Thursday, January 28, 2010, 4:07:07 PM, you wrote: thanks for the tip, but how do I use the library? I can't really make out how to feed it UTF-16 and get String (UTF-8) back. Haskell String type isn't UTF-8 encoded. it's [Char] where Char is in UCS-4 aka UTF-32 :) BTW: I need this function because I'm using HDBC-ODBC with MS Access and in MS Access apparently every string is in UTF-16. look at withTString and its friends: http://hamaoka.org/ghc6/libraries/Win32/src/System-Win32-Types.html Am 28.01.10 12:47, schrieb Ivan Lazar Miljenovic: Gunther Schmidtgue.schm...@web.de writes: is there a library which converts from utf-16 to utf-8? The text library can (you can also choose between big and little endian UTF-16). Gunther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] UTF-16 to UTF-8
Günther Schmidt gue.schm...@web.de writes: thanks for the tip, but how do I use the library? I can't really make out how to feed it UTF-16 and get String (UTF-8) back. One way (probably not very efficient): import Data.Text.Encoding convert :: Bytestring - Bytestring convert = encodeUtf8 . decodeUtf16LE No claims are made about efficiency of this technique (mainly because unless you're already using Bytestrings, then it probably isn't very efficient). -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] UTF-16 to UTF-8
2010/1/28 Bulat Ziganshin bulat.zigans...@gmail.com Hello Gunther, Thursday, January 28, 2010, 4:07:07 PM, you wrote: thanks for the tip, but how do I use the library? I can't really make out how to feed it UTF-16 and get String (UTF-8) back. Haskell String type isn't UTF-8 encoded. it's [Char] where Char is in UCS-4 aka UTF-32 :) That's not quite correct. [Char] is a sequence of Unicode code points, UTF-32 is one possible encoding of those code points. The difference is similar to the one between an integer an e.g. its string representation. Cheers, Johan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[4]: [Haskell-cafe] UTF-16 to UTF-8
Hello Johan, Thursday, January 28, 2010, 4:20:48 PM, you wrote: Haskell String type isn't UTF-8 encoded. it's [Char] where Char is in UCS-4 aka UTF-32 :) That's not quite correct. [Char] is a sequence of Unicode code points, UTF-32 is one possible encoding of those code points. The difference is similar to the one between an integer an e.g. its string representation. i say exactly about its encoding :D -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
There is a nice simple algorithm on wikipedia: http://en.wikipedia.org/wiki/Combinatory_logic (for both SKI and BCKW) translated to haskell: -- The anoying thing about the algorithm is that it is difficult to separate the SKI and LC expression types -- it's easiest to just combine them. data Expr = Apply Expr Expr | Lambda String Expr | Id String | S | K | I deriving (Show) convert (Apply a b) = Apply (convert a) (convert b) convert (Lambda x e) | not $ occursFree x e = Apply K (convert e) convert (Lambda x (Id s)) | x == s = I convert (Lambda x (Lambda y e)) | occursFree x e = convert (Lambda x (convert (Lambda y e))) convert (Lambda x (Apply e1 e2)) = Apply (Apply S (convert $ Lambda x e1)) (convert $ Lambda x e2) convert x = x occursFree var (Apply a b) = (occursFree var a) || (occursFree var b) occursFree var (Lambda a b) = if a == var then False else (occursFree var b) occursFree var (Id a) = if a == var then True else False occursFree var _ = False testExpr = Lambda x $ Lambda y $ Apply (Id y) (Id x) test = convert testExpr Hope that helps, - Job 2010/1/28 Dušan Kolář ko...@fit.vutbr.cz Dear cafe, Could anyone provide a link to some paper/book (electronic version of both preferred, even if not free) that describes an algorithm of translation of untyped lambda calculus expression to a set of combinators? Preferably SKI or BCKW. I'm either feeding google with wrong question or there is no link available now... Thanks, Dušan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ghc-core 0.5 build fails
On Wed, 27 Jan 2010 23:10:29 -0800 Don Stewart d...@galois.com wrote: briand: Hi all, ghc-core.hs:263:13: Not in scope: data constructor `C.ExitException' Looks like this comes from the base control.exception ? When I go to the web page for control.exception, there is no exitexception. My reading of the hackage entry for ghc-core makes me think that I've got the correct version of everything. ghc is 6.10.4 Thanks for the report. ghc-core 0.5.1 was released today, so cabal update; cabal install ghc-core and you should be fine. All is well, thanks ! Brian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linguistic hair-splitting
Am Donnerstag 28 Januar 2010 09:14:38 schrieb Ketil Malde: Daniel Fischer daniel.is.fisc...@web.de writes: It has been known to call such things 'computations', I think actions has been used, too, but perhaps mostly for things in IO and similar monads? as opposed to 'values', and even to separate the categories of types and expressions which deliver the two. As usual, that only works part of the time. [1,4,15,3,7] is not a computation, it's a list of numbers. A plain and simple everyday value. But isn't a value of (IO String) equally plain and simple? Sure, but saying a value of type IO String is a computation (in the IO monad) returning a String makes more sense to me than saying [True,False,True] is a computation (in the [] monad) returning a Bool. I think I prefer (as somebody suggested) monadic value, Yes, that works for all monads. so that (if you want to stress this aspect of its use) the list is a monadic Int value in the [] monad, while getLine is a monadic String value in the IO monad, and so on. Maybe. -k ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] scheduling an alarm
Brian Denheyer wrote: On Tue, 26 Jan 2010 22:41:44 -0800 Thomas DuBuisson thomas.dubuis...@gmail.com wrote: doEvent f usDelay = forkIO $ threadDelay usDelay doEvent f usDelay f Are you sure that's right ? It seems to be a memory-gobbling infinite loop... Why would I think that ? I think that because the following code: import Control.Concurrent f = putStrLn foo doEvent f usDelay = do forkIO $ threadDelay usDelay doEvent f usDelay f _really_ _does_ start to consume all of the memory on my system, that's why. I don't know why, but that's what it does on my system. It's not obvious to me that it should do that. So maybe ghci is not doing TCO. The code you have presented at the bottom is an infinite loop that I would expect to consume all the memory on your system. That code spins at 100% busy, forking off threadDelay calls without ever stopping, and will never perform f. Ouch -- infinite loop, and likely hugely memory-consuming (in fact, I'm not sure how the last poster didn't find that it consumed a lot of memory...). However, that code is slightly different to the original (that I have left in up the top) which had a crucial do missing (although you can infer it from the indentation). The original code should be: doEvent f usDelay = forkIO $ do threadDelay usDelay doEvent f usDelay f That is, the latter two lines should be inside the forkIO block, not after it. This code will wait for the given delay, then fork a new thread, then perform f. As long as f takes less time to complete than usDelay, this code should not eat memory and is quite reasonable. I hope that clears up the confusion. Neil. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
On Thu, Jan 28, 2010 at 09:23:23AM -0500, Job Vranish wrote: -- The anoying thing about the algorithm is that it is difficult to separate the SKI and LC expression types -- it's easiest to just combine them. Why is it difficult? -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] OT: Literature on translation of lambda calculus to combinators
Why is it difficult? Ideally we'd like the type of convert to be something like: convert :: LambdaExpr - SKIExpr but this breaks in several places, such as the nested converts in the RHS of the rule: convert (Lambda x (Lambda y e)) | occursFree x e = convert (Lambda x (convert (Lambda y e))) A while ago I tried modifying the algorithm to be pure top-down so that it wouldn't have this problem, but I didn't have much luck. Anybody know of a way to fix this? - Job On Thu, Jan 28, 2010 at 10:21 AM, Felipe Lessa felipe.le...@gmail.comwrote: On Thu, Jan 28, 2010 at 09:23:23AM -0500, Job Vranish wrote: -- The anoying thing about the algorithm is that it is difficult to separate the SKI and LC expression types -- it's easiest to just combine them. Why is it difficult? -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Linguistic hair-splitting
Quoth Daniel Fischer daniel.is.fisc...@web.de, Am Donnerstag 28 Januar 2010 09:14:38 schrieb Ketil Malde: Daniel Fischer daniel.is.fisc...@web.de writes: As usual, that only works part of the time. [1,4,15,3,7] is not a computation, it's a list of numbers. A plain and simple everyday value. But isn't a value of (IO String) equally plain and simple? Sure, but saying a value of type IO String is a computation (in the IO monad) returning a String makes more sense to me than saying [True,False,True] is a computation (in the [] monad) returning a Bool. For sure, and in general when people speak of monads they're really talking about IO, true? If that's disappointing, maybe it would help to have a word for it, maybe `IO String' is an irreduceable monadic value or something. Donn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANNOUNCE: ThreadScope 0.1
To install on ghc-6.12.1 I had to modify the .cabal to accept containers package version 0.3 (I already had the gtk2hs installed). It works fine at first glance, will use it more. - containers = 0.2 0.3 +containers = 0.2 0.4 Cheers, Thomas On Wed, Jan 27, 2010 at 8:51 AM, Satnam Singh satn...@microsoft.com wrote: I’ve just released ThreadScope version 0.1 on Hackage. Threadscope is a graphical utility for viewing profiling information about Haskell threads. It was written jointly with Simon Marlow and Donnie Jones. It uses Gtk2HS so it works under Windows and the L-word operating system although there seem to be problems making it work with OS-X (due to Gtk2Hs issues I think). $ cabal install threadscope You may need to do cabal update to update your packages list. On Windows operating systems you may need to issue the command from a shell that is running with administrative privileges. Resources: · Web page: http://research.microsoft.com/threadscope · Parallel Performance Tuning for Haskellhttp://research.microsoft.com/apps/pubs/default.aspx?id=80976(paper at Haskell Symposium 2009) Please let me know if you have any problems. Also, please do let us know about your experience with ThreadScope and in particular about accounts of how you used ThreadScope to shed light on parallel performance bugs. If I get enough feedback I may collate the responses into an experience report or paper for ICFP or the Haskell Symposium. Thank you kindly. Enjoy! Cheers, Satnam -- Satnam Singh Microsoft 7 JJ Thomson Avenue Cambridge CB3 0FB United Kingdom Email: satn...@microsoft.com UK tel: +44 1223 479905 Fax: +44 1223 479 999 UK mobile: +44 7979 648412 USA cell: 206 330 1580 USA tel: 206 219 9024 URL: http://research.microsoft.com/~satnamshttp://research.microsoft.com/%7Esatnams Live Messenger: sat...@raintown.org ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] big problems with MS Access backends
Hi, I need to use MS Access as a DB-backend. To make it not too easy there are tables with Umlaut Strings in some of the columns. Using HDBC-ODBC the Umlauts get merely garbled, I believe because MS-Access delivers in some sort of UTF-16 and HDBC-ODBC seems to manage that fine safe for the Umlauts, which get garbled. And Takusen crashes outright. Are there other haskellers out there which were in the same situation, ie. MS-Acess and Umlauts (or other none-ascii) and been able to solve this? I sure tried ... Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Very imperfect hash function
I'm looking for some algorithmic suggestions: I have a set of several hundred key/value pairs. The keys are 32-bit integers, and are all distinct. The values are also integers, but the number of values is small (only six in my current problem). So, obviously, several keys map to the same value. For some subsets of keys, examining only a small portion of the key's bits is enough to determine the associated value. For example, there may be 250 keys that all have the same most-significant byte, and all 250 map to the same value. There are also keys at the other extreme, where two keys that differ in only one bit position map to different values. The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function: hash :: key - value My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function? Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: bindings-DSL 1.0.4 (Category: FFI)
On Sat, Jan 23, 2010 at 01:02:07AM -0200, Maurício CA wrote: bindings-DSL is a mature and well documented preprocessor domain specific language you can use to generate bindings to a C API. It's based on functionality provided by hsc2hs. These are links to Hackage page and documentation: http://hackage.haskell.org/package/bindings-DSL http://bitbucket.org/mauricio/bindings-dsl Much thanks for this lovely package. I'm currently using it to write a low-level Direct3D9 binding and thus far it's very friendly. The only thing I've missed for now is a #ccall equivalence for stdcall functions, I hacked one up myself and called it #stdcall, but it would be nice to have in the package proper if possible. Keep up the good work, -- Lars Viklund | z...@acc.umu.se ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Very imperfect hash function
On Thu, 2010-01-28 at 14:07 -0500, Steve Schafer wrote: I'm looking for some algorithmic suggestions: I have a set of several hundred key/value pairs. The keys are 32-bit integers, and are all distinct. The values are also integers, but the number of values is small (only six in my current problem). So, obviously, several keys map to the same value. For some subsets of keys, examining only a small portion of the key's bits is enough to determine the associated value. For example, there may be 250 keys that all have the same most-significant byte, and all 250 map to the same value. There are also keys at the other extreme, where two keys that differ in only one bit position map to different values. The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function: hash :: key - value My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function? Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ Maybe: data TTree a = TTree Int (TTree a) (TTree a) | TNode a -- | THashNode some hash table hash :: TTree a - Int32 - a hash (TNode v) _ = v hash (TTree b l r) k = if testBit k b then hash r k else hash l k -- hash (THashNode h) k = lookupHashTable h k Of course you need to code efficiently the tree. Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Very imperfect hash function
On 28 Jan 2010, at 20:07, Steve Schafer wrote: The data are currently in a large lookup table. To save space, I'd like to convert that into a sort of hash function: hash :: key - value My question is this: Is there any kind of generic approach that can make use of the knowledge about the internal redundancy of the keys to come up with an efficient function? There are minimal perfect hash functions; there are some libraries mentioned here, though they are not in Haskell code: http://en.wikipedia.org/wiki/Perfect_hash_function This is suitable when you do a lot of lookups with few key updates. An alternative might be Data.Map, where lookups have time complexity O(log n), n = size of map. Hans ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hierachical abstraction
OK, this is going to be a long one... Let's start with parsers. A monadic parser library (e.g., Parsec) gives you a set of primitive parsers. It also supplies functions to construct more complex commonly-used parsers. And then it provides functions for constructing even more complex parsers. (E.g., Parsec's expression parser builder.) Let's call the most basic primitive parsers level-0. Then we have level-1 functions, which construct parsers from level-0 parsers. And later we have level-2 functions which call the level-1 functions to construct even more sophisticated parsers. And so on and so forth, to unlimited depth. (The parser library itself has a limited depth, but the library can have clients that build functions on top of functions.) And so, in the end, the user calls a level-64 function, and gets a parser that does the required task. And that's great. The only problem is, the parser you get is a black box. You can't see what's inside it or what it's going to do. You can only run it. (Or combine it with other parsers.) Why is that a problem? Well, suppose you want to pass the finished parser through some kind of optimiser to rearrange its internal structure. Ah. You can't. It's a black box. Veering off onto a tangent for a moment... It seems to me that this is an inevitable consequence for any monadic parser. After all, the bind method runs some parse primitive, but it then feeds the result to a general function, which can undertake some arbitrarily complex Turing-complete calculation to decide what parse primitive to run next. Hell, I can write a parser that parses a description of a grammar, dynamically constructs a parser for that grammer, and then runs it! There's no way in hell that some static optimiser can hope to optimise the meta-parser so that it always generates optimal parsers. Even in theory it's utterly impossible. I wonder if you can make a parser combinator library which is *not* monadic? And, if you could, in what way would that limit the kinds of things you can parse? Anyway, coming back on topic... Let's suppose that instead of parsers, we've interested in queries. Suppose I'm writing some kind of relational database engine library, and I want to optimise queries before running them. The obvious solution is to design some kind of algebraic data type which can represent every possible level-0 query primitive. I can then write level-1 functions that construct level-0 data structures, and level-2 functions that call the level-1 functions, and so on, and at the end the caller will get a (presumably complex) level-0 description, which my optimiser can then go away and chew on. Now suppose I want to perform optimisations on the higher-level structure of the query. Currently, I can't. The hierachy of abstractions gets flatterend to level-0 in the process of the call stack, so my optimiser can only see the final level-0 representation. The obvious solution would be to design an algebraic data type for every level of the hierachy you want to analyse, complete with a function for converting to the next level down. As I understand it, this is how GHC works. It starts with raw Haskell source code, which it mashes around, and eventually converts into Core. The Core representation is then fiddled around with further, and eventually turned into STG. The STG gets poked and prodded, and converted to C--. And that eventually becomes raw assembly. The thing is, these are all radically different representations of the program. You can't mix (say) Haskell and STG together. And nor would you want to, given that they're such wildly different abstractions. [I notice in passing that, apparently, you can now FFI into C--, which is interesting...] However, consider the initial Haskell input. Initially it reflects what the programmer typed in. But GHC gradually desugars this into some minimal subset of the full Haskell language, before actually converting it to Core. That means that [picking an example out of thin air] initially an expression might contain the if/then/else construct, but at some point [I presume] this is desugared into a case expression. And that must mean that there are parts of the GHC codebase where it is permissible for an expression to contain if/then/else, and other parts where this is not permissible (and the code expects this construct to not be present). Is it possible to encode this kind of expectation into the type system? Or does GHC just tacitly rely on the fact that source code takes a predetermined path through the compiler engine? (That works for a monolithic product like a compiler, but it wouldn't be so hot for a library that 3rd parties can poke and prod arbitrary data into.) I'm basically looking at a problem which is like this. There are primitive constructs, and there are more sophisticated abstractions built from these, and I would like to come up with a system where
Re: [Haskell-cafe] Hierachical abstraction
On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin andrewcop...@btinternet.com wrote: I wonder if you can make a parser combinator library which is *not* monadic? And, if you could, in what way would that limit the kinds of things you can parse? Absolutely! I believe both Applicatives and Arrows were originally invented for parsers. I could be mistaken, but at least there are both Applicative and Arrow parser libraries. I don't know how to classify the language that they parse -- it is not strictly context-free. It corresponds roughly to context-free where certain types of infinite chains are allowed. Anyway they are less expressive than Parsec, but more efficient and optimizable, for reasons you correctly identified. I'm basically looking at a problem which is like this. There are primitive constructs, and there are more sophisticated abstractions built from these, and I would like to come up with a system where abstractions are first-class, new abstractions can be added, and for any particular data structure, you can statically guarantee which abstractions are or aren't present. So you're interested in structures which are all similar in a way. GHC converting between different representations has advantages *because* the representations are so different -- different optimization opportunities are apparent in each one that aren't available in the others. But at the very least for extensibility people want to have AST-like structures which have different features, and those features are statically guaranteed. I don't remember the name, but there is a technique where you compose the features you want and then take its fixed point to get your AST. You can make a typeclass for each feature that uses it on any data structure in which it is present. Not the prettiest thing ever, but fairly powerful. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hierachical abstraction
On Jan 28, 2010, at 9:31 PM, Luke Palmer wrote: I don't remember the name, but there is a technique where you compose the features you want and then take its fixed point to get your AST. Did you think of Data types à la carte by Wouter Swierstra? http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf Also see the comments on Phil Wadler's blog: http://wadler.blogspot.com/2008/02/data-types-la-carte.html You can make a typeclass for each feature that uses it on any data structure in which it is present. I don't fully understand this sentence but it reminds me of Finally Tagless, Partially Evaluated by Jacques Carette, Oleg Kiselyov and Chung-chieh Shan: http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf Regarding the question of representing in the type system which features are used, phantom types might also be helpful. If I remember correctly, they were introduced by Daan Leijen and Erik Meijer to restrict a data type that represents syntactically correct database queries such that only type correct queries can be made: http://research.microsoft.com/en-us/um/people/emeijer/Papers/HaskellDB.pdf Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANN: bindings-DSL 1.0.4 (Category: FFI)
http://hackage.haskell.org/package/bindings-DSL http://bitbucket.org/mauricio/bindings-dsl The only thing I've missed for now is a #ccall equivalence for stdcall functions, I hacked one up myself and called it #stdcall, but it would be nice to have in the package proper if possible. Here is my attempt. I added #callconv macro, that accepts a calling convention parameter. The lines below are now equivalent. #ccall do_something , CString - IO CInt #callconv do_something , ccall , CString - IO CInt Would you mind give it some testing (and of course sugestions as you wish) before I upload it to Hackage? The link below gives you a few options for download format. Look for version 1.0.5. http://bitbucket.org/mauricio/bindings-dsl/downloads There are a few good C libraries that work well under Linux and Windows (libusb1.0 for Windows is in beta now, for instance). Do you think we should have a macro that defaults to 'ccall' in Linux and others and to 'stdcall' on Windows? If so, I would need some help to avoid portability issues (like a list of platforms and proper defaults). Thanks for your toughts, Maurício ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: ANN: bindings-DSL 1.0.4 (Category: FFI)
On Thu, Jan 28, 2010 at 09:36:42PM -0200, Maurício CA wrote: The only thing I've missed for now is a #ccall equivalence for stdcall functions, I hacked one up myself and called it #stdcall, but it would be nice to have in the package proper if possible. Here is my attempt. I added #callconv macro, that accepts a calling convention parameter. The lines below are now equivalent. #ccall do_something , CString - IO CInt #callconv do_something , ccall , CString - IO CInt http://bitbucket.org/mauricio/bindings-dsl/downloads Builds fine here and looks reasonably fine. There are a few good C libraries that work well under Linux and Windows (libusb1.0 for Windows is in beta now, for instance). Do you think we should have a macro that defaults to 'ccall' in Linux and others and to 'stdcall' on Windows? If so, I would need some help to avoid portability issues (like a list of platforms and proper defaults). I would guess that any libraries that are written to be portable will likely use the default (cdecl) as calling convention. I do not expect that one would see stdcall used outside inherently native headers like the Windows ones, DirectX, etc. -- Lars Viklund | z...@acc.umu.se ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hierachical abstraction
On 2010-01-28 20:31, Luke Palmer wrote: I could be mistaken, but at least there are both Applicative and Arrow parser libraries. I don't know how to classify the language that they parse -- it is not strictly context-free. It corresponds roughly to context-free where certain types of infinite chains are allowed. If the token set is finite you don't get any expressive advantage from a monadic parser combinator library (in a lazy setting): you can parse any decidable language using a simple library with an applicative functor interface. -- /NAD ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hierachical abstraction
Luke pretty much nailed the summary of what you can parse using Applicative means. I tend to consider them codata CFGs, because they can have infinite breadth and depth. However, a 'codata CFG' can handle a much larger class of languages than CFGs. To that end, it is interesting to consider that to maximize the ability to successfully parse such degenerate grammars you are well served to use a traversal that can handle both of those cases. Such a traversal can be built out of Luke's Omega monad or a logic monad with fair conjunction/disjunction and provides a straightforward if inefficient 'top-down' parser. http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.html http://hackage.haskell.org/packages/archive/control-monad-omega/0.2/doc/html/Control-Monad-Omega.htmlOn the other hand, I've had greater success by working with Applicatives to build a CFG with 'pure' nodes represented as epsilons, using evil StableName hackery to build bottom up parsers. Although, for that to work you basically need to give up the ability to encode arbitrary codata CFGs in order to let the grammar finish compiling. This limits my approach to handling true CFGs (or TIGs), with an extension that covers TAGs, but lets me build a much more efficient parser. And yes, one of the major motivating ideas behind Arrows were the parsers of Swierstra and Duponcheel ( http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.2446). There are also compromise approaches. For instance Swierstra's uu-parsinglib internally uses both a monadic and applicative parser and a by virtue of a special bind operation that can glue them together yields a monad that can at least optimize the last run of applicative computations. http://www.cs.uu.nl/wiki/bin/view/HUT/ParserCombinators -Edward Kmett On Thu, Jan 28, 2010 at 6:22 PM, Sebastian Fischer s...@informatik.uni-kiel.de wrote: On Jan 28, 2010, at 9:31 PM, Luke Palmer wrote: I don't remember the name, but there is a technique where you compose the features you want and then take its fixed point to get your AST. Did you think of Data types à la carte by Wouter Swierstra? http://www.cs.nott.ac.uk/~wss/Publications/DataTypesALaCarte.pdf You can make a typeclass for each feature that uses it on any data structure in which it is present. I don't fully understand this sentence but it reminds me of Finally Tagless, Partially Evaluated by Jacques Carette, Oleg Kiselyov and Chung-chieh Shan: http://www.cs.rutgers.edu/~ccshan/tagless/jfp.pdf Actually, it is quite the opposite of the Kiselyov Carette and Shan trick. interpreting an ADT is an initial algebraic construction, while the Finally Tagless is a final coalgebraic construction. -Edward Kmett ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hierachical abstraction
On Thu, Jan 28, 2010 at 7:58 PM, Nils Anders Danielsson n...@cs.nott.ac.uk wrote: If the token set is finite you don't get any expressive advantage from a monadic parser combinator library (in a lazy setting): you can parse any decidable language using a simple library with an applicative functor interface. Ah good point. I'd realized the class of 'codata CFGs' I was working with was very large, but I hadn't made that painfully obvious in retrospect connection! Just enumerate the inhabitants of the language via your Applicative, er well, technically, Alternative combinators. -Edward Kmett ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: ANN: bindings-DSL 1.0.4 (Category: FFI)
Here is my attempt. I added #callconv macro, that accepts a calling convention parameter. The lines below are now equivalent. Builds fine here and looks reasonably fine. Okay. Package uploaded, documentation updated. Best, Maurício ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Non-termination of type-checking
But your example uses a recursive type; the interesting bit about this
example is that there is no recursive types or function, and yet we
can encode this loop.
-- ryan
On Wed, Jan 27, 2010 at 4:49 PM, Matthew Brecknell
matt...@brecknell.net wrote:
Ryan Ingram wrote:
The compiler doesn't loop for me with GHC6.10.4; I think GADTs still
had some bugs in GHC6.8.
That said, this is pretty scary. Here's a simplified version that
shows this paradox with just a single GADT and no other extensions.
No use of fix or recursion anywhere!
{-# LANGUAGE GADTs #-}
module Contr where
newtype I f = I (f ())
data R o a where R :: (a (I a) - o) - R o (I a)
run :: R o (I (R o)) - R o (I (R o)) - o
run x (R f) = f x
rir :: (R o) (I (R o))
rir = R (\x - run x x)
absurd :: a
absurd = run rir rir
I think that's essentially the same as this:
data Fix a = Fix { unFix :: Fix a - a }
run :: Fix a - Fix a - a
run x f = unFix f x
rir :: Fix a
rir = Fix (\x - run x x)
absurd :: a
absurd = run rir rir
Non-positive recursive occurrences in type definitions provide various
ways to encode the Y-combinator in a typed lambda calculus, without the
need for any recursive let primitive. Haskell allows such non-positive
occurrences, but for strong normalisation, languages like Coq must
disallow them.
If you change data to newtype in the above, the GHC 6.10.4 compiler
(but not GHCi) will loop. I think this is just a case of the infelicity
documented here:
http://www.haskell.org/ghc/docs/latest/html/users_guide/bugs.html
Regards,
Matthew
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Could not find module `Text.Regex'
import Text.Regex date_by_ntday dateStr ntday = do let [y,m,d] = map (\x - read x::Int) $ splitRegex (mkRegex -) dateStr %ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 Which package(s) do i need to use Text.Regex ? Sincerely! - fac n = foldr (*) 1 [1..n] -- View this message in context: http://old.nabble.com/Could-not-find-module-%60Text.Regex%27-tp27366745p27366745.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Could not find module `Text.Regex'
On 29/01/2010 03:51, zaxis wrote: import Text.Regex date_by_ntday dateStr ntday = do let [y,m,d] = map (\x - read x::Int) $ splitRegex (mkRegex -) dateStr %ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 Which package(s) do i need to use Text.Regex ? Sincerely! It looks like you want regex-compat: http://hackage.haskell.org/packages/archive/regex-compat/0.92/doc/html/Text-Regex.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Could not find module `Text.Regex'
z_axis: import Text.Regex date_by_ntday dateStr ntday = do let [y,m,d] = map (\x - read x::Int) $ splitRegex (mkRegex -) dateStr %ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 Which package(s) do i need to use Text.Regex ? In general, you can find an answer via hayoo: http://holumbus.fh-wedel.de/hayoo/hayoo.html e.g typing in Text.Regex brings: http://holumbus.fh-wedel.de/hayoo/hayoo.html?query=Text.Regex says, for the first hit: regex-compat Text.Regex. splitRegex :: Regex - String - [ String ] so yes, you need regex-compat ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Non-termination of type-checking
Here is a bit more simplified version of the example. The example has
no value level recursion and no overt recursive types, and no impredicative
polymorphism. The key is the observation, made earlier, that two types
c (c ()) and R (c ())
unify when c = R. Although the GADTs R c below is not recursive, when
we instantiate c = R, it becomes recursive, with the negative
occurrence. The trouble is imminent.
We reach the conclusion that an instance of a non-recursive GADT
can be a recursive type. GADT may harbor recursion, so to speak.
The code below, when loaded into GHCi 6.10.4, diverges on
type-checking. It type-checks when we comment-out absurd.
{-# LANGUAGE GADTs, EmptyDataDecls #-}
data False -- No constructors
data R c where -- Not recursive
R :: (c (c ()) - False) - R (c ())
-- instantiate c to R, so (c (c ())) and R (c ()) coincide
-- and we obtain a recursive type
--mu R. (R (R ()) - False) - R (R ())
cond_false :: R (R ()) - False
cond_false x@(R f) = f x
absurd :: False
absurd = cond_false (R cond_false)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
