- Haskell-Cafe - Haskell.org

Matroids in Haskell
by Gerhard Navratil 14 Jan '05

14 Jan '05

Recently I had a course on matroids and would like to investigate the topic a little further. Did anybody write (or start writing) a Haskell-implementation for matroids? It would save me some time figuring out if this part of mathematics is useful for my work ... Thanks in advance, Gerhard ======================================== Gerhard Navratil Teaching- And Research-Assistant Technical University Vienna, Austria Institute of Geoinformation and Cartography Gusshausstr. 27-29, 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12712 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at

3 2

Linear Shuffle
by Okasaki, C. DR EECS 14 Jan '05

14 Jan '05

Clearly, you can do a perfect shuffle in O(N) time using mutable arrays, using the standard imperative algorithm. You can also do it in O(N) expected time using *immutable* arrays, using Haskell's bulk array operations. 1. Start with a list of length N. If N < 2, stop. 2. Pair each element with a random index in the range [1,2N] (or [0,2N-1]). 3. Use "accum" to create an array of size 2N, where slot I contains a list of all the elements paired with I. 4. Map the shuffle function recursively across the array to re-shuffle any slots that got more than one element. 5. Append all the slots together into the result list. If you leave out step 4, you get an algorithm that runs in O(N) worst-case time, rather than expected time, but you no longer have a perfect shuffle (although it might be good enough). Upping the size of the array from 2N to 3N or 4N will help reduce collisions, but will not entirely eliminate them. With step 4, you can imagine pathological cases where everything gets put in the same slot, but with a reasonable random number generator, it is vanishingly unlikely that you will have enough collisions to drive the cost higher than linear. Again, upping the size of the array from 2N to 3N or 4N makes this even more unlikely. -- Chris

1 0

Introducing me
by Derek Elkins 14 Jan '05

14 Jan '05

> Hi, > > my name is Fabian Otto. Heya. Some other fixtures of the Haskell Community are covered on this page, http://haskell.org/hawiki/HaskellCommunities. Two noteworthy ones are the wiki (http://haskell.org/hawiki/) obviously, and the #haskell IRC channel on irc.freenode.net (http://haskell.org/hawiki/HaskellIrcChannel) which has about a hundred or so people on it at a time. Many of the quotes on* http://haskell.org/hawiki/QuotesPage are from the IRC channel, so that may give you an idea of what it's like, at least at the more humorous moments. * For others who haven't looked at it, it is quite entertaining.

1 0

Introducing me
by fabian otto 14 Jan '05

14 Jan '05

Hi, my name is Fabian Otto. I'm doing my master in computer science at the technical university of Berlin (Germany). I have choosen advanced functional programming (FTFP) [1] as one of my subjects. In this course we use opal[2] with some unimplemented features. e.g: * optional laziness * parametic types * theories / typeclasses Some topics in this course are: * monads * fixpoint algorithmes / cpos * parser generatoren * optimized datastructures ( e.g. queues) * reference counting To deepen my understanding in these topics I have choosen Haskell and I am really looking forward participating in this mailinglist Thanks for reading. Otto [1]: http://uebb.cs.tu-berlin.de/lehre/2004SVftfp/ [2]: http://www.cs.nott.ac.uk/~gmh//faq.html#opal -- bookmarks: http://del.icio.us/sigsegv jabber: sigsegv(a)jabber.ccc.de wiki/blog: http://jotpee.de/blog

2 1

RE: [Haskell-cafe] Re: Hugs vs GHC (again) was: Re: Some randomnewbiequestions
by Simon Marlow 14 Jan '05

14 Jan '05

On 08 January 2005 08:09, Aaron Denney wrote: > On 2005-01-07, Simon Marlow <simonmar(a)microsoft.com> wrote: >> - Can you use (some encoding of) Unicode for your Haskell source >> files? I don't think this is true in any Haskell compiler right >> now. > > I assume this won't be be done until the next one is done... Not necessarily; GHC doesn't use the standard IO library for reading source files. >> - Can you do String I/O in some encoding of Unicode? No Haskell >> compiler has support for this yet, and there are design decisions >> to be made. Some progress has been made on an experimental >> prototype (see recent discussion on this list). > > Many of the easy ways to do this that I've heard proposed make the > current hacks for binary IO fail. Making hacks fail isn't necessarily a bad thing :-) > IMHO, we really, really, need a > standard, supported way to do binary IO. I agree, but I think it should be part of a larger redesign of the IO library. The streams proposal includes binary I/O, by the way. I'm not keen to provide binary IO on top of the existing IO library, and then to have Unicode as a layer on top of that. Performance will be terrible. It needs to be designed properly from the ground up. > If I can read in and output > octets, then I can implement unicode handling on top of that. In fact > it would let a bunch of the proposed ideas for unicode support can > be implemented in pure haskell and have API details hashed out and > polished. > > For unix, there are couple different tacks one could take. The locale > system is standard, and does work, but is ugly and a pain to work > with. In particular, it's another (set of) global variables. And > what do you do with a character not expressible in the current locale? > > I'd like to possibility of different character sets for different > files, for example. Not a problem. Have you looked at the streams proposal? Cheers, Simon

