- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] #if and #endif
by ihope 06 May '06

06 May '06

On 4/13/06, Jason Dagit <dagit(a)codersbase.com> wrote: > Try using passing -cpp to ghc when you compile. > > Jason Thanks. Will do.

2 1

NewBinary/ BinMem and IO monad
by Marc Weber 06 May '06

06 May '06

I'm trying to write some true type library (implementing only the tables I need at the moment). When loading a font file it doesn't make sense to "parse" every table which isn't needed. So lazyness of haskell would perfectly meet requirements here. My problem: NewBinary supports memory buffers. After loading a file to mem it can't change anymore so I no longer need an IO monad. It looks like this: bh <- readBinMem "file" b::Word8 <- get bh Of cause I can't remove the monad here because bh contains an internal pointer to the current position... but it might be done returning the new pointer: (bh2,b::Word8) = get bh ? Then I would be able to lazily parse the tables eg: getTable1 bh = do bh = seek bh offset -- seek to the beginning of the table get binary data and build internal representation return list of glyph and outlines and ... of cause this mem should be readonly then.. Would it make sense to implement this? Does it already exist? Marc

2 4

Dynamically stackable monads
by Christophe Poucet 05 May '06

05 May '06

Hello, I was wondering if it's possible to stack a runtime-known amount of monads on top of each other. Let me illustrate. Assume I have a monad that can consume data and expects as starting parameter an action of the underlying monad to use this data (call it produce at the lower level monad). Now one could imagine stacking one of these consumers on top of the other, as can be seen below. However I can not choose at runtime how many I want to stack. Is there any solution for this? Regards, Christophe ------------------------------ -------------------------------------------------- {-# OPTIONS_GHC -fglasgow-exts #-} module Main where import Control.Monad import Control.Monad.Identity import Control.Monad.State import Control.Monad.Trans data Action e m = Action { produce :: e -> m () } newtype SequencerT e m a = SequencerT (StateT (Action e m) m a) deriving (Functor, Monad, MonadIO) newtype Sequencer e a = Sequencer (SequencerT e Identity a) deriving (Functor, Monad, MonadSequencer e) instance MonadTrans (SequencerT e) where lift = SequencerT . lift class Monad m => MonadSequencer e m | m -> e where consume :: e -> m () instance Monad m => MonadSequencer e (SequencerT e m) where consume x = SequencerT $ do s <- get lift . (produce s) $ x evalSequencerT (SequencerT s) action = evalStateT s action evalSequencer (Sequencer s) inputs action = evalSequencerT s action runSequencerT (SequencerT s) action = runStateT s action runSequencer (Sequencer s) action = runSequencerT s action main :: IO () = evalSequencerT (evalSequencerT (consume 1 >> consume 2 >> consume 3) (Action{produce = \x -> if x > 1 then consume x else liftIO . print $ ("A" ++ show x)})) (Action{produce = print . ("B" ++) . show }) -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: --- <Christophe.Poucet(a)imec.be> IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *****DISCLAIMER***** This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. **********

1 0

Re: Optimizing locking with MVars
by Simon Marlow 05 May '06

05 May '06

This is interesting, thanks. I propose to add INLINE pragmas to withMVar and friends. Having an interface for simple locks sounds like a good idea to me. Would you like to send a patch? This won't affect Handle I/O unfortunately, because we need block to protect against asynchronous exceptions. I'm still not certain you won't need that in the stream library, too: check any stateful code (eg. buffering) and imagine what happens if an exception is raised at an arbitrary point. Cheers, Simon Bulat Ziganshin wrote: > Main reason of slowness of existing Handle-based I/O in GHC is locking > around each operation. it is especially bad for simple char-at-a-time > I/O where 99% of time spent on locking and unlocking. > > To be exact, on my CPU, hPutChar for 100mb file requires 150 seconds, > while hGetChar for the same file is "only" 100 seconds long. it seems > that former use 3 locking operations and later 2 ones, because my own > vGetChar/vPutChar implementations both requires 52 seconds, of those > only about one second is real work and rest is just `withMVar` > expenses. > > Until now, i thought that this 0.5 ms (about 1000 primitive CPU > operations) on each withMVar is pure time required to perform > takeMVar+putMVar operations. But yesterday i investigated this problem > deeper and results was amazing! > > First, i just made local copy of `withMVar` and added INLINE to it: > > import Control.Exception as Exception > {-# INLINE inlinedWithMVar #-} > inlinedWithMVar :: MVar a -> (a -> IO b) -> IO b > inlinedWithMVar m io = > block $ do > a <- takeMVar m > b <- Exception.catch (unblock (io a)) > (\e -> do putMVar m a; throw e) > putMVar m a > return b > > > Second, i've developed my own simplified version of this procedure. > Here i should say that my library uses "MVar ()" field to hold lock > and separate immutable data field with actual data locked: > > data WithLocking h = WithLocking h !(MVar ()) > > This allowed me to omit block/unblock operation and develop the > following faster analog of withMVar: > > lock (WithLocking h mvar) action = do > Exception.catch (do takeMVar mvar > result <- action h > putMVar mvar () > return res > ) > (\e -> do tryPutMVar mvar (); throw e) > > And as third variant i tried exception-unsafe variant of `withMVar`: > > unsafeWithMVar :: MVar a -> (a -> IO b) -> IO b > unsafeWithMVar m io = do > a <- takeMVar m > b <- io a > putMVar m a > return b > > > And now are results: > > withMVar 52 seconds > inlinedWithMVar 38 seconds > lock 20 seconds > unsafeWithMVar 10 seconds > > > So, > > 1) `withMVar` can be made significantly faster just by attaching > INLINE pragma to it. until GHC includes this patch, you can just make > local copy of this procedure (it's implementation is > compiler-independent) and use INLINE pragma for this local copy > > 2) if MVar is used only to protect some immutable data from > simultaneous access, it's use can be made significantly faster by > using above-mentioned WithLocking type constructor together with > 'lock' function. I hope that this mechanism will go into future > Haskell implementations and in particular it will be used in my own > Streams library and in new DiffArray implementation (that is a part > of ArrayRef library) > > 3) For simple programs that don't catch exceptions anyway, this > excessive protection is just meaningless. they can use > 'unsafeWithMVar' to work as fast as possible. i mean in particular > shootout-like benchmarks. it is also possible to develop fast & safe > routines by using explicit unlocking (with 'tryPutMVar') in > higher-level exception handlers > > > and a more general conclusion. this case is a good demonstration of > significant performance loss due to using of higher-order functions. i > think that more aggressive inlining of high-order and polymorphic > functions should significantly speed up GHC-compiled programs. > >

3 6

Are records type safe?
by Tom Hawkins 04 May '06

04 May '06

I was experimenting with records this morning and discovered a slight oddity... data Rec = RecA { a :: Int } | RecB { a :: Int, b :: Bool } deriving Show main :: IO () main = do print (b (RecB { a = 1, b = True })) -- Works print (b (RecA { a = 1 })) -- Doesn't Of course extracting "b" from a record constructed with "RecA" is illegal, but the compiler did not warn against it (ghc -W). I was expecting a warning similar to non-exhaustive pattern matching. Are records with optional fields really type safe? -Tom

2 1

Is it possible to export module aliases?
by Brian Hulley 04 May '06

04 May '06

