- Haskell-Cafe - Haskell.org

Using Set: Hypergraph type
by Eray Ozkural 04 Sep '01

04 Sep '01

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Greetings all! I'm a new Haskell user. I've used Haskell for a number of small hacks and I can say that this is a brilliant language. I was just working on a hypergraph implementation in haskell. A hypergraph, for those not familiar with it, is a family of sets which are subsets of a vertex set X. I went straight along the mathematical definition, and I decided to try the Edison library that came along with my ghc-5.00.2 Without further ado, here is the code: type Hypergraph n = Set (Set n) - -- hgraph constructor - -- takes a list of edges hgraph edge_list = unionManySets (map mkSet edge_list) My trouble is that this does not seem to work well. Perhaps it's my lack of experience wih Edison, but the types do not seem to be right and the following expression fails to evaluate: Hypergraph> elementOf (mkSet [1]) (hgraph [ [1,2], [1] ]) I expect "True" in response to this query. Anyway, I think this is not ghc specific. (I enabled -fglasgow-exts, no difference. I get a lot of type errors...) What do you think is wrong with this code? It now seems to me that I may not be able to use Edison for my ADT, so how would you recommend me to go about coding this mathematical definition? All I need is to be able to define a set of sets in a convenient way; it also has to be halfway efficient. Should I implement this with lists, or is there an alternative set implementation which allows me to accomplish a decent hypergraph definition? [*] Regards, [*] I could also use a mix of arrays and lists it seems, similar to the edge list and pin list representations used in imperative code. But that does not give me the interface a set implementation would :) - -- Eray Ozkural (exa) <erayo(a)cs.bilkent.edu.tr> Comp. Sci. Dept., Bilkent University, Ankara www: http://www.cs.bilkent.edu.tr/~erayo GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE7lKJQfAeuFodNU5wRAtyBAJ0SCRLAV5u4IBkt3B2VIYB04l9LNACeNL0Y GE9TPhrWoPY6rH58ZDSdweg= =IdNC -----END PGP SIGNATURE-----

3 7

Re: Using Set: Hypergraph type
by Marcin 'Qrczak' Kowalczyk 04 Sep '01

04 Sep '01

Tue, 4 Sep 2001 21:12:41 +0300, Eray Ozkural <erayo(a)cs.bilkent.edu.tr> pisze: > Thanks for the suggestion, but isn't this a bit inefficient? Ordinarily one > would like to compare two elements of a set by reference, not by content. There is no such thing in Haskell. mkSet [mkSet [1, 2]] is indistinguishable from mkSet [mkSet [1, 2]] even if {1,2} sets were created independently. Whether representations of particular mkSet [1, 2] objects are shared is an implementation detail. Well, there are compiler-dependent unsafe functions which could detect sharing, but they are not normally used. Functional programming is about values, not about objects with identities. You could implement a "tagged object" type, like data Tagged a = Tagged Integer a give objects unique numbers as they are created, and make Eq and Ord instances which compare these numbers only, ignoring the real value. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

Re: Using Set: Hypergraph type
by Marcin 'Qrczak' Kowalczyk 04 Sep '01

04 Sep '01

Tue, 4 Sep 2001 20:28:55 +0300, Eray Ozkural <erayo(a)cs.bilkent.edu.tr> pisze: > Okay, I guess I got it now. The (types of) elements of a Set ought > to be instances of Ord. So I presume Edison supports only flat sets. You can add an inefficient implementation of Ord (Set a) yourself: instance Ord a => Ord (Set a) where compare s1 s2 = compare (toOrdList s1) (toOrdList s2) toOrdList seems to be exported only module Collection. If more than one module does this, they can't be used together. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

some problem question
by karan babuta 02 Sep '01

02 Sep '01

hi there i am having some problem with the haskell question. if u can help me in that will really be appreciated. thanks for help. MY PROBLEM IS WITH THE SEPERATING THE SHAPES IN A GRID waiting for a sooner reply.THANKS here is the question: A rectangular grid is list of list of Char, where all inner lists are of the same length ie. type Grid = [[Char]] . Inside this grid, white space will be denoted by a '.' and filled pixels will be denoted by '*'. For example, a grid containing a square may look like square :: Grid square = ["............", "............", "...****.....", "...****.....", "...****.....", "...****.....", "............" ] The shapes can be anywhere inside the grid and they can can be of any size > 2 x 2 . That is, the only restriction on the size of the shape is a minimum of 2 x 2 area on the grid. And in cases of non-square, the shape will at least occupy 4 pixels. You can assume that no shape given will be smaller than this and that the shapes given will distinctly fall into one of the categories and will not be ambiguous. There is no restriction on the size of the grid itself, but obviously, it must fully contain the shape(s). There can be either one or two shape(s) inside a grid, but if there are two shapes in the grid, then they are guarenteed to be at least 1 pixel apart, and that they can be separated by cutting the grid either horizontally or vertically. twoTriangles :: Grid twoTriangles = ["....................", "....................", "...........*********", ".....*......*******.", "....***......*****..", "...*****......***...", "..*******......*....", "...................."] Shapes The following shapes are allowed inside a grid : RECTANGLE - The very same rectangle as we all know it. It will not be rotated. TRIANGLE - If it looks like a triangle, then it's a triangle. Note that this means the length of the three edges can be different, and it can be rotated in any way. (You'll notice that this is a very ambiguous definition of a triangle. Within the restraints of this specification, including that (1) all shapes given will be valid. (2) there are only three shapes to be identified. and (3) definition of the other shapes are unambiguous and rigid. You should think about how you can identify the triangle using the simplist way you can think of.) DIAMOND - Any thing that has a shape like [".............", ".............", ".............", ".....*.......", "....***......", "...*****.....", "..*******....", "...*****.....", "....***......", ".....*.......", "............."] To make this easy, a diamond will have horizontal symmetry as well as vertical symmetry. Tasks You are to write the following functions: areaOfOneShape:: Grid -> Int For the shape in the grid, you should count the number of pixels it occupies. (ie, count the number of '*' for each shape), and return the count. recogniseOneShape:: Grid -> String The input Grid will be as describe above, with only ONE shape in the grid, and the output String should be the name of the shapes, eg, "RECTANGLE" Note: You MUST capitalise the name of the shapes in the string you returned, and you MUST spell the name of the shapes correctly The ONLY names of the shapes allowed are the ones described above in the Shapes section PROBLEM: separateShapes :: Grid -> [Grid] The input Grid will contain either one or two shapes. You are to separate the shapes into separate Grids, where each contains a whole shape respectively; ie, if there are two shapes in the original Grid, then you should return two Grids containing a shape each. If there is only one shape in the orignal Grid, then you should just return a list containing a single Grid. The Grids returned must also be rectangular. areaOfShapes :: Grid -> [Int] You should return the area of the shapes. If there is only one shape, then the output will just be a list with one Int. If there are two shapes, then the output will be a list of two Int. The order of the integer returned does not matter. You should (but you don't have to) write this function using functions already defined above. recogniseShapes :: Grid -> [String] Give a Grid containing one or two shapes, return a list of String of the names of the shapes. If there are two shapes, then you can return the name of the two shapes in any order you like. Eg, If there is a triangle and a diamond in the grid, then you should return ["TRIANGLE", "DIAMOND"] (the order of the names does not matter). If there is just a single shape, then you just return a list with a single string, eg, ["RECTANGLE"]. You should (but you don't have to) write this function using functions already defined above. ____________________________________________________________ Do You Yahoo!? Get your free @yahoo.co.uk address at http://mail.yahoo.co.uk or your free @yahoo.ie address at http://mail.yahoo.ie

2 1

Re: hiding import, tuple instances
by Ashley Yakeley 01 Sep '01

01 Sep '01

At 2001-08-31 13:59, I wrote: >At 2001-08-31 09:27, Marcin 'Qrczak' Kowalczyk wrote: > >>> How do I define functions that work on all tuples? >> >>You can't, and this is unfortunate. > >You can make your own 'tuples' using cons = (,) and nil = (). Then you >can use multi-parameter classes to manipulate them. See, for instance, <http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/truth-framework/Source/Type Calc/ListType.hs?rev=HEAD&content-type=text/vnd.viewcvs-markup> ListType> concatenate ('p',(3,(False,()))) ("Hello",(7,())) ('p',(3,(False,("Hello",(7,()))))) -- Ashley Yakeley, Seattle WA