10 14

Re: [Haskell-cafe] Question about instance
by John Velman 14 Jan '05

14 Jan '05

Thanks, Andreas. Your example still left me without context in the show statement itself, but your message set me to look in the right place. Now I have --- Code >data Relation a i b = Rel {name::RN, arity::Int, members::(Set [EN])} > >instance (Show a, Show i, Show b) => Show (Relation a i b) > where > show (Rel a i b) = > a ++ "/" ++ (show i) ++ " " > ++ (show b) > --- with result: ---GHCI Prelude> :l test.hs Compiling Main ( test.hs, interpreted ) Ok, modules loaded: Main. *Main> mkRelation1 "test" 2 [["one","two"], ["three","four"]] test/2 mkSet [["one","two"],["three","four"]] *Main> ---End GHCI It's hard to find examples like this, and the fact that it is fairly standard practice for the type name and constructor names to be the same in, for example, Gentle Haskell, and Haskell School of Expression make it more difficult for the novice to see when each is used! Best, John Velman On Fri, Jan 14, 2005 at 01:49:57AM +0100, Andreas Marth wrote: > If you replace > >data Relation = Relation {name::RN, arity::Int, members::(Set [EN])} > with > >data Relation = Rel {name::RN, arity::Int, members::(Set [EN])} > you will easy find out what is wrong and come to: > > >import Data.Set > > > >type EN = String -- element name > > > >type RN = String -- relation name > > > >instance Show a => Show (Set a) where > > show s = "mkSet " ++ show (setToList s) > > > >data Relation = Rel {name::RN, arity::Int, members::(Set [EN])} > > > >instance Show (Relation) > > where > > show (Rel a i b) = a ++ "/" ++ (show i) ++ " " ++ (show b) > > > Of course you can now change Rel back to Relation. But because of the > problems you just experienced I don't like it to name a type and its > constructor the same. > > > Happy coding, > Andreas > > > > ----- Original Message ----- > From: "John Velman" <velman(a)cox.net> > To: <haskell-cafe(a)haskell.org> > Sent: Friday, January 14, 2005 1:29 AM > Subject: [Haskell-cafe] Question about instance > > > > Instance with a context doesn't seem to work as I expect. > > > > Here's the story: > > > > I define an data type, Relation, and I want to make it an instance of > > "Show", partly so I can debug and tinker with things interactively and > have > > ghci print something. > > > > Here is my first try: > > ---- > > > > > >import Data.Set > > > > > >type EN = String -- element name > > > > > >type RN = String -- relation name > > > > > >instance Show a => Show (Set a) where > > > show s = "mkSet " ++ show (setToList s) > > > > > >data Relation = Relation {name::RN, arity::Int, members::(Set [EN])} > > > > > >instance (Show a, Show i, Show b) => Show (Relation a i b) > > > where > > > show (Relation a i b) = > > > a ++ "/" ++ (show i) ++ " " > > > ++ (show b) > > ---- > > > > When I try to load this into ghci, I get: > > > > ---GHCI: > > > > *Main> :l test.hs > > Compiling Main ( test.hs, interpreted ) > > > > test.hs:14: > > Kind error: `Relation' is applied to too many type arguments > > When checking kinds in `Relation a i b' > > When checking kinds in `Show (Relation a i b)' > > In the instance declaration for `Show (Relation a i b)' > > Failed, modules loaded: none. > > Prelude> > > ---END GHCI > > But, when I define showRelation separately, then leave the context out of > > the instance declaration with show = showRelation it works: > > > > -----------(Everything down to the instance declaration is the same) > > >instance Show Relation > > > where > > > show = showRelation > > > > > >showRelation:: Relation -> String > > >showRelation (Relation a i b) = > > > a ++ "/" ++ (show i) ++ " " > > > ++ (show b) > > > > > ----------- > > > > Now I get: > > ----------- GHCI output: > > Prelude> :l test.hs > > Compiling Main ( test.hs, interpreted ) > > Ok, modules loaded: Main. > > *Main> mkRelation1 "test" 2 [["one","two"], ["three","four"]] > > test/2 mkSet [["one","two"],["three","four"]] > > *Main> > > ---------- End GHCI > > > > Why does the original instance declaration result in failure and the > > message "Kind error: `Relation' is applied to too many type arguments" (I > > confess to not understanding 'kinds' too well.) > > > > I've done a bit of tinkering with the original version, and have tried the > > second version with a context in the instance declaration, but none of my > > attmepts work. The only one that worked was the one shown, with no > context > > in the instance declaration. Needless to say (?), I've tried to > > understand this from reading in the Haskell 98 report, `Haskell school of > > Expression', and any place else I can think of, but I'm missing the point > > somewhere. > > > > > > Thanks, > > > > John Velman > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > >

2 1

Problem with wxHaskell
by Dmitri Pissarenko 14 Jan '05

14 Jan '05

