Re: [Haskell-cafe] Mining Twitter data in Haskell and Clojure
Op 14-06-10 07:00, braver schreef: I'm computing a communication graph from Twitter data and then scan it daily to allocate social capital to nodes behaving in a good karmic manner. The graph is culled from 100 million tweets and has about 3 million nodes. First I wrote the simulation of the 35 days of data in Clojure and then translated it into Haskell with great help from the glorious #haskell folks. I had to add -A5G -K5G to make it work. It does 10 days OK hovering at 57 GB of RAM; I include profiling of that in sc10days.prof. At first the Haskell executable goes faster than Clojure, not by an order of magnitude, but by 2-3 times per day simulated. (Clojure also fits well in its 32 GB JVM with compressed references.) However, Haskell gets stuck after a while, and for good. Clearly I'm not doing Haskell optimally here, and would appreciate optimization advice. Here's the code: http://github.com/alexy/husky The data and problem description is in http://github.com/alexy/husky/blob/master/Haskell-vs-Clojure-Twitter.md -- also referred from the main README.md. The main is in sc.hs, and the algorithm is in SocRun.hs. The original Clojure is in socrun.clj. This is a continuation of active Twitter research and the results will be published, and I'd really like to make Haskell work at this scale and beyond! The seq's sprinkled already did no good. I ran under ghc 6.10 with -O2 with or without - fvia-C, with no difference in stallling, and am working to bring 6.12 to bear now. Cheers, Alexy ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe If you just want to optimize it and not compare exactly equal idiomatic code, you should stop using functional data structures and use a structure that fits your problem (the ST monad has been designed for that in Haskell), because compilers do not detect single-threaded usage and rewrite all your code to something mutable and thereby avoid O(log n) costs. In practice it is probably easier to write the whole thing against the parallel Boost Graph Library (a C++ library), since that library provides the abstractions that you would want. If you go this path, it will probably end up being 10-100 times faster. -- Best Regards, Ron de Bruijn, ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Nested Types stack size ...
Hi, Günther Schmidt schreef: Hi, I'm using deeply nested types in my app and exceed some stack-size in ghci. I can't remember the runtime option I have to pass to ghci anymore, it's been about a year since I last pursued this approach. ghci +RTS --help suggests -K Sets the maximum stack size (default 8M) Egs: -K32k -K512k. ghci is just another Haskell program which uses the GHC RTS. Is it also possible to set this stack-size via pragma in the source code? Via an OPTIONS_GHC pragma, if possible. -- Best Regards, Ron de Bruijn, Developer, Gamr7 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Marshalling arrays without flakiness?
Hi,
I would like to know whether there is a good way to marshal the following
structure to C without using pointer arithmetic done by a programmer (as opposed
to a tool).
typedef struct{
double a[10];
double b[10];
double b[10];
} foo;
I don't need this functionality, but it would make Haskell -> C interfaces less
flaky. Basically, writing Haskell -> C interfaces seem to be a very unpopular
thing to do (as opposed to C -> Haskell interfaces).
For example, on Hackage (actually a checkout of a few months ago) there is only
one package using pokeArray and it is not pretty; it uses pointer arithmetic and
all other kinds of hard-coded addresses. If I change the order of the C fields
it will break, if I change the length of the buffer they use, it breaks. Just
look at it, and it will break ;)
If you are a bit creative, it is possible to make it work already, by using the
best features of both hsc2hs and c2hs, but it is hardly elegant.
I suppose the real solution would be to extend c2hs with an offsetof function
(for which patches already exist, btw), but it might be that I have missed some
other solution.
--
Best Regards,
Ron de Bruijn,
Developer, Gamr7
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hsmagick crash
Mark Wassell schreef: > Have you tried > http://hackage.haskell.org/cgi-bin/hackage-scripts/package/pngload ? Hi Mark, I just did: import Codec.Image.PNG png_file_to_2d_array file = do either_error_string_or_png <- loadPNGFile file either (\s -> error $ "(png_file_to_2d_array) " ++ s) (\png -> putStrLn (show (dimensions png)) ) either_error_string_or_png and then calling it gives: *** Exception: (png_file_to_2d_array) failed to parse chunk "IHDR", (line 1, column 1): unexpected 0x0 expecting valid colorType: supported Ct2,Ct6 Best regards, Ron ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hsmagick crash
Hi,
I am trying to extract the image data from various file formats and it appeared
that hsmagick would be the right package to use.
However, it doesn't actually work or I use it incorrectly. If you have installed
hsmagick and change the value of some_png_file to some existing png file, you
should see that it crashes at some random pixel. For the particular 256*256
image I had, it crashed on pixel_nr `elem` [54,56,57].
I am open to suggestions for better ways to get a Array (Int,Int) RGB from e.g.
a png file.
import Graphics.Transform.Magick.Images
import Graphics.Transform.Magick.Types
import Foreign.Storable
import Control.Monad
image_file_name_to_2d_array file = do
himage <- readImage file
let ptr_to_image = image himage
himage_ <- peekElemOff ptr_to_image 0
let bounds@(_rows, _cols) = (rows himage_,columns himage_)
number_of_pixels = fromIntegral _rows * fromIntegral _cols
mapM (\pixel_nr -> do
putStrLn ("Pixel: " ++ show pixel_nr)
pixel_packet <- liftM background_color_ $
peekElemOff
ptr_to_image
pixel_nr
let red_component = red pixel_packet
putStrLn ("Pixel packet: " ++ show red_component)
return red_component)
[0.. number_of_pixels - 1]
some_png_file = "foo.png"
t = do
initialize_image_library
image_file_name_to_2d_array some_png_file
initialize_image_library = initializeMagick
Best regards,
Ron de Bruijn
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Marshalling recursive data structures with the FFI
Hi, A few days ago we published an article (http://gamr7.com/blog/?p=66) on using the FFI to marshal recursive data structures between Haskell and C (or Python if you use ctypes). Best regards, Ron de Bruijn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Initializing GHC from Python
Hi, We have just published a small article on how one can initialize GHC from Python, with only optional use of C. You can read it at http://gamr7.com/blog/?p=65 . Best regards, Ron de Bruijn ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Writing binary files?
--- Sven Panne <[EMAIL PROTECTED]> wrote: > Hal Daume III wrote: > > There's a Binary module that comes with GHC that > you can get somewhere (I > > believe Simon M wrote it). I have hacked it up a > bit and added support > > for bit-based writing, to bring it more in line > with the NHC module. > > Mine, with various information, etc., is available > at: > > > > http://www.isi.edu/~hdaume/haskell/NewBinary/ > > Hmmm, I'm not sure if that is what Ron asked for. > What I guess is needed is > support for things like: > > "read the next 4 bytes as a low-endian unsigned > integer" > "read the next 8 bytes as a big-endian IEEE 754 > double" > "write the Int16 as a low-endian signed integer" > "write the (StorableArray Int Int32) as > big-endian signed integers" > ... > > plus perhaps some String I/O with a few encodings. > Alas, we do *not* have > something in our standard libs, although there were > a few discussions about > it. I know that one can debate ages about byte > orders, external representation > of arrays and floats, etc. Nevertheless, I guess > covering only low-/big-endian > systems, IEEE 754 floats, and arrays as a simple > 0-based sequence of its > elements (with an explicit length stated somehow) > would make at least 90% of all > users happy and would be sufficient for most "real > world" file formats. Currently > one is bound to hGetBuf/hPutBuf, which is not really > a comfortable way of doing > binary I/O. > > Cheers, > S. > Basically, I just want to have a function, that converts a list with zeros and ones to a binary file and the other way around. If I write to a file, it would take 8 bytes. But I want it to take 8 bits. __ Do you Yahoo!? Yahoo! Mail Address AutoComplete - You start. We finish. http://promotions.yahoo.com/new_mail ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Writing binary files?
Hi, I would like to write and read binary files in Haskell. I saw the System.IO module, but you need a (Ptr a) value for using that, and I don't need positions. I only want to read a complete binary file and write another binary file. In 2001 somebody else came up with the same subject, but then there wasn't a real solution. Now, 3 years later, I can imagine there's *something*. What's that *something*? Regards, Ron __ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stack overflow in ghci
--- Tomasz Zielonka <[EMAIL PROTECTED]> wrote: > On Thu, Sep 02, 2004 at 08:47:51AM -0700, Ron de > Bruijn wrote: > > I heard of the +RTS option. I used: > > ghci SomeModule.hs -someoptions +RTS -K150, > but > > this doesn't seem to have any effect. > > Try +RTS -K150M. > -K150 means 150 bytes. > > Best regards, > Tom > > -- > .signature: Too many levels of symbolic links > Ok, it works. I thought the K was equivalent to 1000, but the first K doesn't have that meaning. Thanks. __ Do you Yahoo!? Yahoo! Mail is new and improved - Check it out! http://promotions.yahoo.com/new_mail ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Stack overflow in ghci
I have an expression that gives a stack overflow in ghci (official Debian unstable CVS version)) when I evaluate it. The expression doesn't use more than 150MB of memory (I have more). How can I make sure the stack overflow doesn't happen? There are no strictness flags in my program. But I use DData Maps(I don't know whether they are implemented strict). I also don't know whether strictness/lazyness has anything do to with it. *SomeModule> test *** Exception: stack overflow (148.67 secs, 250825284 bytes) Sometimes I get a negative number of bytes. I heard of the +RTS option. I used: ghci SomeModule.hs -someoptions +RTS -K150, but this doesn't seem to have any effect. I think there should be someother option to change it? Thanks in advance, Ron de Bruijn __ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell extension/improvement
--- Martin_Sjögren <[EMAIL PROTECTED]> wrote: > On Mon, 16 Aug 2004 09:01:45 -0700 (PDT), Ron de > Bruijn > <[EMAIL PROTECTED]> wrote: > > I was playing with QuickCheck and I just wanted to > put > > all of my tests in a list, but that's not > possible, > > because of the fact that a list can only contain > > values of the same type. > > > > So concrete I would like to write down this: > > > > prop_RevRev xs = reverse (reverse xs) == xs > > where types = xs::[Int] > > > > --trivial test > > prop_Simple = True == True > > > > whatIwant::(Testable a)=>[a] > > whatIwant = [prop_RevRev, prop_Simple] > > > > testAll::IO () > > testAll = do sequence_ $ map quickCheck whatIwant > > > I saw this page: > > http://www.haskell.org/hawiki/ExistentialTypes > > > > but you still have to explicitly add the relation > via > > Obj (and that's bad). > > Well, if you write > > data Test = forall a. Testable a => Test a > > instance Testable Test where > property (Test x) = property x > > you at least get the "unwrapping" for free, and can > write things like > > mapM_ quickCheck [Test prop_revrev, Test > prop_trivial, Test prop_something] > > > Regards, > Martin > I didn't expect these replies (including one mentioning the HList idea(the enforced ordening is nice, though)), while I tried to be precise. The idea is that you don't write down the Test constructor in any place, because you(that's the compiler) can check that all the values you put in the list(or any other datastructure) belong to a certain class. Everything that can be derived should be derived. Regards, Ron __ Do you Yahoo!? Take Yahoo! Mail with you! Get it on your mobile phone. http://mobile.yahoo.com/maildemo ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell extension/improvement
I was playing with QuickCheck and I just wanted to put all of my tests in a list, but that's not possible, because of the fact that a list can only contain values of the same type. So concrete I would like to write down this: prop_RevRev xs = reverse (reverse xs) == xs where types = xs::[Int] --trivial test prop_Simple = True == True whatIwant::(Testable a)=>[a] whatIwant = [prop_RevRev, prop_Simple] testAll::IO () testAll = do sequence_ $ map quickCheck whatIwant quickCheck can work on all Testable values, so why can't a list (any datastructure) can't hold Testable values? What this gives you is, a lot more flexibility. Just like you can define your functions on interfaces, now you can use interfaces in your datastructures. I can't think of any reason why it couldn't be implemented in any Haskell compiler. I saw this page: http://www.haskell.org/hawiki/ExistentialTypes but you still have to explicitly add the relation via Obj (and that's bad). Regards, Ron P.S. If it already exist in this exact way, how is it called? ___ Do you Yahoo!? Express yourself with Y! Messenger! Free. Download now. http://messenger.yahoo.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] What versions do I need to compile the fptools?
I want to compile all of the fptools. This is what I did: I got all files via CVS. And I did autoreconf ./configure make But with the make step gcc crashes with an internal error on Syntax.hi. I already filled in a bug report (not the most clear of them). I especially installed an "old" version of gcc (3.3.3)(I had gcc 3.4.1-2) to be able to compile the C Macro's correctly. For the Haskell compilation I used ghc-6.2.1. I think there is somewhere somebody that can compile it, but I need the *exact* versions of the software needed to do it. Is there anyone that *can* compile all of the fptools successfully? Regards, Ron __ Do you Yahoo!? New and Improved Yahoo! Mail - Send 10MB messages! http://promotions.yahoo.com/new_mail ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Laws in category theory..
I have been thinking about the following laws of a
monad. o is composition.
# associative law of a monad
mu o (mu o T) == mu o (T o mu)
The notation: Tmu, that's the same as T o mu, right?
How do I relate this to
x*(y*z) == (x*y)*z ?
# the identity law of a monad
mu o (T o eta) =={id}_\mathcal{C}= mu o (eta o T)
I also don't understand why I can't create the
following law out of the assocaitive law:
(mu o T) == (T o mu)
, bacause the first part of the expression is the
same.
Please, enlighten me :)
Regards, Ron
__
Do you Yahoo!?
New and Improved Yahoo! Mail - 100MB free storage!
http://promotions.yahoo.com/new_mail
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell-Cafe Digest, Vol 10, Issue 3
>G'day all.
Good day to you too.
>I don't know what you mean by "more complex". A dot
>is just a dot, and
>it has no internal structure that we can get at using
>category theory
>alone. Some dots may play specific roles in relation
>to other dots and
>arrows, but no dot is any more complex than any
other, >really.
Well, intuitvively seen, I meant. In some categories,
the dot might stand for a functor, and in some other
as a simple object.
>For a counter-example, think of the dual category
>Set^{op}. A morphism
>f : a -> b in that category means that there is a
>function f^{op} : b -> a
>
>where a and b are sets, however f probably isn't a
>function at all.
Well, what is it then?
I see a function as something where you put something
in and you get a result. In this case, you already
say, there is a morphism b->a, wel than the following
of b to a and return a then is a function?
A couple of days ago, I thought of the distinction
between a function and a morphism, as in that a
function operates on a hole set of objects, a.k.a.
domain. And a morphism only on one. Is that the
distinction you mean?
If all of the above is false, then probably I don't
know what a function is. (It looks like the more you
are busy with things, the less you seem to know of
it).
>In a category which is a partial order, there is a
>morphism f : a -> b
>if and only if a <= b. (Or is it a => b? Can never
>remember.) Here,
>the morphisms really have no internal structure at
>all. If the
>category
>has a finite number of objects, you can represent the
>whole thing using
>a bit matrix, and each morphism can be identified
with >a bit set to
>"true".
Preserving internal structure is not much more than
preservation of composition, right?
>I think the problem here is that you have the idea
>that a morphism is
>a process that turns one object into another. In
many >(probably most)
>interesting, practically significant cases, that's
>true, but it need
>not be.
Well, I think I don't know what a function is, because
the following of an arrow, represents at least for me
a clear mapping of turning one object in to another.
Or do you mean things like in logic, that you can see
the morphism, as relations (instances of axioms)
between logic objects.
So the morphism a->b would mean that a implicates b.
This way, the arrow is not a process of turning an a
into a b.
Hmm, that seems logical.
>I think it really helps to try to understand category
>theory mostly as
>a language for talking about things, and not
>necessarily "things" in
>and of themselves. Using this understanding, a
>morphism is a noun, not
>a verb. It's a concrete thing describing a
>relationship between
>objects,
>not necessarily an action that you perform on
objects.
I think you have already answered my question this
way. But a confirmation would be nice. It seems I had
to read your explanation >1 time.
>I don't know if any of this helps or not.
Well, it certainly helps.
Then the multiplication issue:
Is the following a good summary?
A multiplication is just a name for an operation that
is defined or not defined for each mathematical
construction in terms of to which laws the operation
should comply. The laws are then things like
communativity and so on.
Regards, Ron
__
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Join and it's relation to >>= and return
Hello again, I have thought a while about morphisms and although I had written down in my paper that a functor and also a natural transformation are also morphisms, but in a different category, I now am not sure anymore of this. If you see everything(objects and morphisms) as dots and arrows, and some arrows and some dots are just some more complex than others, then this holds, but is that legal? Intuitively seen, it is. According to some paper, morphisms are not like functions, in that you can apply some morphism to an object, but that you can only compose them. But I would say that if you have the morphism f:a->b, that is a arrow from dot a to dot b. That there clearly is a notion of following that arrow, in effect applying a function. And suppose there is the following path of morphisms: a>b>c>d, with a..d are dots. Then I would say there are three functions(constructed by composition)(in fact more, because of identity mapping) from a that when followed give new objects. This following of arrows, looks a lot like general function application, as in f(x) = 2x for example. It's btw quite hard to write the essence of monads down in a clear and precise way. I hope you can give some feedback on the above. Ragards, Ron P.S. The question about multiplication still stands. Probably multiplication is a set of laws defined on a mathematical object that must hold. And for each mathematical object there is such definition. Is this correct? __ Do you Yahoo!? Friends. Fun. Try the all-new Yahoo! Messenger. http://messenger.yahoo.com/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Join and it's relation to >>= and return
--- "Iavor S. Diatchki" <[EMAIL PROTECTED]> wrote: > hi ron, > > here are the relations between the two formulations > of monads: > (using haskell notation) > > map f m = m >>= (return . f) > join m = m >>= id > > m >>= f = join (fmap f m) > > there are quite a few general concepts that you need > to understand in what sense monads are monoids, but > to understand how monads work you don't need to know > that. > > Ron de Bruijn wrote: > > >I am pretty sure, that >>= is to monads what * is > to > >for example natural numbers, but I don't know what > the > >inverse of >>= is. And I can't really find it > anywhere > >on the web(papers, websites, not a single sole does > >mention it. > > > > > this is not quie correct. (join & return) for a > monad are like > (*,1) or (+,0) for the set of integers. however > those operations on > integers have more structure than join and return. > > there is no operation for "inverse". in mathematical > terms: > monads are a monoid (given that the notion is > generalized considerably > from its usual use), and not a group. > if one was to add such an operation > (i am not sure what it would do), but it would be of > type: > inverse :: M a -> M a (and of course must satisfy > some laws) > > also while you are pondering these things, it may be > useful to use > the "backward join" (=<<) :: (a -> m b) -> (m a -> m > b). > the reason for that is that strictly speaking tha > arrow in the middle > is different from the left and the right arrows > > i am not sure how useful this information is for > you, > but if you have more questions ask away > -iavor I found out what a group is: A group is a monoid each of whose elements is invertible. Only I still find it weird that join is called a multiplication, because according to the definition of multiplication, there should be an inverse. I think, thus that multiplication is only defined on a group. And now still remains: why do they call it a multiplication, while by definition it's not. Or should I understand it as: there's a concept called multiplication and for different structures there's a definition? I think, now I think over it, that it would seem logical. It could be possible that the definition is incorrect, though. Does anyone knows of a definition that is more general (and not absolute nonsens ;))? The information you give me is *very* usefull, because I don't just want to work with monads, I truly want to understand them. Ron __ Do you Yahoo!? Friends. Fun. Try the all-new Yahoo! Messenger. http://messenger.yahoo.com/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Join and it's relation to >>= and return
I am pretty sure, that >>= is to monads what * is to for example natural numbers, but I don't know what the inverse of >>= is. And I can't really find it anywhere on the web(papers, websites, not a single sole does mention it. It should have type, at least that's what I think: inv::M a->M b I say this, because I find this definition of a multiplication operation: 1. There exists a unique special element called neutral such that the operation on any element and the neutral does not change the element. 2. For every element there exists an inverse such that the operation on an element and its inverse is always neutral. 3. The operation is associative: it does not matter how you apply the operation to three elements. You may apply it to the first two and then to the result and the third element. Or you may first apply the operation to the last two and then to the first and the result of the previous operation. An operation may also be commutative 4. The order of two elements in operation is not important. According to 2 there should be an inverse. For join such an inverse is simple: to apply the type constructor on the monad. But I tried to somehow link it with bind, but than the types don't seem to match. So to be concrete: what's the inverse of bind? If I did make some errors, please tell me so. __ Do you Yahoo!? Friends. Fun. Try the all-new Yahoo! Messenger. http://messenger.yahoo.com/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Join and it's relation to >>= and return
Hello, The last 3 or 4 days I have been studying a lot of Category Theory so that I would be able to explain the concept of a monad to some people at the university in a "learn to present something"-course. newtype S a = State -> (a,State) -- functor T to map objects mapS::(a-> b) -> (S a -> S b) -- functor T to map morphisms unitS :: a -> S a --\eta joinS::S(S a)-> S a -- \mu This is a complete monad using a direct mapping from Category Theory. I really like it, because it's mathematically grounded. But I don't know how to map this to Haskell monads using the standard "bind" and "return", as I explain below. Although, I do believe I understand most parts of it(as in Functor, Natural Transformation and so on), I don't really understand how the join function (conventional monadic multiplication as it's called in the documentation) relates to the >>= and return functions that are mostly used. I read somewhere at Google that join can be expresed in terms of >>= and return, but I couldn't find it anymore. I also read that the Kleisli triple has more resemblance to how monads are used in practice, but it has some additional constraints. I don't understand why there are these additional constraints and I don't understand it's relevance, because according to some book there's a one-one mapping from monads to Kleisli triples and reverse. I also don't understand why join is a "multiplication", because a multiplication takes two operands (as in 5*4), at least all multiplication operators I know do so. I think what's happening is that one structure is taken out of the other. And then, the two are "merged" in some way. So this way, there are two operands. Is this correct? (I really could use a function definition in Haskell of join in terms of bind and return). Can somebody explain me (with a lot of detail) how this works? Regards, Ron __ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] 2-CNF Sat algorithm/haskell code
Dear Haskellers,
Today I searched over more than an hour on the web to
find an implementation of an algorithm that was first
written in the 1970's that solves 2-Conjuntive Normal
Form logical sentences in polynomial time.
The only thing I could find were some homework
assignments for students of universities and I learned
that there exist an algoritm for 2-CNF. Although I am
a student, what I am doing is no homework.
I believe the datastructure used was a strongly
connected graph (perhaps this rings any bells).
If you don't know any implementation in any imperative
language or functional language (not to far off when
compared to Haskell), a clear pseudo-code description,
either written by yourself or a URL to a webpage/paper
with that information would also be very welcome.
Thanks in advance,
Ron de Bruijn
P.S. This is really offtopic, but I would like to hear
some opinions about this project:
http://www.supercompilers.com/
I don't know whether they are for real, but when this
works it would greatly impacts the use of inefficient
functional programs(when applied to it ofcourse). Like
in Haskell,
a lot of programs could be written like:
[x|x<-someList, somePred x]
Although they computationally seen would be very slow,
without "supercompilation", with they would perform
just as good as some smart way of doing it.
__
Do you Yahoo!?
Yahoo! Mail - More reliable, more storage, less spam
http://mail.yahoo.com
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Sat solver
Hi there, I need a complete 3-CNF-Sat solver that can solve sentences of about length 20 (or shorter). Now I use simple model checking, but that's a bit slow , you understand :) I have seen some algorithms on the web and some code-sniplets in papers. But I presume there is some implementation available, so I thought: Let's ask, and don't reinvent the wheel. Greets Ron P.S. Thanks to those who answered my previous question, although I have found another way of expressing my problem. __ Do you Yahoo!? Yahoo! Finance: Get your refund fast by filing online. http://taxes.yahoo.com/filing.html ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Generalized list-comprehension
Hi there, I have written this little function: f :: (Num a, Enum a) => a -> [[a]] f n = [[a]|a<-fu n] ++ [a:[b]|a<-fu n,b<-fu n] ++ [a:b:[c]|a<-fu n,b<-fu n,c<-fu n] fu n = [1..n] This is an example of the function in action: *Mod> f 4 [[1],[2],[3],[4],[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3, 3],[3,4],[4,1],[4,2],[4,3],[4,4],[1,1,1],[1,1,2],[1,1,3],[1,1,4],[1,2,1],[1,2,2] ,[1,2,3],[1,2,4],[1,3,1],[1,3,2],[1,3,3],[1,3,4],[1,4,1],[1,4,2],[1,4,3],[1,4,4] ,[2,1,1],[2,1,2],[2,1,3],[2,1,4],[2,2,1],[2,2,2],[2,2,3],[2,2,4],[2,3,1],[2,3,2] ,[2,3,3],[2,3,4],[2,4,1],[2,4,2],[2,4,3],[2,4,4],[3,1,1],[3,1,2],[3,1,3],[3,1,4] ,[3,2,1],[3,2,2],[3,2,3],[3,2,4],[3,3,1],[3,3,2],[3,3,3],[3,3,4],[3,4,1],[3,4,2] ,[3,4,3],[3,4,4],[4,1,1],[4,1,2],[4,1,3],[4,1,4],[4,2,1],[4,2,2],[4,2,3],[4,2,4] ,[4,3,1],[4,3,2],[4,3,3],[4,3,4],[4,4,1],[4,4,2],[4,4,3],[4,4,4]] *Mod> This is ofcourse nice and all, but I need a function that does this same trick, but then doesn't only generate listelements of the maximum hard-coded length of three, but to length m, where m is an extra parameter. It's important that the elements are precisely in this order. I tried rewriting the listcomprehension to map, concat and filter, but that only complicated things. There is a possibility where I can write a function that gives the next of a list. So the next of [1,1,1] would be [1,1,2], but that would be somewhat inefficient when the list becomes large. Then I just call this function with (replicate n (head $ fu n)) and (last $ fu n). Then I just apply this function next to the rest, until I reach a state where all elements of the list equal the last value of the inputlist, so I have the required list of length n. Then to simply get the complete list as in function f. I need to map(\x->otherFunction x) [1..], but this "next"-function is almost identical to what the built-in listcomprehension does. I just don't like my solution. Then I can probably use Template Haskell(which I have never used), but that seems overkill. So does anyone has a better solution? Greets Ron __ Do you Yahoo!? Yahoo! SiteBuilder - Free web site building tool. Try it! http://webhosting.yahoo.com/ps/sb/ ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
XMLParser
Hi there,
I used the PARSEC parser combinator library to create
an following XML-Parser. It's not exactly XML, but
it's a usefull format for saving various data.
The big difference there is, is that I don't have
attributes, but those could easily be added, although
I don't need them.
Below is the complete code (20! lines of code for the
core). I was excited when I saw it also worked like I
had imagined, but then I tested it sometimes with
increasingly big data.
Using my test function below I noticed that there's
some exponentional behaviour. I don't see a reason for
this. Although I use the try combinator, it should at
max double the time, because the parser uses the other
parser when there occurs a parse error in the one.
My definition of xmlParser looks also a bit odd, but
without at least one of the functions
of(subEnTop,topEnSub) it will fail parsing.
I also don't understand why.
Then I question myself: why does my program work with
the downloaded version, and not with the PARSEC
library that ships with GHC 5.0.4.2, I atleast thought
that Parsec hasn't changed for a long time?
Does anyone have an explanation for the above
problems?
Greets Ron
module XMLCreator where
--this module can parse XML
import Parsec
import GHC.Show
import System.Time
--datatype om XML te representeren: XML bestaat altijd
uit een topelement en een aantal nestingen
data XML a = TopElement String [XML a]
| SubElement String a deriving Show
type Level = Int
--not finished Pretty Printer
ppXML::XML a->Level->String
ppXML (TopElement name (xml:xmls)) level = concat(take
level (repeat " "))++openTag name
ppXML _ _ = "hallo"
--ppXML (NestedElement name info) level =
openTag::String->String
openTag s = "<"++s++">"
--run :: Show a => Parser a -> String -> IO ()
run p input= do printTijd
case (parse p "" input) of
Left err -> do{ putStr "parse error
at ";
print err
}
Right x -> do print x
printTijd
--prints time(used above for printing the start time
and the endtime of the algoritm
printTijd = do time<-getClockTime
(putStrLn.show) time
test n = run xmlParser (concat(replicate n str))
--test n = parseTest xmlParser (concat(replicate n
str))
str::String
str =
"1forumTitletopicTitle100100someOnesomeOtherOne1234messageIDPW1421050767736105076267651059155053SomeProgramaboutText
";
--determine which sign can not be in the elementname
or in the informationpiece
signs = noneOf ['<','>']
--parses a piece of xml
xmlParser::Parser ([XML String])
xmlParser = choice [try (many1 sub),try topEnSub,try
subEnTop, many1 top]
--xmlParser = choice[try(many1 sub),many1 top]
getName::Parser String
getName = do teken '<'
name<-many1 signs
teken '>'
return name
where teken t = do skipMany space
char t
skipMany space
end::String->Parser String
end name = do skipMany space
string ("")
sub::Parser (XML String)
sub = do name<-getName
info<-many1 signs
end name
return (SubElement name info)
top::Parser (XML String)
top = do name<-getName
moreXml<-xmlParser
end name
return (TopElement name moreXml)
subEnTop::Parser [(XML String)]
subEnTop = do x<-many1 sub
y<-many1 top
return (x++y)
topEnSub::Parser [(XML String)]
topEnSub = do x<-many1 top
y<-many1 sub
return (x++y)
__
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: functional graph
--- Hal Daume <[EMAIL PROTECTED]> wrote: > >> I think that the > >> difficulties you are > >> facing are from the fact that you are trying to > >> express a purely > >> functional "updatable" graph. > > > > Should I understand from this, that this is a > > difficult problem and that there exist no easy way > to > > do this at the moment? > > Well, I think he was being a bit ironic. You can > either have a > functional graph or an updatable graph, but not > both. It sounds like > either would do and given that later in this message > you discuss that > you don't like imperativeness, then a functional > graph (ala the > Functional Graph Library -- FGL) would suit you > perfectly. > > > About the graphs:Well, I never had graphs at > school > > yet(first year student)... Although it is > somewhere in > > my textbooks... > > They're very simple. You have a collection of > nodes, N, and a > collection of edges between elements of N. Nodes > and edges can have > labels. So for instance you could have Teachers and > Classes as the > nodes and the edges could be between the teacher and > the class(es) which > go together. > > > To solve my problem... I need an mutable array, > but in > > Haskell my program will then be unbelievable > > imperative. > > No, you just need a graph :). > > > I have been following the discussion about the > graph > > and so, but the arrow classes and so on, are like > > something too sophisticated for me at this moment > I > > think, although I have some idea of how they work, > I > > really don't know when to apply them. I just found > > out, how Monads work, so... > > THe discussion about arrows is a complete > divergence. You don't need > anything about them. > > > But I certainly believe that my problem must be > fixed > > before it's easy to program in Haskell. > > Theorem: this problem is already fixed. > Proof: it is easy to program in Haskell. QED. > > :) > > - Hal I have read the chapter in my textbook :) and I have read and played with the FGL module. I must say the FGL module looks impressive, but I find it hard to start with it, because the most intuitive way of doing it for me was, to have different datatypes for Teacher Subject and so on. But it looks the Graph class works on types a and b where a is the Node type where b is the Edge type, or just the other way around :), I don't have the code right now. The above rules out my way of representing the data, or doesn't it (i.e. is there some fancy, magical way of doing this) ? The second intuitive solution is to take a datatype like data GraphNode|Teacher etc |Subject etc |Student etc Should this be the way to do it? And then yet another question: I need some kind of way to remember, which possibilities I already had. In example in my C++ program I used a couple of array's with in each array pointers to the StudentObjects, TeacherObjects. So I had the notion of the first teacher, the second teacher, the third and so on(in 0(1)), although I only need the notion of did I test this possibility and give me the next of Student/Teacher/whatever. I must be able to put it somewhere, but where? In the Graph itself there isn't really space for it, unless I create a complete timetable in the beginning with all Studentnodes pointing to this first teacher. But now I have to be able to change the Graph in such a way that I can change the first node where an error(schedulingerror) occurs, (for example a "room is full" error) to let the Student point to the next room(see the notion above). But then I yet have another problem. How can I guarantee, to do a complete path traversal, each time in exactly the same way? Greets Ron __ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: functional "updatable" graph
Are you sure that your data structure shouldn't be expressed by a graph? In that case, there is a very recent thread (last post today) on functional graph algorithms. I think that the difficulties you are facing are from the fact that you are trying to express a purely functional "updatable" graph. Should I understand from this, that this is a difficult problem and that there exist no easy way to do this at the moment? About the graphs:Well, I never had graphs at school yet(first year student)... Although it is somewhere in my textbooks... To solve my problem... I need an mutable array, but in Haskell my program will then be unbelievable imperative. I have been following the discussion about the graph and so, but the arrow classes and so on, are like something too sophisticated for me at this moment I think, although I have some idea of how they work, I really don't know when to apply them. I just found out, how Monads work, so... But I certainly believe that my problem must be fixed before it's easy to program in Haskell. Greets Ron __ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Multiple "pointers" to "objects"
Hi there, I was almost certain that Haskell was a great language until I wanted to make a real usefull program and got the following problem. I have data Lesson = Lesson Teacher SomeOtherProperties deriving Show data Subject = Subject Name [Teacher] SomeOtherProperties deriving Show data Teacher = Teacher TimeTable SomeOtherProperties What I want is that when I put some lesson in my timetable, the resources needed for that lesson are used up, so for example the timetable of a teacher will fill with each lesson that it gives. The problem is that when I "model" it this way, the state of the teachers that can give a certain subject will not change (suppose I have some function that fills one timeslot of the timetable of a teacher). It makes it even harder, because of the fact that one teacher can teach multiple subjects. In an OO-language I would simply let each element of the list of TeacherObjects of Subjects point to some TeacherObject, so it remembers it state, but that's anti-Haskell. It's ofcourse possible to put a list of Subjects that a Teacher teaches in the data declaration of the teacher. But then there is no way of saying efficiently (O(1) Just a pointer or index):"Give me a list of all teachers that give Physics", and that's just what I need. I could use a hashtable which includes the teachersobjects as values and the subjects as keys, but that isn't a very beautiful solution. This would give me(building of Hashtable O(n) and getting all teachers of some subject O(1)), so it would do. I am almost sure there exist some nice way of doing this, because otherwise Haskell would be completely useless IMHO, but I don't know it. Do you have any idea? Greets Ron __ Do you Yahoo!? SBC Yahoo! DSL - Now only $29.95 per month! http://sbc.yahoo.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
