[Haskell-cafe] Re: [Haskell] ANNOUNCE: CPython / libpython bindings
John Millikin wrote: ...Python language, has a C API... The cpython[2] package is a binding to this API. I wrote: How does this package compare to the classic MissingPy package? MissingPy appears to be a set of data types which implement MissingH classes using the Python library. Not exactly. John Goerzen's MissingH and MissingPy libraries together do provide some useful things that are (or were in the past) missing from Haskell. Useful things that already exist in Python and would be a lot of work to re-implement in Haskell are provided in MissingPy via the Haskell binding to the Python API. The rest of the useful things are provided as native Haskell implementations in MissingH. But for me, and probably many others, the most important service provided by MissingPy is the Python API binding itself. It has only a minimal binding to libpython, enough to implement its class instances but not enough for general-purpose use of libpython. I'm not sure what you mean by that. Using MissingPy, you can instantiate a Python object of any type, marshall data back and forth between Python and Haskell for the basic built-in Python types and any object built out of them, access any Python module, and call any Python function or method. Most people find those capabilities to be quite good for general-purpose use. What do you feel is missing? I wrote this package so I could benchmark Python modules using Criterion, with an eye towards writing extension modules in Haskell, so it has many more data types and computations available. Oh, you want to write Python extension modules in Haskell? Right, MissingPy explicitly does not cover calling Haskell from Python. For accessing Python from Haskell, though, MissingPy has been around for a long time and works well. There may be quite a lot of code around that uses it. Is your API similar? Is there any specific new capability that you are adding? Do you have some compatibility recommendations? One thing you certainly are adding is a more recent version of Python - MissingPy is still at Python 2.5. Also, it is a small annoyance that to use MissingPy's API binding you also have to pull in all of the missing things from MissingH and MissingPy and their dependencies. Those aren't used as much these days now that there is so much available from hackage. Thanks, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] time of day
Brian Denheyer wrote: What's the best way to get the year/month/day/hour/min/sec of the current time ? import Data.Time ... now - getCurrentTime tz - getCurrentTimeZone let t = utcToLocalTime tz now (year, month, day) = toGregorian $ localDay t TimeOfDay hour minute sec = localTimeOfDay t If you need the day of week, then also: import Data.Time.Calendar.OrdinalDate (sundayStartWeek) ... (_, dow) = sundayStartWeek $ localDay t -- Sunday = 0 If you need to use different time zones other than the current local one, construct them like this: est = TimeZone {timeZoneMinutes = -300, timeZoneSummerOnly = False, timeZoneName = EST} edt = TimeZone {timeZoneMinutes = -240, timeZoneSummerOnly = True, timeZoneName = EDT} I've become mired in confusion with Time, Data.Time, DateTime and I think there is even an old-time. Might be a couple of calendar libraries in there, not quite sure... Thomas DuBuisson wrote: 'time' is the generally accepted package which exports the Data.Time you mentioned. Yes, use that. 'DateTime' looks to use 'time' to provide an aledgedly simpler API. I tried that once. It is supposed to have a slightly gentler learning curve, but in the end I think Data.Time itself is nicer. The only reason Data.Time is a little confusing at first is because the most useful functions are sprinkled into many different modules in the documentation, and hidden among less useful ones. Once you know where to look for things, it's easy. -Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Finally tagless and abstract relational Algebra
Hi, I'm still trying to build an *abstract* Relation Algebra using the finally tagless style. My guess is that finally tagless style allows one to create a syntax without any initial dependency to an implementation. Ie. once one has created the syntax in this style one can then proceed to construct terms. So this is my goal, create a syntax for relational algebra, express an abstract relational algorithm in this syntax and worry about implementation / compilation / evaluation *later*. But at least being able to express a correctly typed term. I presume I will need to employ HList at some point, but I'm not entirely certain where. Will I need it at the very beginning, as constrains in the syntax so that only correct abstract terms can be built, or will I need it in on of the interpreters / compilers later? Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finally tagless and abstract relational Algebra
Günther Schmidt wrote: My guess is that finally tagless style allows one to create a syntax without any initial dependency to an implementation. Ie. once one has created the syntax in this style one can then proceed to construct terms. Yes. So this is my goal, create a syntax for relational algebra, express an abstract relational algorithm in this syntax and worry about implementation / compilation / evaluation *later*. But at least being able to express a correctly typed term. Good plan. But syntax design is hard, whatever style you choose. I presume I will need to employ HList at some point, but I'm not entirely certain where. Will I need it at the very beginning, as constrains in the syntax so that only correct abstract terms can be built, or will I need it in on of the interpreters / compilers later? You will not need HList for constraining the syntax -- Haskell's type system should already provide all you need to constrain the syntax. In fact, in tagless final style (rather than in initial style), for the lambda calculus you don't even need GADTs to deal with exotic terms! Why do you think you'll have to use HList? While HList is great, in this particular instance, I don't think you'll need it. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finally tagless and abstract relational Algebra
Hi Jacques, well in short my post is supposed to pretty much lay bare my lack of understanding of the problem I try to solve, with the hope that someone is willing to fill the gaps. I do know that I could express my algorithms via list-comprehension or in a List Monad, all using tuples. And that would be concrete and grossly inefficient. But I also wouldn't be able to express an incorrectly typed term *thanks* to using tuples. So how would it be possible to express selecting /field/ b from /record/ x and field c from record y, creating record z, while making sure that record x does have field b and record y does have field c? I mean design a syntax for it? Günther Am 28.12.09 16:15, schrieb Jacques Carette: Günther Schmidt wrote: My guess is that finally tagless style allows one to create a syntax without any initial dependency to an implementation. Ie. once one has created the syntax in this style one can then proceed to construct terms. Yes. So this is my goal, create a syntax for relational algebra, express an abstract relational algorithm in this syntax and worry about implementation / compilation / evaluation *later*. But at least being able to express a correctly typed term. Good plan. But syntax design is hard, whatever style you choose. I presume I will need to employ HList at some point, but I'm not entirely certain where. Will I need it at the very beginning, as constrains in the syntax so that only correct abstract terms can be built, or will I need it in on of the interpreters / compilers later? You will not need HList for constraining the syntax -- Haskell's type system should already provide all you need to constrain the syntax. In fact, in tagless final style (rather than in initial style), for the lambda calculus you don't even need GADTs to deal with exotic terms! Why do you think you'll have to use HList? While HList is great, in this particular instance, I don't think you'll need it. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] GHC 6.12 on OS X 10.5
On Dec 22, 2009, at 9:36 PM, wren ng thornton wrote: Aaron Tomb wrote: I've come across the issue with iconv, as well. The problem seems to be that some versions of iconv define iconv_open and some related functions as macros (that then call libiconv_open, etc.), and some versions of iconv have exported functions for everything. In particular, the iconv bundled with OS X (1.11) defines iconv_open, but the iconv installed with MacPorts (1.13) does not. The binary package for GHC 6.12.1 seems to have been compiled on a system without MacPorts, and therefore references iconv_open (etc.) from the Apple-distributed version of the library. If you set up an installation of GHC 6.12 on OS X (I've only tried 10.5) with no references to /opt/local/lib, everything works fine. If you include /opt/local/lib in the extra-lib-dirs field of your .cabal/config file, it tries to link with the MacPorts version and fails with undefined references. Is this a problem with *versions* of iconv, or with branches/forks? If it's versions, then it seems like migrating to =1.13 would be good for everyone. If it's just branches, do you know whether this afflicts Fink users as well as MacPorts users, or should I be the guinea pig to test that? It's a problem with versions. I checked that the official iconv repository does indeed make the change between 1.11 and 1.13 that causes the problem. The issue is that OS X includes an old version. So migrating to =1.13 means convincing Apple to upgrade what they include with the system. If we can accomplish that, I'd be thrilled. But it hasn't happened yet as of 10.6. Fink comes with 1.12. I'm not sure whether 1.12 is more like 1.11 or 1.13. Aaron ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finally tagless and abstract relational Algebra
Günther Schmidt wrote: I do know that I could express my algorithms via list-comprehension or in a List Monad, all using tuples. And that would be concrete and grossly inefficient. You should probably tell us what these algorithms accomplish, rather than how one implementation goes. From a higher-level view of what you're trying to do [but not as high as saying 'implement abstract relational algebra'], it will be easier to give concrete advice. So how would it be possible to express selecting /field/ b from /record/ x and field c from record y, creating record z, while making sure that record x does have field b and record y does have field c? I mean design a syntax for it? Perhaps you should tell us why you think you need records at all, and record sub-typing to boot. You might well be right, but the higher-level requirements will have a much bigger influence on the design than anything else. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance of functional priority queues
On Sat, Dec 26, 2009 at 12:49 AM, Svein Ove Aas svein@aas.no wrote: Lazyness can be considered to be a controlled form of mutation Can someone explain why this is true (or link me to an explanation)? -- Gautam ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance of functional priority queues
On Monday 28 December 2009 17:11:14 Gautam bt wrote: On Sat, Dec 26, 2009 at 12:49 AM, Svein Ove Aas svein@aas.no wrote: Lazyness can be considered to be a controlled form of mutation Can someone explain why this is true (or link me to an explanation)? Forcing the evaluating of a thunk replaces the unevaluated expression with the value it evaluates to. That is effectively in-place mutation. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Finally tagless and abstract relational Algebra
Dear Jacques, I'll try to explain by a concrete example and what I'm hoping to achieve. my app imports 4 CSV files, generated from a hospital's IT system and nationally standardized (Germany). Theses 4 files contain records of how much money the hospital received for a patient, when he was initial admitted, what kind of procedures a patient had and when, his transfers and stays from departments within the hospital and his initial admission date. The common key in all these different kind of records is a patient's case-id. From all this information and more I calculate through a very complicated scheme a departments share of the revenue created for a individual patient. Well not even patients as such but rather hospital-case. The scheme is rather complicated and a bit of a moving target, because the auditors in a hospital do have the possibility to redistribute shares from one department to another. For instance revenue shares on surgical procedures may be redistributed from a non-surgical department to a surgical one and so on. Initially I had simply imported the CSV files into empty tables in a database and done the calculations directly in SQL, never ever again! The algorithms for looking up values in one table and matching them with the next, and sometimes creating new values, for instance figuring out in which department a patient had which procedures, those I'd like to express concisely and abstractly. Because I may or may not choose to evaluate the algorithm then to in-memory haskell code, using Maps or what-have-you or to compile to SQL, or whatever. But my 1st goal here is to express the algorithm. I figure if I have to change the abstract algorithm due to new requirements (but not the syntax), the concrete and probably more elaborate implementation follows suit automatically. Günther Am 28.12.09 17:49, schrieb Jacques Carette: Günther Schmidt wrote: I do know that I could express my algorithms via list-comprehension or in a List Monad, all using tuples. And that would be concrete and grossly inefficient. You should probably tell us what these algorithms accomplish, rather than how one implementation goes. From a higher-level view of what you're trying to do [but not as high as saying 'implement abstract relational algebra'], it will be easier to give concrete advice. So how would it be possible to express selecting /field/ b from /record/ x and field c from record y, creating record z, while making sure that record x does have field b and record y does have field c? I mean design a syntax for it? Perhaps you should tell us why you think you need records at all, and record sub-typing to boot. You might well be right, but the higher-level requirements will have a much bigger influence on the design than anything else. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: [Haskell] ANNOUNCE: CPython / libpython bindings
On Mon, Dec 28, 2009 at 03:52, Yitzchak Gale g...@sefer.org wrote: John Millikin wrote: It has only a minimal binding to libpython, enough to implement its class instances but not enough for general-purpose use of libpython. I'm not sure what you mean by that. Using MissingPy, you can instantiate a Python object of any type, marshall data back and forth between Python and Haskell for the basic built-in Python types and any object built out of them, access any Python module, and call any Python function or method. Most people find those capabilities to be quite good for general-purpose use. What do you feel is missing? http://docs.python.org/3.1/c-api/init.html http://docs.python.org/3.1/c-api/reflection.html Most of http://docs.python.org/3.1/c-api/concrete.html Most of http://docs.python.org/3.1/c-api/abstract.html While it is possible to emulate some C API procedures using Python encoded in Haskell, I find the C API more readable. Compare: - -- emptySet :: IO Set callArgs (getItem (getAttribute (importModule types) __builtins__) set) [] = fmap fromJust cast toList [] = iterableToSet - And of course, it's very difficult to do things like create a new interpreter or modify the sys module from within a running interpreter. I wrote this package so I could benchmark Python modules using Criterion, with an eye towards writing extension modules in Haskell, so it has many more data types and computations available. Oh, you want to write Python extension modules in Haskell? Right, MissingPy explicitly does not cover calling Haskell from Python. Eventually -- Python 3 improved the module system enough that it should be possible (compared to 2.x, where C-style static memory was essentially required). I'd like to try (for example) implementing the Python decimal.Decimal type in terms of Haskell's Ratio. For accessing Python from Haskell, though, MissingPy has been around for a long time and works well. There may be quite a lot of code around that uses it. Is your API similar? Is there any specific new capability that you are adding? Do you have some compatibility recommendations? My API's not similar -- one of my goals was to match the C API as closely as is reasonable, with more type safety. According to the reverse dependency-enabled Hackage[1], as of December 24[2] there are no dependencies on MissingPy. In contrast, there are 27 direct and 17 indirect dependencies on MissingH. [1] http://bifunctor.homelinux.net/~roel/cgi-bin/hackage-scripts/package/MissingPy [2] http://bifunctor.homelinux.net/~roel/hackage/packages/archive/recent.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance of functional priority queues
On Tue, Dec 29, 2009 at 12:04 AM, Jon Harrop j...@ffconsultancy.com wrote: Forcing the evaluating of a thunk replaces the unevaluated expression with the value it evaluates to. That is effectively in-place mutation. How can one use that to gain on efficiency? I understand that laziness allows a modified data structure to share nodes with the original data structure preventing unnecessary copying, but I do not see how forcing an evaluation can be used to gain on efficiency (or alternatively prevent inefficiency). Is there any simple example to illustrate this (or should I read Okasaki)? -- Thanks, Gautam ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Performance of functional priority queues
On Monday 28 December 2009 18:04:32 Gautam bt wrote: On Tue, Dec 29, 2009 at 12:04 AM, Jon Harrop j...@ffconsultancy.com wrote: Forcing the evaluating of a thunk replaces the unevaluated expression with the value it evaluates to. That is effectively in-place mutation. How can one use that to gain on efficiency? In a purely functional setting? I understand that laziness allows a modified data structure to share nodes with the original data structure preventing unnecessary copying, I think you mean that idiomatic purely functional data structures evade copying the entire structure by breaking it down recursively and referring back to older versions whenever possible (i.e. sharing). That has nothing to do with laziness though and, compared to the mutable case, it incurs a lot of extra copying. In fact, that is half the reason why purely functional data structures are so slow. The other half is that recursive decomposition leads to many levels of indirection which is hugely inefficient on modern computers due to cache misses. The main use case where purely functional data structures pay dividends in terms of performance is persistence. For example, when you backtrack in an n-queens solver you create a new, slightly-different list and forget about the old one (which gets recycled). This style of programming is very common in metaprogramming such as compilers, interpreters and theorem provers. but I do not see how forcing an evaluation can be used to gain on efficiency (or alternatively prevent inefficiency). An example of preventing an inefficiency in the purely functional case is easy: consider two threads about to perform the same computation. Making them compete to force a thunk can prevent them from redundantly performing the same computation. The downside is that the implementation of laziness must deal with race conditions and this is neither easy nor efficient. Is there any simple example to illustrate this (or should I read Okasaki)? You should read Okasaki regardless. :-) A good example from Okasaki might be the purely functional queue. A simple eager solution maintains front and back lists, pushes on the back and pops from the front except when it is empty, whereupon it reverses the back list to create a new front list. Eager evaluation of that list reversal is problematic in the presence of persistent use: the programmer might keep the same old version of a queue with an empty front list around and pop from it several times whereupon the same list reversal will be repeated needlessly every time. So non-persistent use of these batched queues has good amortized complexity but persistent use has awful complexity. Okasaki presents a real-time queue that uses laziness to avoid this inefficiency. In essence, the reversal is stored element-wise as thunks that are forced only when necessary and their result reused if it is ever required again. So it makes persistent use asymptotically more efficient. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Upgraded to GHC 6.12 and can't find anything
Ok, I'm trying to build the haskell platform but getting this. Anyone know what the problem is? As far as I know I have all the development libs for OpenGL. I'm not sure what this means. I'm running Ubuntu 9.04 on a 64bit dual core AMD. Preprocessing library GLUT-2.1.1.2... Building GLUT-2.1.1.2... Registering GLUT-2.1.1.2... Setup: GLUT-2.1.1.2: dependency OpenGL-2.2.1.1-e949822dd9af14c1680857afb46ab567 doesn't exist (use --force to override) Error: Building the GLUT-2.1.1.2 package failed make: *** [build.stamp] Error 2 make: Target `default' not remade because of errors. --- On Sun, 12/27/09, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: From: Ivan Lazar Miljenovic ivan.miljeno...@gmail.com Subject: Re: [Haskell-cafe] Upgraded to GHC 6.12 and can't find anything To: Gregory Propf gregorypr...@yahoo.com Cc: Haskell-Cafe haskell-cafe@haskell.org Date: Sunday, December 27, 2009, 11:30 PM Gregory Propf gregorypr...@yahoo.com writes: I finally compiled and installed GHC 6.12 on my Linux system and it seems to be failing to find a lot of things. Notably these import Control.Monad import Control.Monad.State import Control.Monad.Trans import Control.Parallel A lot of these kinds of modules were not actually part of GHC but installed as part of GHC's extralibs packages (which is being replaced by the Haskell platform). You can get the first three modules by installing mtl and the last by installing parallel, both of which can be found on Hackage. -- 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] Upgraded to GHC 6.12 and can't find anything
On Monday 28 December 2009 21:06:20 Gregory Propf wrote: Ok, I'm trying to build the haskell platform but getting this. Anyone know what the problem is? As far as I know I have all the development libs for OpenGL. I'm not sure what this means. I'm running Ubuntu 9.04 on a 64bit dual core AMD. I had the same problem with Debian Lenny on a 32-bit 2x quadcore Opteron: http://groups.google.com/group/fa.haskell/msg/34ee76bed380438d I found that installing the binary Debian packages (from Sid) haskell-platform and ghc6, and then installing ghc 6.12 from source fixed 6.10. Now I seem to be able to compile with 6.10 and programs run without segfaulting (but not 6.8 or 6.12). I never managed to get cabal to work though... -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Control.Parallel missing
Hi! A friend of mine tried to learn Haskell and asked me for an advice because he had problems with Haskell in 5 steps: http://www.haskell.org/haskellwiki/Haskell_in_5_steps Under Write your first parallel Haskell program section there is import Control.Parallel which is simply missing in 6.12 and also it is not in documentation anymore: http://www.haskell.org/ghc/docs/latest/html/libraries/index.html I know that we have moved now to Haskell Platfrom so you can install it additionally (probably), but for a novice it is not really nice that example programs do not compile out of the box. Maybe we could extend this 4th step also with an introduction to Cabal? Mitar ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Control.Parallel missing
Hi Mitar, I think that step 1 should link to the Haskell Platform, and not to GHC or Hugs specifically. A beginner should not be using GHC 6.12 yet! greetings, Sjoerd On Dec 29, 2009, at 12:03 AM, Mitar wrote: Hi! A friend of mine tried to learn Haskell and asked me for an advice because he had problems with Haskell in 5 steps: http://www.haskell.org/haskellwiki/Haskell_in_5_steps Under Write your first parallel Haskell program section there is import Control.Parallel which is simply missing in 6.12 and also it is not in documentation anymore: http://www.haskell.org/ghc/docs/latest/html/libraries/index.html I know that we have moved now to Haskell Platfrom so you can install it additionally (probably), but for a novice it is not really nice that example programs do not compile out of the box. Maybe we could extend this 4th step also with an introduction to Cabal? Mitar ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Sjoerd Visscher sjo...@w3future.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Upgraded to GHC 6.12 and can't find anything
Jon, I haven't tried GHC 6.12 or the Haskell Platform yet, but here is our standard install procedure for our company, which has worked consistently for us since GHC 6.8 (we use ubuntu 9.04 32-bit): - Add ~/.ghc/bin and ~/.cabal/bin to PATH. - Download and extract latest ghc. Then from directory: $ configure --prefix=$HOME/.ghc make install - Download and extract cabal-install from hackage. Then from directory: $ ./bootstrap.sh - Update cabal package database: $ cabal update - Install required libs and tools: $ cabal install darcs atom ... When we upgrade GHC, we typically nuke ~/.cabal and ~/.ghc and start over. The whole process usually only takes about 20 minutes. -Tom On Tue, Dec 29, 2009 at 12:02 AM, Jon Harrop j...@ffconsultancy.com wrote: On Monday 28 December 2009 21:06:20 Gregory Propf wrote: Ok, I'm trying to build the haskell platform but getting this. Anyone know what the problem is? As far as I know I have all the development libs for OpenGL. I'm not sure what this means. I'm running Ubuntu 9.04 on a 64bit dual core AMD. I had the same problem with Debian Lenny on a 32-bit 2x quadcore Opteron: http://groups.google.com/group/fa.haskell/msg/34ee76bed380438d I found that installing the binary Debian packages (from Sid) haskell-platform and ghc6, and then installing ghc 6.12 from source fixed 6.10. Now I seem to be able to compile with 6.10 and programs run without segfaulting (but not 6.8 or 6.12). I never managed to get cabal to work though... -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ___ 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] FGL/Haskell and Hierarchical Clustering/dendograms
Thank you very much for your reply! I have been looking at the code, and there are two problems, as I can see. First, trying with the example t1 :: Tree (Id, Cost) t1 = Node (4,0) [Node (3,2) [Node (1,12) []] ,Node (2,3) [Node (5,1) [Node (6,2) [Node (7,2) [] printed as (4,0) | +- (3,2) | | | `- (1,12) | `- (2,3) | `- (5,1) | `- (6,2) | `- (7,2) your function 'cluster fst snd t1' returns Many [Many [Many [Many [Many [One (0,[4]),One (1,[5])],One (2,[3])],One (2,[6,7])],One (3,[2])],One (12,[1])] I can't see how this representation is giving the hierarchical clusters. The example above should resolve into level 1: [[(2,3),(5,1)],[(6,2)],[(7,2)],[(4,0)], [(3,2)], [(1,12)]] level 2: [[(2,3),(5,1),(6,2),(7,2)], [(4,0),(3,2)], [(1,12)]] level 3: [[(2,3),(5,1),(6,2),(7,2),(4,0),(3,2)], [(1,12)]] level 4 (or (cost) level 12): [[(2,3),(5,1),(6,2),(7,2),(4,0),(3,2),(1,12)]] By doing it this way, we cluster all nodes connected with edges less than or equal x at (cost) level x. Clearly, we can have level 1: [[(1,1),(2,1)],[(3,1),(4,1)],...] if the edges between [(1,1),(2,1)] and [(3,1),(4,1)] are greater than 1. Second, I don't think it is trivial to tree-i-fy the root path tree. I have done the function treeifyMST, which surely isn't efficient, since the list encounteredNodes is traversed as many times as the number of nodes (a binary search tree would be more efficient). But more important, the tree isn't correct, since each path is connected at the root of the tree. Example (LRTree Int): [ [(1,0)],[(5,1),(1,0) ], [(2,2),(1,0)] , [(3,3),(2,2),(1,0)] , [(4,4),(2,2),(1,0)] ] - [ [(5,1),(1,0) ] , [(3,3),(2,2),(1,0)] , [(4,4),(2,2),(1,0)] ] In my code, all 3 paths are branching at the root (1,0), but should for the last two paths branch at node (2,2). How should I cope with that in an efficient way? I wonder if if it is easier to implement it from the ground using the approach given at http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html? - --TO DO: now all paths are connected at the root of the tree. Should be patched at the right places inside the tree. The search in the list encounteredNodes is not efficient. treeifyMST :: LRTree Int - Tree (Id,Cost) treeifyMST rootpathtree = let (LP rpt:rpts) = rootpathtree root = head rpt revrootpathtree = reverse rootpathtree in Node root (constructTree [] revrootpathtree) where constructTree :: [Int] - LRTree Int - [Tree (Id,Cost)] constructTree encounteredNodes (LP x:[]) = [] constructTree encounteredNodes (LP x:xs) = let path1 = x !! 0 path2 = x !! 1 id1 = fst path1 id2 = fst path2 in case (L.find (==id1) encounteredNodes) of -- because we have encountered an already processed id, we can skip this sublist Just _ - constructTree (id2:encounteredNodes) xs -- new id, meaning that we have encountered a new path Nothing - let lenpath = length x revpath = reverse $ take (lenpath-1) x tree = listToNode revpath in tree:constructTree (id2:encounteredNodes) xs constructTree _ _ = [] listToNode (p:ps:[]) = Node p [Node ps []] listToNode (p:ps) = Node p [listToNode ps] - Nikolas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
apfelmus apfelmus at quantentunnel.de writes: Dave Bayer wrote: What I'm calling a venturi venturi :: Ord a = [[a]] - [a] merges an infinite list of infinite lists into one list, under the assumption that each list, and the heads of the lists, are in increasing order. I wrote this as an experiment in coding data structures in Haskell's lazy evaluation model, rather than as explicit data. The majority of the work done by this code is done by merge; the multiples of each prime percolate up through a tournament consisting of a balanced tree of suspended merge function calls. In order to create an infinite lazy balanced tree of lists, the datatype data List a = A a (List a) | B [a] is used as scaffolding. One thinks of the root of the infinite tree as starting at the leftmost child, and crawling up the left spine as necessary. After some pondering, the List a data structure for merging is really ingenious! :) Here's a try to explain how it works: The task is to merge a number of sorted and infinite lists when it's known that their heads are in increasing order. In particular, we want to write primes = (2:) $ diff [3..] $ venturi $ map multiple primes Thus, we have a (maybe infinite) list xss = [xs1, xs2, xs3, ...] of infinite lists with the following properties all sorted xss sorted (map head xss) where sorted is a function that returns True if the argument is a sorted list. A first try to implement the merging function is venturi xss = foldr1 merge xss = xs1 `merge` (xs2 `merge` (xs3 `merge` ... where merge is the standard function to merge to sorted lists. However, there are two problems. The first problem is that this doesn't work for infinite lists since merge is strict in both arguments. But the property head xs1 head xs2 head xs3 ... we missed to exploit yet can now be used in the following way venturi xss = foldr1 merge' xss merge' (x:xt) ys = x : merge xt ys In other words, merge' is biased towards the left element merge' (x:_|_) _|_ = x : _|_ which is correct since we know that (head xs head ys). The second problem is that we want the calls to merge to be arranged as a balanced binary tree since that gives an efficient heap. It's not so difficult to find a good shape for the infinite tree, the real problem is to adapt merge' to this situation since it's not associative: .. The problem is that the second form doesn't realize that y is also smaller than the third argument. In other words, the second form has to treat more than one element as privileged, namely x1,x2,... and y. This can be done with the aforementioned list data structure data People a = VIP a (People a) | Crowd [a] The people (VIPs and crowd) are assumed to be _sorted_. Now, we can start to implement merge' :: Ord a = People a - People a - People a Hi, ... replying to a two-years-old post here, :) :) and after consulting the full VIP version in haskellwiki/Prime_Numers#Implicit_Heap ... It is indeed the major problem with the merged multiples removing code (similar one to Richard Bird's code from Melissa O'Neill's JFP article) - the linear nature of foldr, requiring an (:: a-b-b) merge function. To make it freely composable to rearrange the list into arbitrary form tree it must indeed be type uniform (:: a-a-a) first, and associative second. The structure of the folded tree should be chosen to better suit the primes multiples production. I guestimate the total cost as Sum (1/p)*d, where p is a generating prime at the leaf, and d the leaf's depth, i.e. the amount of merge nodes its produced multiple must pass on its way to the top. The structure used in your VIP code, 1+(2+(4+(8+...))), can actually be improved upon with another, (2+4)+( (4+8)+( (8+16)+...)), for which the estimated cost is about 10%-12% lower. This can be expressed concisely as the following: primes :: () - [Integer] primes () = 2:primes' where primes'= [3,5] ++ drop 2 [3,5..] `minus` comps mults = map (\p- fromList [p*p,p*p+2*p..]) $ primes' (comps,_) = tfold mergeSP (pairwise mergeSP mults) fromList (x:xs) = ([x],xs) tfold f (a: ~(b: ~(c:xs))) = (a `f` (b `f` c)) `f` tfold f (pairwise f xs) pairwise f (x:y:ys) = f x y : pairwise f ys mergeSP (a,b) ~(c,d) = let (bc,b') = spMerge b c in (a ++ bc, merge b' d) where spMerge u@(x:xs) w@(y:ys) = case compare x y of LT - (x:c,d) where (c,d) = spMerge xs w EQ - (x:c,d) where (c,d) = spMerge xs ys GT - (y:c,d) where (c,d) = spMerge u ys spMerge u [] = ([], u) spMerge [] w = ([], w) with ''merge'' and ''minus'' defined in the usual way. Its run times are indeed improved 10%-12% over the VIP code from the haskellwiki page. Testing was done by running the code,
[Haskell-cafe] Invertible functions list
Hi, I would to create a list of tuples (or something similar) of invertible functions [((a - b), (b - a)), ((b - c), (c - b)), Such that I could call forward invertibleFuctionList domainValue = ? -- composite all the functions backward invertibleFuctionList rangeValue = forward (reverse invertibleFuctionList) rangeValue -- or something similar I would also like to concat them. This sounds like a job for GADT that someone might have already tackled. Any ideas? -Jonathan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))
apfelmus apfelmus at quantentunnel.de writes: ~~ This is a repost, with apologies to anyone who sees this twice (I've replied to a two years old thread, and it doesn't show up in GMANE as I thought it would). ~~ Dave Bayer wrote: What I'm calling a venturi venturi :: Ord a = [[a]] - [a] merges an infinite list of infinite lists into one list, under the assumption that each list, and the heads of the lists, are in increasing order. I wrote this as an experiment in coding data structures in Haskell's lazy evaluation model, rather than as explicit data. The majority of the work done by this code is done by merge; the multiples of each prime percolate up through a tournament consisting of a balanced tree of suspended merge function calls. In order to create an infinite lazy balanced tree of lists, the datatype data List a = A a (List a) | B [a] is used as scaffolding. One thinks of the root of the infinite tree as starting at the leftmost child, and crawling up the left spine as necessary. After some pondering, the List a data structure for merging is really ingenious! :) Here's a try to explain how it works: The task is to merge a number of sorted and infinite lists when it's known that their heads are in increasing order. In particular, we want to write primes = (2:) $ diff [3..] $ venturi $ map multiple primes Thus, we have a (maybe infinite) list xss = [xs1, xs2, xs3, ...] of infinite lists with the following properties all sorted xss sorted (map head xss) where sorted is a function that returns True if the argument is a sorted list. A first try to implement the merging function is venturi xss = foldr1 merge xss = xs1 `merge` (xs2 `merge` (xs3 `merge` ... where merge is the standard function to merge to sorted lists. However, there are two problems. The first problem is that this doesn't work for infinite lists since merge is strict in both arguments. But the property head xs1 head xs2 head xs3 ... we missed to exploit yet can now be used in the following way venturi xss = foldr1 merge' xss merge' (x:xt) ys = x : merge xt ys In other words, merge' is biased towards the left element merge' (x:_|_) _|_ = x : _|_ which is correct since we know that (head xs head ys). The second problem is that we want the calls to merge to be arranged as a balanced binary tree since that gives an efficient heap. It's not so difficult to find a good shape for the infinite tree, the real problem is to adapt merge' to this situation since it's not associative: .. The problem is that the second form doesn't realize that y is also smaller than the third argument. In other words, the second form has to treat more than one element as privileged, namely x1,x2,... and y. This can be done with the aforementioned list data structure data People a = VIP a (People a) | Crowd [a] The people (VIPs and crowd) are assumed to be _sorted_. Now, we can start to implement merge' :: Ord a = People a - People a - People a Hi, ... replying to a two-years-old post here, :) :) and after consulting the full VIP version in haskellwiki/Prime_Numers#Implicit_Heap ... It is indeed the major problem with the merged multiples removing code (similar one to Richard Bird's code from Melissa O'Neill's JFP article) - the linear nature of foldr, requiring an (:: a-b-b) merge function. To make it freely composable to rearrange the list into arbitrary form tree it must indeed be type uniform (:: a-a-a) first, and associative second. The structure of the folded tree should be chosen to better suit the primes multiples production. I guestimate the total cost as Sum (1/p)*d, where p is a generating prime at the leaf, and d the leaf's depth, i.e. the amount of merge nodes its produced multiple must pass on its way to the top. The structure used in your VIP code, 1+(2+(4+(8+...))), can actually be improved upon with another, (2+4)+( (4+8)+( (8+16)+...)), for which the estimated cost is about 10%-12% lower. This can be expressed concisely as the following: primes :: () - [Integer] primes () = 2:primes' where primes'= [3,5] ++ drop 2 [3,5..] `minus` comps mults = map (\p- fromList [p*p,p*p+2*p..]) $ primes' (comps,_) = tfold mergeSP (pairwise mergeSP mults) fromList (x:xs) = ([x],xs) tfold f (a: ~(b: ~(c:xs))) = (a `f` (b `f` c)) `f` tfold f (pairwise f xs) pairwise f (x:y:ys) = f x y : pairwise f ys mergeSP (a,b) ~(c,d) = let (bc,b') = spMerge b c in (a ++ bc, merge b' d) where spMerge u@(x:xs) w@(y:ys) = case compare x y of LT - (x:c,d) where (c,d) = spMerge xs w EQ - (x:c,d) where (c,d) = spMerge xs ys GT - (y:c,d) where (c,d) = spMerge u ys spMerge u [] = ([], u) spMerge [] w = ([], w) with ''merge''
Re: [Haskell-cafe] Invertible functions list
This might be pertinent: Alimarine et al, There and Back Again: Arrows for Invertible Programming http://www.cs.ru.nl/A.vanWeelden/bi-arrows/ Jonathan Fischoff wrote: Hi, I would to create a list of tuples (or something similar) of invertible functions [((a - b), (b - a)), ((b - c), (c - b)), Such that I could call forward invertibleFuctionList domainValue = ? -- composite all the functions backward invertibleFuctionList rangeValue = forward (reverse invertibleFuctionList) rangeValue -- or something similar I would also like to concat them. This sounds like a job for GADT that someone might have already tackled. Any ideas? -Jonathan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Invertible functions list
Do you need to be able to extract the intermediate types? If not, then the only observable value for your function list is the composition (forward/backward), and you can easily represent it like this: data Inv a b = Inv { forward :: (a - b), backward :: (b - a) } nil :: Inv a a nll = Inv id id cat :: Inv a b - Inv b c - Inv a c cat ab bc = Inv (forward bc . forward ab) (backward ab . backward bc) reverse :: Inv a b - Inv b a reverse ab = Inv (backward ab) (forward ab) -- ryan On Mon, Dec 28, 2009 at 8:32 PM, Jonathan Fischoff jonathangfisch...@gmail.com wrote: Hi, I would to create a list of tuples (or something similar) of invertible functions [((a - b), (b - a)), ((b - c), (c - b)), Such that I could call forward invertibleFuctionList domainValue = ? -- composite all the functions backward invertibleFuctionList rangeValue = forward (reverse invertibleFuctionList) rangeValue -- or something similar I would also like to concat them. This sounds like a job for GADT that someone might have already tackled. Any ideas? -Jonathan ___ 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] Invertible functions list
On Mon, Dec 28, 2009 at 10:32 PM, Jonathan Fischoff jonathangfisch...@gmail.com wrote: Hi, I would to create a list of tuples (or something similar) of invertible functions [((a - b), (b - a)), ((b - c), (c - b)), Such that I could call forward invertibleFuctionList domainValue = ? -- composite all the functions backward invertibleFuctionList rangeValue = forward (reverse invertibleFuctionList) rangeValue -- or something similar I would also like to concat them. This sounds like a job for GADT that someone might have already tackled. Any ideas? It looks like the thrist package should help you out: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/thrist You could define some sort of type Iso: data Iso a b = Iso (a - b) (b - a) And then build a Thrist and fold over it, the functions forward and backwards can both be implemented with right-folds. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))
Will Ness will_n48 at yahoo.com writes: wheelSums = roll 0 wdiffs roll = scanl (+) wheel = wdiffs ++ wheel wdiffs = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2: 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wdiffs Apparently that works too, but I meant it to be: wdiffs = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2: 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:[] :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Design question
There are many SVG elements, of which only a few are valid as the content of each other SVG elements. SvgDocumentElement defines the allowed subset for the SVG document. I want to generate a DList Char for all those sub-elements and finally collapse them to one DList Char representing the whole SVG document. So it's a bit more complicated than your Either example I suggest a monadic combinator approach. The grammar's the thing. Consider: data View a = AtomicView a | NestViews (View a) (View a) (View a) | ConcatViews (View a) (View a) | Etc... instance Monad View where return = AtomicView AtomicView v = f = f v (NestViews left middle right) = f = (ConcatViews (ConcatViews left middle) right) = f (ConcatViews left right) = f = ConcatVeiws (f left) (f right) -- Etc = f = whatever These are structural nodes. Notice how = normalizes your document automagically. You would put your specific node types in Etc. Writing a renderer from something with this form is pretty straight forward. Enforcing constraints isn't too hard either. Neither is parsing. Just write a parser for each http://www.haskell.org/haskellwiki/Parsec http://legacy.cs.uu.nl/daan/download/parsec/parsec.html___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Request to review my attempt at understanding Monads
Hi, I've been reading the papers titled Comprehending Monads and Monadic Parser Combinator to understand Monads and I think I am beginning to understand it. In my attempt to validate my understanding, I've written my version of List data structure with Monadic behaviour - I'd appreciate answers to the following queries - 1. Comments about the functions I've written 2. I've used the do notation at the bottom which is a result of my List being a Monad - are there any other benefits that comes in because of List being a Monad? What would MonadPlus provide me? 3. The comprehension syntax for Lists in Haskell - can that be used in anyway for other Monads? Regards, Kashyap import Monad ( MonadPlus(..) ) data List a = Cons a (List a) | Empty deriving Show --myMap :: (t - a) - List t - List a myMap :: (t - a) - List t - List a myMap f Empty = Empty myMap f (Cons a rest) = Cons (f a) (myMap f rest) --myAppend :: List a - List a - List a myAppend :: List a - List a - List a myAppend Empty l = l myAppend l Empty = l myAppend (Cons a rest) l = Cons a (myAppend rest l) --myConcat :: List (List a) - List a myConcat :: List (List a) - List a myConcat Empty= Empty myConcat (Cons Empty rest)= myConcat rest myConcat (Cons list rest)= myAppend list (myConcat rest) instance Monad List where return a = Cons a Empty Empty = f = Empty l = f = myConcat (myMap f l) instance MonadPlus List where p `mplus` q = myAppend p q mzero= Empty list2myList :: [a] - List a list2myList [] = Empty list2myList (x:xs) = Cons x (list2myList xs) l1 = list2myList [1..10] l2 = do x - l1 y - Cons (2*x) Empty return y ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Configuring cabal install readline on Snow Leopard with MacPorts
I've tried to do cabal install readline on Snow Leopard with MacPorts and it fails with the infamous: $ cabal install readline ... checking for GNUreadline.framework... checking for readline... no checking for tputs in -lncurses... yes checking for readline in -lreadline... yes checking for rl_readline_version... yes checking for rl_begin_undo_group... no configure: error: readline not found, so this package cannot be built See `config.log' for more details. cabal: Error: some packages failed to install: readline-1.0.1.0 failed during the configure step. The exception was: exit: ExitFailure 1 Googilng shows the usual explanation that Mac'y broken clone interferes; yet I do have MacPorts and readline 6 there. So I try, per fixes recommended, $ cabal install readline --extra-include-dirs=/opt/local/include --extra-lib-dirs=/opt/local/lib ... checking for rl_readline_version... yes checking for rl_begin_undo_group... no ... -- same result. Downloaded the package and do configure manually: ./configure --with-readline-includes=/opt/local/include --with-readline-libraries=/opt/local/lib ... checking for readline in -lreadline... no checking for rl_readline_version... no ... Huh? $ port contents readline ... /opt/local/include/readline/readline.h ... /opt/local/lib/libreadline.5.0.dylib /opt/local/lib/libreadline.5.1.dylib /opt/local/lib/libreadline.5.2.dylib /opt/local/lib/libreadline.6.0.dylib /opt/local/lib/libreadline.6.dylib /opt/local/lib/libreadline.a /opt/local/lib/libreadline.dylib ... How should I properly tell cabal install readline where my readline is? Cheers, Alexy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe