[Haskell-cafe] Re: Literate programming
On Sat, 12 Jun 2010 17:10:07 -0400 aditya == aditya siram aditya.si...@gmail.com wrote: aditya Unfortunately literate programming doesn't really have the tool aditya support yet. I use emacs for Haskell development and loading aditya Haskell code in to the REPL will be an issue if you're editing aditya a noweb file. Currently this is the only thing keeping me from aditya starting a large ( 2000 LOC) literate project Nobody mentioned Leo (http://webpages.charter.net/edreamleo/front.html) editor which works as stand-alon editor or one can use it with Emacs/Vim... I plan to use it for my project... Sincerely, Gour -- Gour | Hlapicina, Croatia | GPG key: F96FF5F6 signature.asc Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Harder than you'd think
So the other day I was writing some code, and I ended up wanting to have a collection of data indexed in more than one way. In other words, I wanted fast lookup with several different keys. Initially I built something using two Data.Map objects to represent the two lookup keys, but then I needed up needing more keys per value than that, so I decided I should write a small library to abstract the whole thing. What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782 It sorta kinda works, but man, take a look at the first line. That's *a lot* of type-system abuse to make it go. And it strikes me that if you had two keys, both of which happen to have the same type (e.g., String)... what then? On the other hand, it's not like you can go lookup :: KeyID - Key - Container - Maybe Value since the type of both the container and the key depend on which key you want to access. Man, this is way, way harder than I realised! Does anybody have a less-insane way of doing this? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
On Sun, Jun 13, 2010 at 01:09:24PM +0100, Andrew Coppin wrote: Does anybody have a less-insane way of doing this? Did you take a look at happstack-ixset[1]? [1] http://hackage.haskell.org/package/happstack-ixset -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782 lookup :: KeyID - Key - Container - Maybe Value Does anybody have a less-insane way of doing this? Sure: type MyMap = Map (KeyID, Key) Value Don't use multiple keys. Put the keys into a tuple and use that as key. Let me know whether this is what you were looking for. I tried writing something like this. Yet SQL gives all this stiff for free. I still wonder which is the nicest way to express this data in Haskell without coding everything yourself.. Yours Marc Weber ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
Felipe Lessa wrote: On Sun, Jun 13, 2010 at 01:09:24PM +0100, Andrew Coppin wrote: Does anybody have a less-insane way of doing this? Did you take a look at happstack-ixset[1]? No. I'll take a look at it. (From the looks of it, it seems to be using TH and/or run-time checks to get around the type-system problems...) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
On 13 June 2010 15:23, Andrew Coppin andrewcop...@btinternet.com wrote: Felipe Lessa wrote: On Sun, Jun 13, 2010 at 01:09:24PM +0100, Andrew Coppin wrote: Does anybody have a less-insane way of doing this? Did you take a look at happstack-ixset[1]? No. I'll take a look at it. (From the looks of it, it seems to be using TH and/or run-time checks to get around the type-system problems...) A while ago I've written a simple version of ixset that uses type classes (without TH) as a proof of concept: http://darcs.monoid.at/tbox/Data/Index.hs Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
Marc Weber wrote: Does anybody have a less-insane way of doing this? Sure: type MyMap = Map (KeyID, Key) Value Don't use multiple keys. Put the keys into a tuple and use that as key. Let me know whether this is what you were looking for. Trouble is, this requires you to have *all* the keys to perform a single lookup. You can't do a lookup on just one attribute. I tried writing something like this. Yet SQL gives all this stiff for free. [Except that SQL bindings don't work on Windows. Besides, I'm only working with small data volumes, I don't need persistence or transaction guarantees, etc.] I still wonder which is the nicest way to express this data in Haskell without coding everything yourself.. Indeed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
Philippa Cowderoy wrote: On 13/06/2010 14:52, Andrew Coppin wrote: Marc Weber wrote: Does anybody have a less-insane way of doing this? Sure: type MyMap = Map (KeyID, Key) Value Don't use multiple keys. Put the keys into a tuple and use that as key. Let me know whether this is what you were looking for. Trouble is, this requires you to have *all* the keys to perform a single lookup. You can't do a lookup on just one attribute. No it doesn't - think sum/or, not product/and, your tuple's (KeyID, Key) not (Key1, Key2, Key3...). Oh, I see - so you enter (1, author), (2, date), (3, time), etc? That then requires all keys to have the same type - although I think for my needs I can put together an ADT to fix that... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Difficulties with tagless - create primitives or compose them
Excellent answer! Splitting the Symantics class into pieces is one of the techniques that we didn't need for solving the original problem (tagless partial evaluation without resorting to fancy types) that set us on this track. Which is too bad, because it would have made a nice addition. The 'typecase pattern', on the other hand, was one of the explicit techniques we did use. One of these days, Oleg, Ken and I need to write a follow-up on this, as the code contains a number of extra techniques (in the advanced partial evaluation parts) which were not explained in our paper. And, of course, Oleg's added a number of refinements to the general technique [see his web site]. I must admit that I find it amusing that most people seem to use finally-tagless for writing interpreters, while we created it for partial evaluation and program transformation! [It also allows you to do certain kinds of program analyses, but one needs additional techniques to make that comfortable - another thing to write up properly]. Jacques ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Difficulties with tagless - create primitives or compose them
Dear Jacques, I have recently found something new that might also prove to be useful for EDSLs. http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html Dan's blog post doesn't give any code or implementation but in a way it tackles the same problem, and since you also mention partial evaluation and transformation you might also find this interesting. Then again this might be an old hat to you :) Best regards Günther ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Harder than you'd think
Marc Weber wrote: Andrew Coppin wrote: What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782 lookup :: KeyID - Key - Container - Maybe Value Does anybody have a less-insane way of doing this? Sure: type MyMap = Map (KeyID, Key) Value Don't use multiple keys. Put the keys into a tuple and use that as key. Actually, it's a disjoint sum type: data a :+: b = Inl a | Inr b -- also known as Either type DB3 e k1 k2 k2 = D1 e (k1 :+: k2 :+: k3) Hm, that's not quite right either because every e has multiple keys. The following should work, however: type DB3 e k1 k2 k2 = D1 e k1 :*: DB1 e k2 :*: DB2 e k3 lookup :: (k1 :+: k2 :+: k3) - DB3 e k1 k2 k3 - Maybe e In any case, I recommend using a special key type for combining keys anyway, as explained here http://article.gmane.org/gmane.comp.lang.haskell.cafe/23648 Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Graph type
Hi, I am trying to write a routine that would generate a graph - where each vertex would be a string. type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent vertices list addEdgeToGraph :: Graph - String - String - Graph I am having trouble coming up with the body of this function - that takes the original graph, and an edge (string - string) and the produces the new graph. -- Regards, Kashyap ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Harder than you'd think
Hello, My idea for solving this problem was to try to use something similar to a kd-tree. I have a proof of concept for 2 keys here: http://src.seereason.com/haskell-kdmap/ But, to extend it to an arbitrary number of keys may need template haskell. The basic concept is to build a (balanced) tree (the same way Data.Map does). But instead of using the same key at every level of the tree, you cycle through the keys. For example, if you are inserting a type which has keys that are Int and Char. At the first level of the tree you might use the Int key to decide if you should insert on the left or right. At the second level, you use the Char to decide left or right, at the third level Int again, and so on. It is fine if the keys are the same type (Int, Int). The first level you would use the first Int, the second level the second Int, the third level the first Int, and so on. Unlike multiple maps, each value only appears in one place. This should make it easier to handle updates/deletes, which are pretty tricky in the multiple map solution. You can do lookups on a single (or multiple keys). For example, if you want to do a lookup only the Int value, then at the first level you compare the int key and go left or right. At the Char level you go both left and right, and join the results. At the next Int levels you go left or right, and so on. There is a also supposedly a more type-safe variant of IxSet somewhere, but I am not sure where it is offhand. - jeremy On Jun 13, 2010, at 7:09 AM, Andrew Coppin wrote: So the other day I was writing some code, and I ended up wanting to have a collection of data indexed in more than one way. In other words, I wanted fast lookup with several different keys. Initially I built something using two Data.Map objects to represent the two lookup keys, but then I needed up needing more keys per value than that, so I decided I should write a small library to abstract the whole thing. What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782 It sorta kinda works, but man, take a look at the first line. That's *a lot* of type-system abuse to make it go. And it strikes me that if you had two keys, both of which happen to have the same type (e.g., String)... what then? On the other hand, it's not like you can go lookup :: KeyID - Key - Container - Maybe Value since the type of both the container and the key depend on which key you want to access. Man, this is way, way harder than I realised! Does anybody have a less-insane way of doing this? ___ 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] Harder than you'd think
Excerpts from Jeremy Shaw's message of Sun Jun 13 19:16:02 +0200 2010: Hello, My idea for solving this problem was to try to use something similar to a kd-tree. I have a proof of concept for 2 keys here: http://src.seereason.com/haskell-kdmap/ But, to extend it to an arbitrary number of keys may need template haskell. I tried this. TH changed a little bit so it may be broken. I mapped multi keys to Data.Map Key1 (Data.Map Key 2) http://github.com/MarcWeber/rdmhaskell/ I gave up the project that time due to lack of time and because spending so much time on this project was not worth the time because Postgres and MYSQL already did what I was looking for.. The idea was to model kind of database because I wasn't satisfied with IxSet that time. line 50 shows how to define a combined index on two fields: http://github.com/MarcWeber/rdmhaskell/blob/master/test/TestCase.hs I'm not even sure whether I should recommend reading my code :) All I want to say: Its a little bit of work which is highly appreciated by many Haskellers IMHO. If you start such a project keep posting updates to the list. I'll read them. Marc Weber ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Graph type
* C K Kashyap ckkash...@gmail.com [2010-06-13 22:45:44+0530]
Hi,
I am trying to write a routine that would generate a graph - where each
vertex would be a string.
type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent
vertices list
addEdgeToGraph :: Graph - String - String - Graph
I am having trouble coming up with the body of this function - that takes
the original graph, and an edge (string - string) and the produces the new
graph.
If you know that the vertices already exist and you need only to add an
edge, then you just go through all the vertices, compare current vertex
to given ones and if they match add a vertex.
\begin{code}
addEdgeToGraph :: Graph String - String - String - Graph String
addEdgeToGraph gr v1 v2 = map modify gr
where
modify (v,vs) | v == v1 = (v,v2:vs)
modify (v,vs) | v == v2 = (v,v1:vs)
modify x = x
\end{code}
Otherwise it is possible that one (or both) vertex doesn't exist yet, so
you first need to try the first version, and if at least one of the
vertex is not found, add it to the list. You can use fold for this.
\begin{code}
addEdgeToGraph' :: Graph String - String - String - Graph String
addEdgeToGraph' gr v1 v2 =
let (newgr, (foundV1, foundV2)) = foldr modify ([],(False,False)) gr
in
(if foundV1 then [] else [(v1,[v2])]) ++
(if foundV2 then [] else [(v2,[v1])]) ++
newgr
where
modify (v,vs) (lst,(_,foundV2)) | v == v1 = ((v,v2:vs):lst, (True,foundV2))
modify (v,vs) (lst,(foundV1,_)) | v == v2 = ((v,v1:vs):lst, (foundV1,True))
modify v (lst,f) = (v:lst,f)
\end{code}
--
Roman I. Cheplyaka :: http://ro-che.info/
Don't let school get in the way of your education. - Mark Twain
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Announce: Properties-0.0.2
http://hackage.haskell.org/package/properties-0.0.2 http://hackage.haskell.org/package/properties-0.0.2Properties can use QuickCheck properties in the same way than assertions are used, for causal debugging of real programs. It also add an human readable structure for grouping properties for classes or libraries. The properties can then be tested in the instance´s body or in programs as if they were assertions. The main advantage is that the compliance of properties can be done with the complete data range that the real application generates (hopefully, with an pleasant separation of real code and debug code). This is a simple example: stringProperty= [Property http://hackage.haskell.org/packages/archive/properties/0.0.2/doc/html/Test-Properties.html#t%3AProperty length (\(x, y)- length (x++y)== length x + length y)] main= do let s= hello let s2= world print $ s++ s2 `verify http://hackage.haskell.org/packages/archive/properties/0.0.2/doc/html/Test-Properties.html#v%3Averify` stringProperty `with http://hackage.haskell.org/packages/archive/properties/0.0.2/doc/html/Test-Properties.html#v%3Awith`(s,s2) print that's all! It is possible to check quickCheck style properties. The same example with a quickCheck-style property: quickCheckProperty x y= length (x++y)== length x + length y main= do let s= hello let s2= world print $ s++ s2 `verify http://hackage.haskell.org/packages/archive/properties/0.0.2/doc/html/Test-Properties.html#v%3Averify` [Property stringSumLength $ uncurry quickCheckProperty] `with http://hackage.haskell.org/packages/archive/properties/0.0.2/doc/html/Test-Properties.html#v%3Awith`(s,s2) print that's all! The package include a more sophisticated example. I Hope that this would be useful Alberto ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How to browse code written by others
Hello all, I need your advice about how to browse code which was written by someone else (Paul Hudak's Euterpea, to be precise, apx. 1 LOC). I had set some hopes on leksah, and it indeed shows me the interfaces, but I have not yet convinced it to show me more than that. I ran haddock over the sources, and again I could not see more that just signatures. I would be very happy with something like a Smalltalk browser. Something that would let me zoom down to the source code, but with search and hyperlink capabilities (senders and implementers in Smalltalk). Anyways, how do you guys do it, i.e. how to you dive into non-trivial foreign code? -- Martin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to browse code written by others
Hi Martin With Haddock you can also make the highlighted source as per docs hosted on Hackage. Install hscolour, then when you invoke haddock on the cabal file add the --hyperlink-source flag. No hyperlinks in the source though, just colourization. Thomas Hallgren had another source-to-html tool with hyperlinks in the html source rather than just colourizing, but I'm not sure what happened to it - maybe it is part of Programatica? http://ogi.altocumulus.org/~hallgren/Programatica/ Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How to browse code written by others
Excerpts from Martin Drautzburg's message of Sun Jun 13 22:32:18 +0200 2010: Anyways, how do you guys do it, i.e. how to you dive into non-trivial foreign code? I use Vim and tag files generated by Vim. Using gnu idutils or such you can find any occurences of words very fast in large code bases. Of course they are not language aware but they often get the job done. I'd like to share all my scripts. Write me an email if you're interested. Marc Weber ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] parsec: how to get end location
Suppose I have some parser 'p'. I want to parse it as well as get its
span in the text. So I could write
\begin{code]
pWithLocation = do
loc_start - getPosition
pval - p
loc_end - getPosition
return (pval,loc_start,loc_end)
\end{code}
except that loc_end gives me the location _after_ 'p'. In case when 'p'
has consumed trailing newline I see no way to recover the end location
of 'p' (it is the last column of the previous line).
So, can I do anything with this without patching parsec?
I use parsec3 if it matters.
--
Roman I. Cheplyaka :: http://ro-che.info/
Don't let school get in the way of your education. - Mark Twain
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] parsec: how to get end location
On Sun, Jun 13, 2010 at 4:17 PM, Roman Cheplyaka r...@ro-che.info wrote:
Suppose I have some parser 'p'. I want to parse it as well as get its
span in the text. So I could write
\begin{code]
pWithLocation = do
loc_start - getPosition
pval - p
loc_end - getPosition
return (pval,loc_start,loc_end)
\end{code}
except that loc_end gives me the location _after_ 'p'. In case when 'p'
has consumed trailing newline I see no way to recover the end location
of 'p' (it is the last column of the previous line).
So, can I do anything with this without patching parsec?
I use parsec3 if it matters.
Can you use a parser which doesn't consume leading/trailing whitespace?
Or somehow layer the parsers so that the whitepsace munching happens
outside of parseWithLocation.
Antoine
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] parsec: how to get end location
* Antoine Latter aslat...@gmail.com [2010-06-13 16:47:28-0500]
On Sun, Jun 13, 2010 at 4:17 PM, Roman Cheplyaka r...@ro-che.info wrote:
Suppose I have some parser 'p'. I want to parse it as well as get its
span in the text. So I could write
\begin{code]
pWithLocation = do
loc_start - getPosition
pval - p
loc_end - getPosition
return (pval,loc_start,loc_end)
\end{code}
except that loc_end gives me the location _after_ 'p'. In case when 'p'
has consumed trailing newline I see no way to recover the end location
of 'p' (it is the last column of the previous line).
So, can I do anything with this without patching parsec?
I use parsec3 if it matters.
Can you use a parser which doesn't consume leading/trailing whitespace?
Or somehow layer the parsers so that the whitepsace munching happens
outside of parseWithLocation.
Of course most parsers don't consume trailing newlines. But I was
writing general function to use in many places in the code which would
recover the end location. In most cases it just subtracts 1 from the
column number, but what if it just happened so that column number is 1?
So I got an impression that this way of obtaining the end location is at
least ugly. It would be better if there was a function
parseWithLocation :: Parser a - Parser (a, SourcePos, SourcePos)
which, I guess, is easy to implement within Parsec without any such
hacks.
--
Roman I. Cheplyaka :: http://ro-che.info/
Don't let school get in the way of your education. - Mark Twain
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] parsec: how to get end location
On Mon, Jun 14, 2010 at 12:10 AM, Roman Cheplyaka r...@ro-che.info wrote: Of course most parsers don't consume trailing newlines. But I was writing general function to use in many places in the code which would recover the end location. In most cases it just subtracts 1 from the column number, but what if it just happened so that column number is 1? Parsec can handle state, right ? You could modify the parsers for white space so they record the beginning position in some state. ( In a maybe ) Then, modify parseWithLocation to set the state position to nothing, parse p then if no position has been recorded in the state , use the current position, else use the position in the state. Excuse me if this is unclear or confused, it's late :) David. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Graph type
I love this list ... thanks Roman.
I take it that there is nothing obviously inefficient about this approach to
graph - as in the graph type.
On Mon, Jun 14, 2010 at 12:02 AM, Roman Cheplyaka r...@ro-che.info wrote:
* C K Kashyap ckkash...@gmail.com [2010-06-13 22:45:44+0530]
Hi,
I am trying to write a routine that would generate a graph - where each
vertex would be a string.
type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent
vertices list
addEdgeToGraph :: Graph - String - String - Graph
I am having trouble coming up with the body of this function - that takes
the original graph, and an edge (string - string) and the produces the
new
graph.
If you know that the vertices already exist and you need only to add an
edge, then you just go through all the vertices, compare current vertex
to given ones and if they match add a vertex.
\begin{code}
addEdgeToGraph :: Graph String - String - String - Graph String
addEdgeToGraph gr v1 v2 = map modify gr
where
modify (v,vs) | v == v1 = (v,v2:vs)
modify (v,vs) | v == v2 = (v,v1:vs)
modify x = x
\end{code}
Otherwise it is possible that one (or both) vertex doesn't exist yet, so
you first need to try the first version, and if at least one of the
vertex is not found, add it to the list. You can use fold for this.
\begin{code}
addEdgeToGraph' :: Graph String - String - String - Graph String
addEdgeToGraph' gr v1 v2 =
let (newgr, (foundV1, foundV2)) = foldr modify ([],(False,False)) gr
in
(if foundV1 then [] else [(v1,[v2])]) ++
(if foundV2 then [] else [(v2,[v1])]) ++
newgr
where
modify (v,vs) (lst,(_,foundV2)) | v == v1 = ((v,v2:vs):lst,
(True,foundV2))
modify (v,vs) (lst,(foundV1,_)) | v == v2 = ((v,v1:vs):lst,
(foundV1,True))
modify v (lst,f) = (v:lst,f)
\end{code}
--
Roman I. Cheplyaka :: http://ro-che.info/
Don't let school get in the way of your education. - Mark Twain
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Regards,
Kashyap
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Graph type
C K Kashyap ckkash...@gmail.com writes:
I love this list ... thanks Roman.
I take it that there is nothing obviously inefficient about this approach to
graph - as in the graph type.
Sure there is (using p = |V|, q = |E|):
* Finding a particular node is O(p).
* Adding an edge to an already existing node is also O(p).
* Finding reverse edges is O(q) (probably more actually since you'd be
checking every node that you have and then checking if the other end
is in the list of relationships).
etc.
The main advantage of your type is that it's O(1) to add a new node +
successor edges.
Now, depending upon what you're wanting to do, this may suffice.
However, there are a couple of alternatives:
* Use Data.Graph from containers
* Use either Data.Graph.Inductive.Tree or
Data.Graph.Inductive.PatriciaTree (which has better performance but
doesn't allow multiple edges) from fgl.
* If you still want a custom type, then something like Map v (Set v)
would be much more efficient than using [(v, [v])] (this could be
improved at the expense of disk space and more bookkeeping by using
Map v (Set v, Set v) to store both successor and predecessor edges).
On Mon, Jun 14, 2010 at 12:02 AM, Roman Cheplyaka r...@ro-che.info wrote:
* C K Kashyap ckkash...@gmail.com [2010-06-13 22:45:44+0530]
Hi,
I am trying to write a routine that would generate a graph - where each
vertex would be a string.
type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent
vertices list
addEdgeToGraph :: Graph - String - String - Graph
I am having trouble coming up with the body of this function - that takes
the original graph, and an edge (string - string) and the produces the
new
graph.
If you know that the vertices already exist and you need only to add an
edge, then you just go through all the vertices, compare current vertex
to given ones and if they match add a vertex.
\begin{code}
addEdgeToGraph :: Graph String - String - String - Graph String
addEdgeToGraph gr v1 v2 = map modify gr
where
modify (v,vs) | v == v1 = (v,v2:vs)
modify (v,vs) | v == v2 = (v,v1:vs)
modify x = x
\end{code}
Otherwise it is possible that one (or both) vertex doesn't exist yet, so
you first need to try the first version, and if at least one of the
vertex is not found, add it to the list. You can use fold for this.
\begin{code}
addEdgeToGraph' :: Graph String - String - String - Graph String
addEdgeToGraph' gr v1 v2 =
let (newgr, (foundV1, foundV2)) = foldr modify ([],(False,False)) gr
in
(if foundV1 then [] else [(v1,[v2])]) ++
(if foundV2 then [] else [(v2,[v1])]) ++
newgr
where
modify (v,vs) (lst,(_,foundV2)) | v == v1 = ((v,v2:vs):lst,
(True,foundV2))
modify (v,vs) (lst,(foundV1,_)) | v == v2 = ((v,v1:vs):lst,
(foundV1,True))
modify v (lst,f) = (v:lst,f)
\end{code}
--
Roman I. Cheplyaka :: http://ro-che.info/
Don't let school get in the way of your education. - Mark Twain
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Graph type
Thanks Roman.
I think I'll try out Data.Graph in that case.
On Mon, Jun 14, 2010 at 8:53 AM, Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com wrote:
C K Kashyap ckkash...@gmail.com writes:
I love this list ... thanks Roman.
I take it that there is nothing obviously inefficient about this approach
to
graph - as in the graph type.
Sure there is (using p = |V|, q = |E|):
* Finding a particular node is O(p).
* Adding an edge to an already existing node is also O(p).
* Finding reverse edges is O(q) (probably more actually since you'd be
checking every node that you have and then checking if the other end
is in the list of relationships).
etc.
The main advantage of your type is that it's O(1) to add a new node +
successor edges.
Now, depending upon what you're wanting to do, this may suffice.
However, there are a couple of alternatives:
* Use Data.Graph from containers
* Use either Data.Graph.Inductive.Tree or
Data.Graph.Inductive.PatriciaTree (which has better performance but
doesn't allow multiple edges) from fgl.
* If you still want a custom type, then something like Map v (Set v)
would be much more efficient than using [(v, [v])] (this could be
improved at the expense of disk space and more bookkeeping by using
Map v (Set v, Set v) to store both successor and predecessor edges).
On Mon, Jun 14, 2010 at 12:02 AM, Roman Cheplyaka r...@ro-che.info
wrote:
* C K Kashyap ckkash...@gmail.com [2010-06-13 22:45:44+0530]
Hi,
I am trying to write a routine that would generate a graph - where
each
vertex would be a string.
type Graph v = [(v,[v])] -- list of tuples of vertices and adjacent
vertices list
addEdgeToGraph :: Graph - String - String - Graph
I am having trouble coming up with the body of this function - that
takes
the original graph, and an edge (string - string) and the produces
the
new
graph.
If you know that the vertices already exist and you need only to add an
edge, then you just go through all the vertices, compare current vertex
to given ones and if they match add a vertex.
\begin{code}
addEdgeToGraph :: Graph String - String - String - Graph String
addEdgeToGraph gr v1 v2 = map modify gr
where
modify (v,vs) | v == v1 = (v,v2:vs)
modify (v,vs) | v == v2 = (v,v1:vs)
modify x = x
\end{code}
Otherwise it is possible that one (or both) vertex doesn't exist yet, so
you first need to try the first version, and if at least one of the
vertex is not found, add it to the list. You can use fold for this.
\begin{code}
addEdgeToGraph' :: Graph String - String - String - Graph String
addEdgeToGraph' gr v1 v2 =
let (newgr, (foundV1, foundV2)) = foldr modify ([],(False,False)) gr
in
(if foundV1 then [] else [(v1,[v2])]) ++
(if foundV2 then [] else [(v2,[v1])]) ++
newgr
where
modify (v,vs) (lst,(_,foundV2)) | v == v1 = ((v,v2:vs):lst,
(True,foundV2))
modify (v,vs) (lst,(foundV1,_)) | v == v2 = ((v,v1:vs):lst,
(foundV1,True))
modify v (lst,f) = (v:lst,f)
\end{code}
--
Roman I. Cheplyaka :: http://ro-che.info/
Don't let school get in the way of your education. - Mark Twain
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
--
Regards,
Kashyap
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Mining Twitter data in Haskell and Clojure
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
[Haskell-cafe] learning advanced haskell
Hi Cafe, I've been doing Haskell for a few months, and I've written some mid-sized programs and many small ones. I've read lots of documentation and many papers, but I'm having difficulty making the jump into some of the advanced concepts I've read about. How do people build intuitions for things like RankNTypes and arrows? (Is the answer Get a PhD in type theory?) Normally I learn by coding up little exercise programs, but for these I don't have good intuitions about the kinds of toy problems I ought to try to solve that would lead me to understand these tools better. For systems like Template Haskell and SYB, I have difficulty judging when I should use Haskell's simpler built-in semantic abstractions like functions and typeclasses and when I should look to these other mechanisms. I understand the motivation for other concepts like iteratees, zippers and functional reactive programming, but there seem to be few entry-level resources. John Lato's recent Iteratee article is a notable exception*. Hints? Tips? Here's how I did it? ___ is a great program to write to get to learn __? Thanks in advance, Aran * Even in this article, he busted out (=). And it appears that the iteratee library's actual design is more sophisticated than the design presented. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Mining Twitter data in Haskell and Clojure
deliverable: 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. Hey. Very cool! When you run it with +RTS -s what amount of time is being spent in garbage collection? What are you main data types? When you compile with -prof -auto-all and do some heap profiling, what do you see? There's an introduction to profiling with GHC's heap and time tools here: http://book.realworldhaskell.org/read/profiling-and-optimization.html#id677729 Either way: * step one: do time profiling * step two: do space/heap profiling * look at the main data types being allocated and improve their representation. * look at the main functions using time, and improve their complexity. * iterate until happy. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