Hi - Given some large list of modules which need to be used qualified, I'd like to be able to make a convenience module that I could use instead, and which would export all these modules also qualified by an alias, ie: module Top ( module qualified Top.First as First , module qualified Top.Second as Second ) where ... import qualified Top.First so that I could then say: import Top main = do a <- First.create ... b <- Second.create ... instead of having to always write: import qualified Top.First as First import qualified Top.Second as Second -- this may be a *very* long list in every module that uses the "Top" API. The current "workaround" for this problem in the standard libraries seems to be to always append the module name to the name of the function or type or constructor (which is unfortunately, like record field names, not local to the type but that's another story) eg by using createFirst, createSecond etc, which seems a bit messy to me. An alternative is to use the C preprocessor and #include a file containing all the import declarations, but although "ok", I'd prefer to be able to express the code organization purely in Haskell itself. This must be a very common issue so I'm wondering if anyone else has some better ideas on how to solve it? Thanks, Brian.

2 2

Am I lazy enough?
by Joel Reymont 03 May '06

03 May '06

Folks, I'm looking to use the following code to process a multi-GB text file. I am using ByteStrings but there was a discussion today on IRC about tail recursion, laziness and accumulators that made me wonder. Is fixLines below lazy enough? Can it be made lazier? Thanks, Joel --- module Main where import IO import System import Numeric import Data.Char import Data.Word import qualified Data.Map as M import qualified Data.ByteString.Char8 as B import Prelude hiding (lines) grabTableInfo x = (tableId', (tableType, tableStakes)) where (tableId:tableType:_:tableStakes:_) = B.split ',' x Just (tableId', _) = B.readInt tableId lines = B.split '\n' --- My Oracle ascii dump is 80 characters wide so some lines --- are split. I need to skip empty lines and join lines --- containing less than the required number of commas. fixLines 0 lines = lines fixLines _ [] = [] fixLines n (line:lines) = fixLines' lines line [] where fixLines' [] str acc | B.count ',' str == n = acc ++ [str] | otherwise = acc fixLines' (x:xs) str acc | B.null str -- skip = fixLines' xs x acc | B.count ',' str < n -- join with next line = fixLines' xs (B.append str x) acc | otherwise = fixLines' xs x (acc ++ [str]) mkMap = M.fromList . map grabTableInfo . fixLines 20 loadTableInfo = do bracket (openFile "game_info_tbl.csv" ReadMode) (hClose) (\h -> do c <- B.hGetContents h return $ mkMap $ lines c) -- http://wagerlabs.com/

2 1

Code review: efficiency question
by Brian Hulley 03 May '06

03 May '06

Hi - I started off writing the following piece of monadic code: let drawModal :: Control -> ManagerM () drawModal c = do -- details omitted -- Prolog style coding... drawModals :: [Control] -> ManagerM () drawModals [] = return () drawModals (c:cs) = do drawModals cs drawModal c drawModals cs then it struck me that I should have not bothered with drawModals and instead should just have used: mapM_ drawModal (reverse cs) However, while this looks more elegant, it is less efficient? In other words, how much optimization can one assume when writing Haskell code? I'm trying to get a rough idea so I can decide whether to write helper functions such as drawModals in future or whether I should always just use the most elegant code instead. Any ideas? Thanks, Brian.

5 7

GetOpt
by Anton Kulchitsky 02 May '06

02 May '06

Hi all, I just started to study Haskell and it is my almost first big experience with functional languages (except Emacs Lisp and Python). I enjoyed all small exercises and started a bigger business writing a general utility. However, I have a problem from the beginning. The utility get some file and convert it to another format. It is a kind of small compiler. It also accepts many parameters and behaves depending on them. The problem is how to do this neat! How should I write my program to accept and neatly work with options???? Please, could you suggest an example of code how to do this properly in Haskell. No book or tutorial discuss this topic. It is really sad because the problem is very unclear. Indeed, what I do in C. I make a struct settings and set its fields. Then, the program uses this parameters easily. However, what can I do in Haskell? I imagine the program as a composite function that take some input and produce the output. I decided that now I should consider my program options as an additional variable(s) of the input. Well, it is still hard to implement. Below is an example of what I did first. However, it is just not enough and looks ugly for me. Please, HELP!!!: -------------------------CODE IS BELOW------------------------- module Main where -- std import System.IO import System.Console.GetOpt import System.Environment ( getArgs ) import System.Exit import Char -- data import Data.Maybe ( fromMaybe ) -- local -- main program: options, maybe in file >> out file main :: IO () main = do -- program info genInfo -- options processing args <- getArgs case check_filter args of (WrongOpts,strLst) -> usage ("Error: Wrong option list\n" ++ (concat strLst)) >> exitWith (ExitFailure 1) (ForHelp,strLst) -> usage [] >> exitWith ExitSuccess (ForVersion,strLst) -> version >> exitWith ExitSuccess --strLst contains 3 strings: input file name, output, and parameters (OK,strLst) -> do inputstr <- readFile infile --get the content writeFile outfile (pgnjs inputstr params) --write the result exitWith ExitSuccess --exit where infile = (strLst !! 0) outfile = (strLst !! 1) params = (strLst !! 2) --(_,_) -> version >> exitWith (ExitFailure (-1)) ---------------- OPTIONS DESCRIPTION ---------------- -- OptionFlag is data OptionFlag = Version | Help | Output String | Input String deriving (Show, Eq) -- description of all options options :: [OptDescr OptionFlag] options = [ Option ['h', '?'] ["help"] (NoArg Help) ("show this help"), Option ['V'] ["version"] (NoArg Version) ("show version number"), Option ['i'] ["input"] (ReqArg Input "file") ("input file name"), Option ['o'] ["output"] (ReqArg Output "file") ("output file name") ] ------------------------------------------------------ -- this data describes the result of program work data ErrKey = OK | ForHelp | ForVersion | WrongOpts deriving (Show, Eq) ----------------------------------------------------------------------- -- input is a string of options and output is the result of the -- program. Actually, this is only a filter which filter all -- exceptional situation in option lists and then call a real function -- if list is good check_filter :: [String] -> ( ErrKey, [String] ) check_filter args = case (getOpt Permute options args) of (os, [], []) -> if (elem Help os) then (ForHelp,[]) else if (elem Version os) then (ForVersion, []) else if (not ((elem "-i" args) && (elem "-o" args)) ) then (WrongOpts, ["both -i and -o must be specified\n"]) -- we filtered now all exceptional situation else (OK, ["in.tmp","out.tmp",[]]) (os, fs, ers) -> (WrongOpts, []) -------------- OPTIONS EXCEPTIONAL FUNCTIONS ----------------- -- Version info version :: IO () version = putStrLn $ "Version 0.1.1a of October-November 2005" -- Usage short info: Output error line and usage usage :: String -> IO () usage errLine = putStr $ errLine ++ (usageInfo "Usage: shipgnjs [option...]" options) -- General info string genInfo :: IO () genInfo = putStrLn "shipgnjs (c) 2005 Anton Kulchitsky" {- This is the main function that operates on correct string: input: the first element is input pgn, the second line are parameters the output is html text for the result file -} pgnjs :: String -> String -> String pgnjs pgnstr params = map toUpper pgnstr ---- Thank you in advance, Anton Kulchitsky (a.k.a. atoku)

8 18

Summer of Code - Student Application Form
by Paolo Martini 02 May '06

02 May '06

Hi, it was just published the student application form, you can find it at: <http://code.google.com/soc/student_step1.html> I hope we will be collecting good Haskell applications from students :-) I am very happy to see how many did signed up on the People page as now: <http://hackage.haskell.org/trac/summer-of-code/> Keep on writing! Paolo. --

1 0

database access recommendation
by Brock Peabody 02 May '06

02 May '06

I'm teaching myself Haskell, and was wondering if anyone could recommend a library for accessing databases, PostgreSQL in particular. I looked at http://www.haskell.org/haskellwiki/Libraries_and_tools, and HSQL looked promising, but I can't get it to install on Windows or FreeBSD, with Hugs or GHC. According to the FreeBSD ports system, it is marked as broken. It fails with Hugs on both platforms on the "runhugs Setup.lhs configure" step in the base HSQL library with: FreeBSD: ERROR "/usr/local/lib/hugs/libraries/Text/ParserCombinators/ReadP.hs":133 - Syntax error in type expression (unexpected `.') Windows: ERROR "C:\Program Files\WinHugs\libraries\Text\ParserCombinators\ReadP.hs":156 - Syntax error in type expression (unexpected `.') GHC crashes with no error on the "runghc Setup.lhs build" step in the base HSQL library in Windows. In FreeBSD I can completely build and install the base library, but in any of the database specific directories, "runghc Setup.lhs configure" yields: "Setup.lhs:17:71: Couldn't match `PackageDescription' against `LocalBuildInfo' Expected type: Args -> ConfigFlags -> LocalBuildInfo -> IO ExitCode Inferred type: [String] -> ConfigFlags -> PackageDescription -> LocalBuildInfo -> IO ExitCode In the `postConf' field of a record In the record update: defaultUserHooks {preConf = preConf, postConf = postConf} <interactive>:1:87: Failed to load interface for `Main': Bad interface file: Setup.hi Setup.hi: openBinaryFile: does not exist (No such file or directory)" Thanks, Brock

6 11

Newbie: Haskell Sine Oddities
by Aditya Siram 01 May '06

01 May '06

The Sine function in the prelude is not behaving as I expected. In the following Hugs session I tested sin on 0, 90,180 & 360 degrees. Prelude> sin 0 0.0 --correct Prelude> sin (pi/2) 1.0 --correct Prelude> sin pi 1.22460635382238e-16 --WRONG! Prelude> sin (2*pi) -2.44921270764475e-16 --WRONG! Is this normal behaviour? Or am I using the trig functions in an unexpected way? Thanks... Deech

6 5

Funct dependency conflict when using types
by Frank 30 Apr '06

30 Apr '06

I have observed the error message (ghci 6.4) Functional dependencies conflict between instance declarations: LocTest.hs:16:0: instance B S Bool LocTest.hs:22:0: instance (F f, B a b) => B (f a) (f b) when I changed in an instance from a simple type to a type with a parameter (i.e. from Int to (Int, Bool)). The following minimal program demonstrates the problem: an instance with type S (= T Float) conflicts with B (f a) (f b) whereas the comparable instance with data R (= R Float) does not. Is this intentional? How can it be avoided? Help is greatly appreciated! Andrew ---------------------------------------- class F f where m2 :: (a -> b -> c) -> f a -> f b -> f c --zipWith class B a b | a -> b where dist2 :: a -> a -> b instance B S Bool where -- line 16 dist2 a d = True instance B R Float where dist2 a d = 1 instance (F f, B a b) => B (f a) (f b) where -- line 22 dist2 a b = m2 dist2 a b data T f = T f type S = T Float data R = R Float

2 1

Current situation regarding global IORefs
by Brian Hulley 29 Apr '06

29 Apr '06

Hi - I've run into the global mutable state problem described in http://www.haskell.org/hawiki/GlobalMutableState Since the page was last edited in March last year, I'm wondering if there have been any developments or further thoughts on how to safely create top level IORefs since they are absolutely essential for the library I'm writing. For my library, which implements a GUI, I have a Manager module which keeps track of which control currently has the keyboard focus etc, and I don't want to have to pass round the state of the manager to every control since this would be monstrously inconvenient and a total waste of space/time, so at the moment I'm reduced to: module Manager where keyboard :: IORef (Maybe Control) {-# NOINLINE keyboard #-} keyboard = unsafePerformIO $ newIORef Nothing The problem is that I don't know if this is guaranteed to be completely safe for all Haskell compilers or even for all future versions of ghc (?) Thanks, Brian.

7 25

Newbie "Instance Of Floating Int" Error
by Aditya Siram 29 Apr '06

29 Apr '06

Hi all, I just started working with Haskell and am having some difficulties with its type system. Here is function that is supposed to calculate the distance between two coordinates: distBetween (x1,y1) (x2,y2) = sqrt((x2-x1)^2 + (y2-y1)^2) I am trying to explictly give it a type signature. Here is what I have tried and the errors generated by Hugs: type Point = (Int,Int) distBetween :: Point -> Point -> Float >>ERROR - Type error in explicitly typed binding *** Term : distBetween *** Type : Point -> Point -> Int *** Does not match : Point -> Point -> Float distBetween :: Point -> Point -> Int >>Instance of Floating Int required for definition of distBetween Any help is appreciated... Deech

4 4

Saving a data structure to a file
by Neil Mitchell 28 Apr '06

28 Apr '06

Hi, I have a program which needs to cache intermediate data structures to a file (finite, non-cyclic, relatively simple, around ~100Kb when shown). Is there any easy way to acheive this? The current approach I am using is to add deriving Read, Show to all the data structures, and then writeFile "output.txt" (show x) read =<< readFile "output.txt" The problem is that this is too slow, and itsn't lazy. Is there any way to do better than this? I can imagine something like showBinary/readBinary which did this using binary files directly, but is there anything that does this? I'd like it to work with GHC and Hugs at least, and the less extra code I have to write the better :) Thanks Neil

2 1

Billion-triple RDF store
by Joel Reymont 26 Apr '06

26 Apr '06

Folks, How would you go about implementing a RDF triple store in Haskell capable of handling a billion triples? I'm looking for ideas. For example, you could use tries to store all strings but you could easily get to the point where you can't load them all into, say, 1Gb of memory which is all I have on my machine. I'm thinking that the required data could be pulled from disk lazily (as needed) and laziness is a Haskell forte. Thanks, Joel P.S. I know about Swish but would go for a far more compact and efficient representation. -- http://wagerlabs.com/

2 1

Re: Proposal for Number classes
by Serge D. Mechveliani 26 Apr '06

26 Apr '06

Dylan Thurston <dthurston(a)barnard.edu> wrote on 17 Apr 2006 > On Sat, Apr 08, 2006 at 10:16:53PM +0400, Serge D. Mechveliani wrote: >> I think that without dependent types for a Haskell-like language, >> it is impossible to propose any adequate and in the same time plainly >> looking algebraic class system. > Agreed. Is there anything really wrong with the Kiselyov-Shan > approach to dependent types? Does it look too bizarre? > > http://okmij.org/ftp/Haskell/types.html#Prepose > http://okmij.org/ftp/Haskell/number-parameterized-types.html I am out of this field since about 2001. The first paper mentions the foreign function interface, and transmitting integer by means of tricks with types (I recall difficulties with existential types), and so on. It also mentions passing vocabularies (maybe, via foreign interface extension). Of course, if a language extension allows to express the constructs like if isPrime n then (pass inv (the inversion operation) to the vocabulary of (ResidueDomain Integer n), with this implementation ... ) else do not pass it , then this is what is needed: an equivalent of a dynamic conditional instance. In this example, passing inv expresses actially dynamic and conditional definition of the Field instance. Field a <==> (CommutativeRing a, `inv' is in vocabulary of a). In Magma system, and in Aldor, it can be, probably, written plainly. But these systems are not functional, nor lazy, have not pattern matching, etc. Currently I am out of this field, have not time to study all this. For example, if Dylan Thurston tries to implement the Basic Algebra proposal basing on the approach of `configurations' of http://okmij.org/ftp/Haskell/types.html#Prepose, and with the functionality as of the BAL proposal, then we could observe whether the thing looks natural enough. I could also think of doing an attentive investigation on this subject, maybe, together with some qualified people, if I have this project as somehow a visiting research job, and paid. And there is no guarantee that the result occurs positive. ----------------- Serge Mechveliani mechvel(a)botik.ru

1 0

Haskell.org and Google Summer of Code 2006
by Paolo Martini 26 Apr '06

26 Apr '06

Hello, It is now official. Haskell.org is a mentoring organization for this year's Summer of Code programme. You can see it listed on the official site <http://code.google.com/soc/> clicking on `Haskell.org (ideas)' you'll be directed to the trac site we are setting up. (It's 4 AM and I've just finished adding the projects, and cleaning things up a bit.) I am _very_ happy about seeing this project working out for real. I fear that I wouldn't be able to reach everybody even mailing all the important mailing list; I hope many students will be able to take advantage of this great occasion. Help me spread the word, tell everybody about the project :-) You can find the new site here <http://hackage.haskell.org/trac/summer-of-code/>, the StartPage will be updated with details during the program. Projects ideas and volunteers for mentoring are still very much welcome! students' application period starts on May 1. Thanks very much for the support, hope to hear thoughts and proposals, Paolo. --

1 0

Project proposal
by michael＠schmong.org 26 Apr '06

26 Apr '06

Hi, All this chatter about the Summer of Code has inspired me to throw caution to the wind and become more committed to an idea I had for a Haskell project. I first thought to apply this to Python, but well, Haskell stole my heart. I wanted to throw the idea out there and see if anyone was interested in mentoring me through the process. I want to build a MUD engine written in Haskell with Haskell as the MUD development language. This is a great way to introduce kids to Haskell as their first programming language. And when they get bored and grow out of mudding, they will have knowledge of a real-world language instead of just a toy language particular to whatever MUD they were playing with. Getting a mentor, and completing the project is more important to me than officially becoming a Summer of Code project. But if they both happen then all the better. Any takers? Michael Litchard of Mission College Santa Clara , CA

1 0

Google Summer of Code 2006
by Paolo Martini 25 Apr '06

25 Apr '06

Hello, Haskell.org is going to partecipate as mentoring organization to the Google Summer of Code programme of this year. We have formed a group of volunteers taking care of the administrative work as well as the mentoring part. The group is listed here: <http://haskell.org/haskellwiki/Summer_of_Code:_People>. We are now looking for projects, and mentors. We've reached number 24 but we are happily going to add more, Haskell Open Source paid work for the summer! If you run some active open source program you might want to mentor some student who will be working on your code, for example. Either just add your ideas here: <http://haskell.org/haskellwiki/Summer_of_Code:_Project_suggestions> (as well as your informations on the People's page) or contact me for details. I am also looking for students, I'd like to ear from them if they are going to partecipate with Haskell projects, last year I was alone! (I did write the bindings to the Cairo vector graphics library and integrated them in Gtk2Hs.) Details about the programme itself can be found on the official webpage: http://code.google.com/summerofcode.html Hoping you like the idea as much as me, Paolo. --

2 1

Re: [Haskell-cafe] Google Summer of Code 2006
by Paolo Martini 25 Apr '06

25 Apr '06

Evan Martin ha scritto: > (This is Evan from Google.) > Just wanted to say that it's rad to see you making all this happen. Hi Evan! Fabulous to see you around! Thank you very much, we have done great work last year. Google is doing so well making students able to work on what they like most, during the summer, I couldn't resist about sharing this opportunity and making it available for the bigger number of people I could. Cheers, Paolo. --

1 0

Control.Exceptions and MonadIO
by oleg＠pobox.com 24 Apr '06

24 Apr '06

Robert Dockins wrote: > One additional (very unfortunate) point is that higher-order IO monad > combinators will not work on your monad, eg, the ones in > Control.Exception. Although that is true in general, for many useful and interesting cases (including ReaderT, the state transformer, and the newtype wrapping of IO) one _can_ use catch, bracket etc. constructs in MonadIO. Please see this message and the follow-up discussion: http://www.haskell.org/pipermail/haskell/2006-February/017547.html

3 6

How to get Haddock to generate docs for a directory tree of modules
by Brian Hulley 24 Apr '06

24 Apr '06

Hi - I've been looking at the docs for Haddock at http://haskell.org/haddock/haddock-html-0.7/index.html but I can't seem to find any option to recursively traverse a directory generating hyperlinked docs for all modules anywhere in the directory or any sub directory etc. Is there a simple undocumented flag I'm missing? Thanks, Brian.

2 2

Advice needed on best way to simulate an STL vector
by Brian Hulley 24 Apr '06

24 Apr '06

Hi - In C++, STL provides a vector class which behaves as an array except you can insert/delete elements from it. I'm wondering what is the best Haskell data structure to use to simulate this, either mutable or immutable. I've looked at the Array interface, but although there is the // operation to replace some elements, there does not appear to be a simple way to delete/insert elements. Ideally I'd like functions like: -- Insert new elements starting at the specified index, moving the others up to make room insert:: Array i e -> i -> [e] -> Array i e -- Delete a range of elements, moving later elements back down delete:: Array i e -> i -> i -> Array e -- Append a new element to the end of an array push_back :: Array i e -> e -> Array i e Is there an efficient way of implementing these operations in Haskell, based on arrays, or should I be using some other data structure altogether eg a list? Also, for large arrays, am I right in thinking that it is still more efficient to use immutable arrays rather than mutable arrays (because it is easier for gc to always just deal with immutable values)? Thanks, Brian.

9 16

Independent component analysis and RDF
by Joel Reymont 24 Apr '06

24 Apr '06

Howdy folks! Does anyone have sample code for independent component analysis (ICA), singular value decomposition (SVD) aka spectral graph partitioning, or semidiscrete decomposition (SDD)? I'm trying to learn this rocket science and apply it to RDF graph analysis. Thanks, Joel -- http://wagerlabs.com/

2 1

Re: Predicates in HaXml
by luby liao 23 Apr '06

23 Apr '06

For this purpose, try h1 [keep /> dfilter (parseXtract "/greetings/greeting[1]/-")] cheers, Luby Liao > I am just trying out a few things with the Xtract tool. I have a > simple XML document: > > <greetings> > <greeting>hello</greeting> > <greeting>world</greeting> > </greetings> > > I am using the Xtract query /greetings/greeting[1]/- hoping to get the > text "world" > e.g. > mkElem "h1" [applypred (keep) (parseXtract "/greetings/greeting[1]/-")] > > but this just returns the entire xml document. Have i got something > fundamentally wrong here? > > Thanks > Tom Spencer > >

1 0

Re: [Haskell] Haskell.org and Google Summer of Code 2006
by Creighton Hogg 22 Apr '06

22 Apr '06

Well, now that we've started this discussion I presume it's okay if I ask a few things. I don't know if these are good ideas, but I thought I'd throw them out. Basically, I am a student and would be eligible for the SoC. I'd like to work on something related to numerics support or performance in Haskell. Either building on existing gsl bindings, making something out of whole cloth, or spending some intensive work on compiler optimizations. My dream would be to build up enough monte carlo support in haskell that things like high energy physics event simulators could be coded in the language without sacrificing too much performance and having a hundred times the flexibility and *maintainability*. Creighton Hogg On 4/22/06, Paolo Martini <paolo(a)nemail.it> wrote: > Hello everybody, nice to meet you all. > > Last year I did work on an Haskell project during the first year of > the Google Summer of Code programme[1]. I wrote the bindings to the > Cairo Vector Graphics library and integrated them in Gtk2Hs. You can > see last year's announcement on the website[2]. > > I had to take Google itself as my mentoring organization, in absence > of a better-suited one, no wonder I was the only one with an Haskell > project, eventually I got one of its 13 slots available -- Chris > DiBona[3], the project leader, seem to like Haskell very much! > > They recently announced they would be running the programme again > this year, and I thought we could surely do better! My idea is that > the best way we are going to get more Haskell projects done is having > Haskell.org as a mentoring organization this year. > > Let me briefly summarize how the project works; it starts with a > number of mentoring organizations that support active open source > projects. They are required to publish a list of projects for > students to apply for, and some mentors which will take care of the > pupils during their work. Part of the fun is of course that the > students can propose their own projects too. Each successful > applicant gets an initial $500, three months of coding time, a mid- > term $2,000 of are doing well and a final $2,000 on successful > completion of the project (The site[4] does explain it all.) > > I contacted many of the people who usually reside in the #haskell IRC > channel asking for collaboration, and they promptly accepted, forming > a quite big number of well organized people -- as now, those three > people are in charge for the administrative work: > > - Isaac Jones <http://www.syntaxpolice.org/>, > - Donald Bruce Steward <http://www.cse.unsw.edu.au/~dons/>, > - David Himmelstrup <http://darcs.haskell.org/~lemmih/aboutMe.html>. > > Not surprisingly, since the people of the channel are known to be > very kind and helpful, answering questions at every time of the day, > I've got a good number of volunteers for mentoring too (which I'm > very happy about): > > - David Himmelstrup, > - John Goerzen <http://www.complete.org/>, > - Cale Gibbard <http://www.haskell.org/hawiki/CaleGibbard>, > - Einar Karttunen <http://www.cs.helsinki.fi/u/ekarttun/>, > - Shae Matijs Erisson <http://www.ScannedInAvian.com/>, > - Duncan Coutts <http://haskell.org/gtk2hs/development/>. > - Andres L\¨oh <http://www.iai.uni-bonn.de/~loeh>, > - Ian Lynagh <http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/>, > > And the list is getting bigger and bigger! > > Unsure about where to get an "authoritative answer" about things like > this I have mailed Simon Peyton-Jones, he likes the idea (Thanks very > much!) He explained to me that since the Haskell community is very > decentralized I would better send a message to the Haskell mailing > list to propose this project. > > I hope you will be as enthusisatic as I am. Hacking Haskell code > during the summer, funded enough to keep up with the other things > (and getting some pretty cool hardware lately), was a *great* > experience. > > I sincerely hope that many students will apply for Haskell works. We > need projects done! I'll be mailing you the url of the wikipage > collecting projects and details. > > Thank you very much, > Paolo. > -- > > [1] <http://code.google.com/summerofcode.html> > [2] <http://haskell.org/gtk2hs/?p=30> > [3] <http://dibona.com> > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

1 0

Google SoC
by Pepe Iborra 21 Apr '06

21 Apr '06

http://code.google.com/soc/ This is not news. SoC was presented a few days ago, and by now there are a lot of projects available, yet none(?) Haskell related :( This is a plea for Haskell FOSS project managers to apply as mentor organizations, so that we students can have a choice. Surely there are a lot of contributions that can be tackled by a motivated student in three months time. GHC related stuff, work in Visual Haskell, tasks in a given Haskell framework, Darcs stuff, you name it. Deadline for mentor organizations is May 1, but they might close it earlier if they get their hands full. pep

2 1

matrix computations based on the GSL
by Alberto Ruiz 21 Apr '06

21 Apr '06

Hello all! This is my first message to the list. In my work I often need linear algebra algorithms and other numeric computations. An option is using scientific computing systems like Matlab, Mathematica, Maple, etc. In Haskell there are several modules and bindings to matrix libraries; many of them are excellent. But I think that Haskell would be even more attractive if the basic matrix computations (what we find, for example, in the GNU Octave Quick Reference) were easily available in a standard library. We have all we need: an interactive environment, excellent graphics (HOpenGL), FFI and ForeignPtr with automatic garbage collection, QuickCheck, etc. Computations can be implemented by the GSL (GNU Scientific Library), a well designed numerical library written in C. Well... I know that I am trying to reinvent the wheel: I am working on a user friendly functional interface to matrix computations based on the GSL. I think that many numeric problems that can be solved using Octave or a similar system can be also solved more elegantly using Haskell. The library is very preliminary and incomplete but some simple problems can already be solved. The sources, haddock documentation and the draft of a tutorial can be found at: http://dis.um.es/~alberto/hmatrix/matrix.html I am not a Haskell expert, I only use the most basic programming techniques, so any suggestion will be greatly appreciated... Alberto

22 97

C++ parser in Haskell?
by Ravi Nanavati 20 Apr '06

20 Apr '06

It turns out we might find such a beast useful at Bluespec. If anyone has written a C++ parser in Haskell (or knows of one), we'd like to hear about it. Thanks, - Ravi Nanavati Bluespec, Inc.

4 4

Spawning a terminal window?
by ihope 20 Apr '06

20 Apr '06

Does Haskell have a handy way to spawn a new terminal window and give you a handle to access it with? --ihope

1 0

Re: [Haskell-cafe] 1G strings in Haskell
by dons＠cse.unsw.edu.au 20 Apr '06

20 Apr '06

dagit: > On 4/19/06, Donald Bruce Stewart <dons(a)cse.unsw.edu.au> wrote: > > Question: > > Can I manipulate 1G strings in Haskell? > > > > > > Failed due to memory exhaustion. > > Almost made it though, just need a tad more ram than I had. > > > > filter ! > > unlines ! > > unwords ! > > reverse ! -- copy > > cons ! -- copy > > snoc ! -- involves a copy > > ++ ! -- can't concat two 1G strings on this box > > I would say given the nature of the experiment that you want to feed > these functions with values that lead to 1 GB results. At least, that > makes sense in the case of ++, but maybe not the others. Yes, good point. Previous experiments with 500M strings indicated that these all worked fine: Size of test data: 531416k Fine: filter 7.264 unwords 1.715 reverse 1.980 cons 0.976 snoc 0.689 ++ 2.845 Still wouldn't work at 0.5G unlines ! concat ! > Did the machine have any available swap? If so, why was it not used? Swap was used, 1G more, but ulimits kicked in a few times (and I'm not an admin on the box). This was a bit frustrating, but the 0.5G results show what is possible. > The strings had to be in memory all at once to not skew the benchmark > by including I/O time? The strings were all in memory, yes, with some deepSeq tricks. -- Don

1 0

1G strings in Haskell
by dons＠cse.unsw.edu.au 20 Apr '06

20 Apr '06

Question: Can I manipulate 1G strings in Haskell? Short answer: Yes! Mostly. Doing some stress testing of FPS, here are some results for 1G strings. 3.2Ghz box, 2G physical mem. Size of input string: 1G N.B. 2G of physical ram is not enough when trying to benchmark functions that copy 1G strings around :) Function Time in seconds All O(1) functions: length O index 0 head 0 tail 0 last 0 init 0 O(n) , but answer found early on: compare 0 any 0 all 0 elem 0 elemIndex 0 O(n) mostly: maximum 3.855 minimum 4.666 filterChar 8.084 elemIndicies 11.504 lines 12.247 find 14.046 tails 27.328 inits 33.620 words 100.963 map toUpper 143.871 Failed due to memory exhaustion. Almost made it though, just need a tad more ram than I had. filter ! unlines ! unwords ! reverse ! -- copy cons ! -- copy snoc ! -- involves a copy ++ ! -- can't concat two 1G strings on this box sort ? taking too long, but space was ok. [Char] functions are much more costly. pack ! -- constructing 1G [Char] is not ok. unpack ! Lesssons, you can play with 1G strings in Haskell. Having more than 2G ram is useful though. Replacing higher order functions with hard coded first order equivalents can help. -- Don

1 0

Re: [Haskell-cafe] Advice needed on best way to simulate an STL vector
by Cale Gibbard 19 Apr '06

19 Apr '06

I should perhaps point out that in the development GHC (iirc), there is a library called Data.Sequence which uses 2-3 finger trees to get rather nice efficient sequences. Operations on both ends (appending or dropping) are constant time, while operations in the middle tend to be on the order of the logarithm of the distance to the closer of the two ends. For instance, concatenation and splitting at a point both have complexity proportional to the logarithm of the smaller of the two parts involved. - Cale On 19/04/06, Brian Hulley <brianh(a)metamilk.com> wrote: > Thanks. I might try this if I don't have any luck with finger trees (from > Udo's post), or if they seem too heavy for the simple thing I'm planning to > use them for (implementing the text buffer for an edit control which needs a > mutable array of lines where each line contains a mutable array of character > info). I don't need non-Int indices so your data type for Vector would be > fine. > > Best regards, Brian. > >