Hello! I've downloaded wxHaskell, ran the wxhaskell-register.bat file and now try to build a minimal wxHaskell program. For this purpose, I tried to start GHCi using following command ghci -package wx GuiTest.hs GHCi crashed with following error messages: <error-messages> GHC Interactive, version 6.2.2, for Haskell 98. http://www.haskell.org/ghc/ Type :? for help. Loading package base ... linking ... done. Loading package haskell98 ... linking ... done. Loading package lang ... linking ... done. Loading package concurrent ... linking ... done. Loading package QuickCheck ... linking ... done. Loading package readline ... linking ... C:/ghc/ghc-6.2.2/HSreadline.o: unknown symbol `_rl_redisplay_function' ghc.exe: unable to load package `readline' </error-messages> What am I doing wrong? TIA Dmitri Pissarenko PS: Here is the code of the application module Main where import Graphics.UI.WXCore main :: IO () main = run gui gui :: IO () gui = do frame <- frameCreateTopFrame "Hello World" windowShow frame windowRaise frame return () -- Dmitri Pissarenko Software Engineer http://dapissarenko.com

5 6

Question about instance
by John Velman 14 Jan '05

14 Jan '05

Instance with a context doesn't seem to work as I expect. Here's the story: I define an data type, Relation, and I want to make it an instance of "Show", partly so I can debug and tinker with things interactively and have ghci print something. Here is my first try: ---- > >import Data.Set > >type EN = String -- element name > >type RN = String -- relation name > >instance Show a => Show (Set a) where > show s = "mkSet " ++ show (setToList s) > >data Relation = Relation {name::RN, arity::Int, members::(Set [EN])} > >instance (Show a, Show i, Show b) => Show (Relation a i b) > where > show (Relation a i b) = > a ++ "/" ++ (show i) ++ " " > ++ (show b) ---- When I try to load this into ghci, I get: ---GHCI: *Main> :l test.hs Compiling Main ( test.hs, interpreted ) test.hs:14: Kind error: `Relation' is applied to too many type arguments When checking kinds in `Relation a i b' When checking kinds in `Show (Relation a i b)' In the instance declaration for `Show (Relation a i b)' Failed, modules loaded: none. Prelude> ---END GHCI But, when I define showRelation separately, then leave the context out of the instance declaration with show = showRelation it works: -----------(Everything down to the instance declaration is the same) >instance Show Relation > where > show = showRelation > >showRelation:: Relation -> String >showRelation (Relation a i b) = > a ++ "/" ++ (show i) ++ " " > ++ (show b) > ----------- Now I get: ----------- GHCI output: Prelude> :l test.hs Compiling Main ( test.hs, interpreted ) Ok, modules loaded: Main. *Main> mkRelation1 "test" 2 [["one","two"], ["three","four"]] test/2 mkSet [["one","two"],["three","four"]] *Main> ---------- End GHCI Why does the original instance declaration result in failure and the message "Kind error: `Relation' is applied to too many type arguments" (I confess to not understanding 'kinds' too well.) I've done a bit of tinkering with the original version, and have tried the second version with a context in the instance declaration, but none of my attmepts work. The only one that worked was the one shown, with no context in the instance declaration. Needless to say (?), I've tried to understand this from reading in the Haskell 98 report, `Haskell school of Expression', and any place else I can think of, but I'm missing the point somewhere. Thanks, John Velman

1 0

Re: [Haskell-cafe] Parsec and type (IO t) error
by Greg Buchholz 13 Jan '05

13 Jan '05

Mike Gunter wrote: > > I'd guess that > let (cam, sh) = parse_text shape_parse input > is what you want? (Completely untested ...) > Yep. That did it. Thanks, Greg Buchholz

1 0

Parsec and type (IO t) error
by Greg Buchholz 13 Jan '05

13 Jan '05

This is probably an easy question, but I'm having a problem with parsec in the IO monad. The essential parts of my program looks like this... >import Text.ParserCombinators.Parsec > >main = do input <- getContents > putStr $ show $ parse_text shape_parse input > --(cam, sh) <- parse_text shape_parse input > --putStr $ (show cam) ++ "\n" ++ (show sh) > putStr "\n" > >parse_text p input = case (parse p input) of > Left err -> error $ "Invalid input"++(show err) > Right x -> x > >shape_parse = do cam <- camera_parse > shapes <- many1 (sphere_parse <|> plane_parse) > return (cam, shapes) > >-- blah, blah, blah, etc. This works fine in GHC. The types for parse_text and shape_parse are... *Main> :t parse_text parse_text :: forall a tok. GenParser tok () a -> [tok] -> a *Main> :t shape_parse shape_parse :: forall st. GenParser Char st (Camera, [Shape]) *Main> Now when I change main to... >main = do input <- getContents > --putStr $ show $ parse_text shape_parse input > (cam, sh) <- parse_text shape_parse input > putStr $ (show cam) ++ "\n" ++ (show sh) > putStr "\n" I get the following message from GHCi... p2.hs:38: Couldn't match `IO t' against `(Camera, [Shape])' Expected type: GenParser Char () (IO t) Inferred type: GenParser Char () (Camera, [Shape]) In the first argument of `parse_text', namely `shape_parse' In a 'do' expression: (cam, sh) <- parse_text shape_parse input I'm probably missing something silly. Any hint would be appreciated. Thanks, Greg Buchholz

1 0