1 0

classes
by Cagdas Ozgenc 31 Aug '01

31 Aug '01

Hi, I am a newbie, so I might be making nonsense. In the following definiton: class Eq a where (==) :: a -> a -> Bool Why do we conlude that both of the "a" refer to the same type? Apparently using different types that both belonging to class Eq results in an error. For example 65 == 'a' It doesn't make much sense at first, however, how do you go by implementing multiple polymorphism? Secondly, why does Haskell distinguish between a Type and a Class? There seems to be no benefit of such approach. Thirdly, is it possible to define meta-classes in Haskell? Thanks

4 5

Re: hiding import, tuple instances
by Ashley Yakeley 31 Aug '01

31 Aug '01

At 2001-08-31 09:27, Marcin 'Qrczak' Kowalczyk wrote: >> How do I define functions that work on all tuples? > >You can't, and this is unfortunate. You can make your own 'tuples' using cons = (,) and nil = (). Then you can use multi-parameter classes to manipulate them. -- Ashley Yakeley, Seattle WA

1 0

Re: hiding import, tuple instances
by Marcin 'Qrczak' Kowalczyk 31 Aug '01

31 Aug '01

Fri, 31 Aug 2001 18:53:11 +0300, Cagdas Ozgenc <co19(a)cornell.edu> pisze: > 1) How can I hide an instance of a class imported from prelude? You can't. A given class/type pair must have at most one instance in the whole program. > How do I define functions that work on all tuples? You can't, and this is unfortunate. -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

hiding import, tuple instances
by Cagdas Ozgenc 31 Aug '01

31 Aug '01

Hi, 1) How can I hide an instance of a class imported from prelude? For example I would like to redefine instance (Ord a, Ord b) => Ord (a,b) where (<=) (x,y) (z,w) | x < z = True | x == z = if y <= w then True else False | otherwise = False for educational purposes. 2) I could not find an entry for this instance in Prelude instead I found instance Ord () where compare () () = EQ Is this suppose to mean "for all tuples"? How do I define functions that work on all tuples? Thanks for taking time

1 0

Job advert: Compiler designer/architect
by Benedict R. Gaster 31 Aug '01

31 Aug '01

The following job advert has been sent to both the GCC and Pro64 mailing lists and I thought maybe of interest to people on this mailing list. SuperH are not looking for Haskell developers but rather are keen to recruit people with experience in language design and implementation. (The Pro64 is a highly optimizing compiler initially designed by SGI and targeted for the MIPS and IA64 architectures. Recently the Pro64 was made open source and SuperH is in the process of porting this technology to a selection of their current and future microprocessors.) Advert: SuperH, Inc is a new company formed by STMicroelectronics and Hitachi in order to market and develop the SuperH series of microprocessors as an independent company. The SuperH series will be offered as licensable cores for synthesis into embedded applications. See www.superh.com for more information. SuperH is headquartered in San Jose CA with R&D centers in Bristol UK and Tokyo Japan. SuperH will be developing software systems based on Open Source tecnology, including Gnu tools (i.e., gcc, gdb, etc.) and Pro64, and is looking for a range of engineers who have interests and/or experience in the following skill areas: o Code generation and optimization. Software pipelining, register allocation. Specific experience with gcc or Pro64 would be an advantage. o JIT compilation and dynamic optimization. o Linux development. o Architecture design. o Benchmarking. o Debugging technologies including gdb. SuperH will be developing products based on Gnu and Linux technogy as well as carrying out research into new innovative architectures and advanced compiler design, including the Pro64 and dynamic optimization. The main location for these posts is Bristol, UK. SuperH will be offering a comprehensive benefits package as well as an emloyee stock option scheme and bonus schemes. Job Title: Compiler designer/architect. Qualifications. Good knowledge of compiler optimizations, experience with Gnu or Pro64 would be useful. In depth knowledge of C & C++. Java an advantage. Experience in embedded system design. Please send CVs to: benedict.gaster(a)st.com Benedict R. Gaster SuperH, Inc.

1 0