2 1

RE: [Haskell-cafe] Proposal for restructuring Number classes
by Andrew U. Frank 19 Apr '06

19 Apr '06

i am most grateful to henning and dylan for their effort in restructuring the number classes. there seems to be agreement, that the current classes are not optimal. the decision what goes in a class depends enormously on what axioms one is assuming for an operation symbol. should * always be commutative or is its use for non-commutative types acceptable? i will now make an effort to use the proposed classes by dylan and hennig and adapt my code to it and then come back and report how it suited my needs. thank you for the help! andrew frank

2 1

Re: Proposal for restructuring Number classes
by Serge D. Mechveliani 18 Apr '06

18 Apr '06

On Sat, Apr 08, 2006 at 02:39:39PM +0200, Andrew U. Frank wrote: > there has been discussions on and off indicating problems with the structure > of the number classes in the prelude. i have found a discussion paper by > mechveliani but i have not found a concrete proposal on the haskell' list of > tickets. > i hope i can advance the process by making a concrete proposal for > which i attach Haskell code and a pdf giving the rational. if i have not > found other contributions, i am sorry. > > i try a conservative structure, which is more conservative than the > structure we have used here for several years (or mechveliani's proposal). > It suggests classes for units (Zeros, Ones) and CommGroup (for +, -), > OrdGroup (for abs and difference), CommRing (for *, sqr), EuclideanRing (for > gdc, lcm, quot, rem, div...) and Field (for /). I think the proposed > structure could be a foundation for mathematically strict approaches (like > mechveliani's) but still be acceptable to 'ordinary users'. > > i put this proposal for discussion here and hope for suggestions how it can > be improved before i put it to haskell'! > > andrew frank > For a long time, there exist the following documents and programs * BAL library (implemented, downloadible) -- Basic Algebra Library for Haskell, which was a proposal for a new "Num"-like library. * A paper "Haskell and computer algebra" which describes the idea of BAL. * A paper "What should be an universal functional language", which describes, what are the problems of Haskell as related to algebra. These three items can be downloaded from www.botik.ru/~mechvel by clicking at BAL, and at the papers you choose. The main problem with the language can be illustrated by the following example. The domain Matrix(n, m) of matrices n by m depends on the ordinary values. These n, m can be computed in some cycle at run time. But in Haskell, we need to model a _domain_ as a _type_, with several _instances_ for this type. And these latter cannot evolve at run time. For example the domain Matrix(3, m) must have MultiplicativeSemigroup instance -- if m == 3, and must not have such instance otherwise. And m may change at run-time. This is the reason for why BAL looks so complicated -- and why the proposal has been rejected. (By the way, both these papers have been rejected by the conference referrees of the Haskell community and FP community). I think that without dependent types for a Haskell-like language, it is impossible to propose any adequate and in the same time plainly looking algebraic class system. ----------------- Serge Mechveliani mechvel(a)botik.ru

3 2

Justification for Ord inheriting from Eq?
by Brian Hulley 18 Apr '06

18 Apr '06

Hi - I've been wondering for a long time if there is a reason why Ord should inherit from Eq and not vice versa, or whether in fact there is any justification for making either Ord or Eq inherit from the other one. For example, Ord and Eq could alternatively be defined as: class Ord a where (<), (<=), (>=), (>) : a -> a -> Bool x <= y = not (y < x) x >= y = not (x < y) x > y = y < x class Ord a => Eq a where (==), (/=) :: a -> a -> Bool x /= y = x < y || y < x x == y = not (x /= y) Part of the reason for my question is that it seems to me that the lesson from object oriented programming is that inheritance is usually a bad idea, since very few things (perhaps nothing?) have a single natural taxonomy (witness the efforts to reorganise the numeric hierarchy that have been alluded to on this list). In languages such as C++ the only "good" use of inheritance seems to be when you have an abstract base class representing an interface and multiple concrete derived classes (as immediate children of it) representing the implementations, but in Haskell, this is the class/instance distinction, so I can't see a strong reason why Haskell classes should be allowed to inherit from other classes. Except perhaps Monad, MonadIO, MonadPlus etc... Any thoughts? Thanks, Brian.

14 22

Re: coherence when overlapping?
by oleg＠pobox.com 17 Apr '06

17 Apr '06

> But I am still confused by the exact definition of coherence in the case of > overlapping. Does the standard coherence theorem apply? If yes, how? > If no, is there a theorem? Yes, the is, by Martin Sulzmann et al, the Theory of overloading (the journal version) http://www.comp.nus.edu.sg/~sulzmann/ms_bib.html#overloading-journal A simple intuition is this: instance selection may produce more than one candidate instance. Having inferred a polymorphic type with constraints, the compiler checks to see of some of the constraints can be reduced. If an instance selection produces no candidate instances, the typechecking failure is reported. If there is exactly one candidate instance, it is selected and the constraint is removed because it is resolved. An instance selection may produce more then one candidate instance. Those candidate instances may be incomparable: for example, given the constraint "C a" and instances "C Int" and "C Bool", both instances are candidates. If such is the case, the resolution of that constraint is deferred and it `floats out', to be incorporated into the type of the parent expression, etc. In the presence of overlapping instances, the multiple candidate instances may be comparable, e.g. "C a" and "C Int". The compiler then checks to see if the target type is at least as specific as the most specific of those candidate instances. If so, the constraint is reduced; otherwise, it is deferred. Eventually enough type information is available to reduce all constraints (or else it is a type error).

3 4

Re: [Haskell] ANNOUNCE: An index-aware linear algebra library in Haskell
by Alberto Ruiz 16 Apr '06

16 Apr '06

On Friday 14 April 2006 17:02, Frederik Eaton wrote: > An index-aware linear algebra library in Haskell Excellent work! Is it possible to create a vector or matrix whose size is not known at compile time? > - Due to the need to specify index types at some point, input of > vectors is difficult. I have provided two functions in Fu.Vector.Base > which should cover most of the cases: > > listVec :: Vector v e => [e] -> (forall n . (ReflectNum n) => v (L n) -> w) > -> w > listMat :: Vector v e => [[e]] -> > (forall n m . (ReflectNum n, ReflectNum m) => v (L m, L n) -> w) -> w > > However, these aren't useful in interactive situations. So I have also > provided some template-haskell routines > > http://ofb.net/~frederik/futility/src/Vector/Template.hs > > which can be used to instantiate vectors directly. For example: (In examples.hs): >-- matrix with elements of type Double >v6 = trans $(dAM [[1,2,3,4]]) > >v7 = $(dAM [[1,0,0],[0,1,0],[0,0,1],[1,1,1]]) -- Alberto

2 3

Re: [Haskell-cafe] Code Review: Sudoku solver
by Michael Hanus 16 Apr '06

16 Apr '06

Jared Updike wrote: > On 3/22/06, David F. Place <d(a)vidplace.com> wrote: > ... > > It solves > > sudoku puzzles. (What pleasure do people get by doing these in their > > heads?!?) > > > > They are probably asking the same question: why take hours to write a > program to do it when with my mad sudoku solving skills I can solve it > in X seconds? My roommate is like this. I would say because they have chosen the wrong language for this problem :-) Solving Sudoku is a typical finite domain constraint problem. Thus, a language with constraint solving facilities like Curry (a combination of Haskell and constraint logic programming) is much better suited. Actually, I wrote a Sudoku solver in Curry and the actual code for the solver is 10 lines of code which is compact and well readable (if you are familiar with Haskell), see http://www.informatik.uni-kiel.de/~curry/examples/CLP/sudoku.curry Regards, Michael

11 35

web servers
by Tim Newsham 15 Apr '06

15 Apr '06

Hi Everyone, I'm new to the list, been on irc a bit. I'm still learning haskell. Wanted to say Hi before getting in to things... I'm interested in real-world programs in haskell, especially ones where security and formal methods are important. I'm looking at web servers right now. I found a copy of Simon Marlow's HWS on haskell.org's cvs server. I know there's a newer plugin version, but I cant find a working link to the actual code. I've been able to get the code to compile after a while, but it still has some warnings of deprecated features which I havent been able to get rid of (if anyone's interested in helping out, let me know). Anyway, I configured it an ran it and it works, although I have noticed two security flaws in it which need fixing. Is it possible there is a newer version with these flaws fixed? Besides HWS, what other web servers exist? Does anyone actually use a haskell based web server in practice? Which web server is considered the most mature? stable? fastest? I'm trying to decided if I should sink some time into HWS or if I should use another server. Tim Newsham http://www.lava.net/~newsham/

6 7

6.2.1 for glibc-2.4
by Paul A. Steckler 15 Apr '06

15 Apr '06

I need a Linux ghc 6.2.1 built with glibc-2.4. The existing 6.2.1 RPM, built with glibc-2.3, works mostly OK, but with some programs, the generated executables barf and die on startup. Any suggestions on how to create such a beast? I've tried using ghc 6.4.1, for which there's a Fedora 5 RPM, to build 6.2.1 from source, but all sorts of compile errors occur. On a Linux with glibc-2.3 installed, is there a way to have the ghc build use a different glibc? -- Paul -- Paul Steckler, PhD Tel: +1 503.626.6616 x156 Galois Connections, Inc. Fax: +1 503.350.0833 12725 SW Millikan Way, Beaverton, OR 97005 Email: steck(a)galois.com

1 0

AFP 2006: any news ?
by Alain Cremieux 14 Apr '06

14 Apr '06

Hi, Has anyone any news about an Advanced Functional Programming school, which was scheduled for 2006 ? Thanks, Alain

2 1

RuntimeLoader
by Tim Newsham 14 Apr '06

14 Apr '06

Hi, I'm about to start playing with HWS-WP (web server + plugins). It relies on RuntimeLoader: http://www.algorithm.com.au/wiki/hacking/haskell.ghc_runtime_loading I grabbed the example and built it (only one minor tweak to imports to get it to build) but it doesnt quite work: $ ./src/TextFilter ./plugins/Lower.o < README TextFilter: ./plugins/Lower.o: unknown symbol `__stginit_Char_' TextFilter: user error (resolveFunctions failed?False) There were also some warnings during building: Compiling RuntimeLoader ( ../runtime_loader/RuntimeLoader.hs, ./RuntimeLoader .o ) /tmp/ghc11951.hc: In function `s2Pj_ret': /tmp/ghc11951.hc:170: warning: implicit declaration of function `unloadObj' /tmp/ghc11951.hc: In function `s2JU_entry': [...] I assume this is because it is mucking with some ghc internals? Is anyone familiar with this package? Is there a more up-to-date version or alternative? Tim Newsham http://www.lava.net/~newsham/

3 2

Local Fundeps [was: Fundeps: I feel dumb]
by oleg＠pobox.com 14 Apr '06

14 Apr '06

Creighton Hogg posed the following problem. Given a rather straightforward matrix multiplication code > -- The elements and the size > data Vec a = Vec (Array Int a) Int deriving (Show,Eq) > type Matrix a = (Vec (Vec a)) > class MatrixProduct a b c | a b -> c where > (<*>) :: a -> b -> c > instance (Num a) => MatrixProduct a (Vec a) (Vec a) where > (<*>) num (Vec a s) = Vec (fmap (*num) a) s > vector n elms = Vec (array (0,n-1) $ zip [0..n-1] elms) n we'd like to get the following straightforward test to compile: > test = 10 <*> (vector 10 [0..9]) The trouble it doesn't: the function (<*>) has the type a->b->c so the type of the scalar doesn't have to be in any a priori relation with the type of the matrix (to permit efficient representations for particular sorts of matrices). Such a general type for (<*>) means that the test expression does not constrain "10" to be of the same numeric type as the type of matrix elements. So, the inferred type for test is test :: (Num a, Num b, MatrixProduct a (Vec b) c) => c The constraint must be resolved (top level, monomorphism restriction): but it can't because there is no instance MatrixProduct a (Vec b) c There is only more specialized instance, which doesn't match. The solution exists: change test so that the type of the scalar and the base type of the vector are the same: > test1 = (10::Int) <*> (vector 10 [0..9::Int]) > test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)]) or add the type annotations in other ways. But that is annoying. Creighton Hogg asked if there is another way? There is. Change the instances to > instance (Num a,Num b,TypeCast a b) => MatrixProduct a (Vec b) (Vec b) where > (<*>) num (Vec a s) = Vec (fmap (* (typeCast num)) a) s The difference is subtle but important: given such a general instance, trying to resolve "MatrixProduct a (Vec b) c" now succeeds. Instance selection is done only based on the types in the head; constraints are not taken into account. When the match succeeds, GHC commits to it and goes checking the constraints. One of the constraints, TypeCast a b, says that the type a must be the same as b. Because 'a' and 'b' were just type variables (could be instantiated), that constraint succeeds and we accomplished our task. Now the original test types and works. In short: given the instance "C a a" and the constraint "C a b", we see failure: "C a a" can't match "C a b". The type variables of the latter aren't instantiated: this is matching, not the full unification. The re-written instance "TypeCast a b => C a b", effectively describes the same set of types. Now, however, "C a b" matches that instance -- and, the TypeCast constraint forces "a" and "b" to be the same. These _local_, per-instance functional dependencies notably improve the power of instance selection: from mere matching to some type improvement (towards the full unification). The net result is fewer type annotations required from the user. One might consider that useful. The full code: {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module Foo where import Array data Vec a = Vec (Array Int a) Int deriving (Show,Eq) type Matrix a = (Vec (Vec a)) class MatrixProduct a b c | a b -> c where (<*>) :: a -> b -> c {- previously: instance (Num a) => MatrixProduct a (Vec a) (Vec a) where (<*>) num (Vec a s) = Vec (fmap (*num) a) s -} instance (Num a,Num b,TypeCast a b) => MatrixProduct a (Vec b) (Vec b) where (<*>) num (Vec a s) = Vec (fmap (* (typeCast num)) a) s vector n elms = Vec (array (0,n-1) $ zip [0..n-1] elms) n test = 10 <*> (vector 10 [0..9]) test1 = (10::Int) <*> (vector 10 [0..9::Int]) test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)]) class TypeCast a b | a -> b, b->a where typeCast :: a -> b class TypeCast' t a b | t a -> b, t b -> a where typeCast' :: t->a->b class TypeCast'' t a b | t a -> b, t b -> a where typeCast'' :: t->a->b instance TypeCast' () a b => TypeCast a b where typeCast x = typeCast' () x instance TypeCast'' t a b => TypeCast' t a b where typeCast' = typeCast'' instance TypeCast'' () a a where typeCast'' _ x = x

1 0

#if and #endif
by ihope 13 Apr '06

13 Apr '06

I grabbed the source code to Haddock, but GHC doesn't like the #if's and the #endif's. What can I do with these?

1 0

Re: [Haskell-cafe] Re: coherence when overlapping?
by Martin Sulzmann 13 Apr '06

13 Apr '06

I believe that GHC's overlapping instance extensions effectively uses inequalities. Why do you think that 'inequalities' model 'best-fit'? instance C Int -- (1) instance C a -- (2) under a 'best-fit' instance reduction strategy we would resolve C a by using (2). 'best-fit' should be very easy to implement. Simply order instances (resulting CHRs) in an appropriate 'best-fit' order. In case of instance C Int instance a =!=Int | C a (2') we can't reduce C a (because we can't satisfy a=!=Int) Notice that (2') translates to rule C a | a =!=Int <==> True I think it's better to write a =!=Int not as part of the instance context but write it as a guard constraint. I don't think there's any issue for an implementation (either using 'best-fit' or explicit inequalities). The hard part is to establish inference properties such as completeness etc. Martin Tom Schrijvers writes: > On Thu, 13 Apr 2006, Martin Sulzmann wrote: > > > > > Coherence (roughly) means that the program's semantics is independent > > of the program's typing. > > > > In case of your example below, I could type the program > > either use the first or the second instance (assuming > > g has type Int->Int). That's clearly bound. > > > > Guard constraints enforce that instances are non-overlapping. > > > > instance C Int > > instance C a | a =!= Int > > > > The second instance can only fire if a is different from Int. > > > > Non-overlapping instances are necessary but not sufficient to > > obtain coherence. We also need that types/programs are unambiguous. > > Claus Reinke was discussing this with me some time ago. He called it the > best fit principle, which would in a way, as you illustrate above, allow > inequality constraints to the instance head. You could even write it like: > > instance (a /= Int) => C a > > as you would do with the superclass constraints... I wonder whether > explicit inequality constraints would be useful on their own in all the > places where type class and equality constraints are used (class and > instance declarations, GADTs, ...). Or maybe it opens a whole new can of > worms :) > > Tom > > -- > Tom Schrijvers > > Department of Computer Science > K.U. Leuven > Celestijnenlaan 200A > B-3001 Heverlee > Belgium > > tel: +32 16 327544 > e-mail: tom.schrijvers(a)cs.kuleuven.be

4 3

Re: Fundeps: I feel dumb
by oleg＠pobox.com 13 Apr '06

13 Apr '06

Creighton Hogg wrote: > No instance for (MatrixProduct a (Vec b) c) > arising from use of `<*>' at <interactive>:1:3-5 > Probable fix: add an instance declaration for (MatrixProduct a > (Vec b) c) > In the definition of `it': it = 10 <*> (vector 10 ([0 .. 9])) Let us look at the instance class MatrixProduct a b c | a b -> c where (<*>) :: a -> b -> c instance (Num a) => MatrixProduct a (Vec a) (Vec a) where it defines what happens when multiplying a vector of some numeric type 'a' by a value _of the same_ type. Let us now look at the error message: > (MatrixProduct a (Vec b) c) That is, when trying to compile your expression 10 <*> (vector 10 ([0 .. 9])) the typechecker went looking for (MatrixProduct a (Vec b) c) where the value and the vector have different numeric types. There is no instance for such a general case, hence the error. It is important to remember that the typechecker first infers the most general type for an expression, and then tries to resolve the constraints. In your expression, 10 <*> (vector 10 ([0 .. 9])) we see constants 10, 10, 0, 9. Each constant has the type Num a => a. Within the expression 0 .. 9, both 0 and 9 must be of the same type (because [n .. m] is an abbreviation for enumFromThen n m, and according to the type of the latter enumFromThen :: a -> a -> [a] both arguments must be of the same type). But there is nothing that says that the first occurrence of 10 must be of the same numeric type as the occurrence of 9. So, the most general type assignment will be (Num a => a) for 10, and (Num b => b) for 9. Solution: either choose a specific (non-polymorphic type) > test1 = (10::Int) <*> (vector 10 [0..9::Int]) Or tell the typechecker that those constants must be of the same type: > test2 = let n = 10 in n <*> (vector 10 [0..(9 `asTypeOf` n)])

2 1

Counting bits: Sanity Check
by David F. Place 13 Apr '06

13 Apr '06

Hi All, Since it seems that real applications need more than just union, intersection, difference and complement to be fast to make EnumSet useful, I've been looking into the less naive approaches to the other things. In particular, size seems to find itself in the inner loop. I've made a comparison of various approaches to bit counting. It seems I was too hasty to declare Bulat's suggestion of table lookup (table,table32) the winner. It seems Robert's suggestion of Kernighan's (kern) method is faster. I also implemented the method described in pages 187-188 of Software Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors. (ones32) It's slower on my powerbook, but may be the winner on 64bit processors. Here are the results: [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 ones32 21 1.788u 0.136s 0:03.30 57.8% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table 21 2.404u 0.164s 0:04.96 51.6% 0+0k 0+1io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table32 21 2.067u 0.140s 0:04.27 51.5% 0+0k 0+0io 0pf+0w [Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 kern 21 1.729u 0.137s 0:03.25 56.9% 0+0k 0+1io 0pf+0w If you'd like to give it a whirl on your fancy modern computers, here's the code: ghc -O3 -optc-O3 -o bits BitTwiddle.hs Of course, if I've done something lame-brained and skewed the results, please let me know. Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com

4 6