Re: [Haskell-cafe] Generating random graph
On Mon, 11 Apr 2011, Mitar wrote: generateGraph :: Int - IO (Gr String Double) generateGraph graphSize = do when (graphSize 1) $ throwIO $ AssertionFailed $ Graph size out of bounds ++ show graphSize let ns = map (\n - (n, show n)) [1..graphSize] es - fmap concat $ forM [1..graphSize] $ \node - do nedges - randomRIO (0, graphSize) others - fmap (filter (node /=) . nub) $ forM [1..nedges] $ \_ - randomRIO (1, graphSize) gen - getStdGen let weights = randomRs (1, 10) gen return $ zip3 (repeat node) others weights return $ mkGraph ns es Just a note on style: This function can perfectly be written without IO. http://www.haskell.org/haskellwiki/Avoiding_IO#State_monad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] CFP: APLAS 2011, Kenting, Taiwan
==
APLAS 2011 Call For Papers
Ninth Asian Symposium on Programming Languages and Systems
Kenting, Taiwan, December 5--7, 2011
(co-located with CPP 2011)
http://flolac.iis.sinica.edu.tw/aplas11/
==
BACKGROUND:
APLAS aims at stimulating programming language research by
providing a forum for the presentation of latest results and
the exchange of ideas in topics concerned with programming
languages and systems. APLAS is based in Asia, but is an
international forum that serves the worldwide programming
language community.
APLAS is sponsored by the Asian Association for Foundation of
Software (AAFS) founded by Asian researchers in cooperation with
many researchers from Europe and the USA. The past APLAS symposiums
were successfully held in Shanghai ('10), Seoul ('09),
Bangalore ('08), Singapore ('07), Sydney ('06), Tsukuba ('05),
Taipei ('04) and Beijing ('03) after three informal workshops.
Proceedings of the past symposiums were published in
Springer-Verlag's LNCS 6461, 5904, 5356, 4807, 4279, 3780, 3302,
and 2895.
The 2011 edition will be held at Kenting, a seaside resort in
Southern Taiwan.
TOPICS:
The symposium is devoted to both foundational and practical
issues in programming languages and systems. Papers are solicited
on, but not limited to, the following topics:
+ semantics, logics, foundational theory;
+ design of languages and foundational calculi;
+ type systems;
+ compilers, interpreters, abstract machines;
+ program derivation and transformation;
+ program analysis, verification, model-checking, software security;
+ concurrency, constraints, domain-specific languages;
+ tools for programming, verification, implementation.
APLAS 2011 is not limited to topics discussed in previous
symposiums. Papers identifying future directions of
programming and those addressing the rapid changes of the
underlying computing platforms are especially welcome.
Demonstration of systems and tools in the scope of APLAS are
welcome to the System and Tool presentations category.
Authors concerned about the appropriateness of a topic are
welcome to consult with Program Chair prior to submission.
IMPORTANT DATES:
Abstract Deadline: June 13, 2011
Submission Deadline: June 17, 2011 (GMT)
Notification: August 29, 2011
Camera-Ready: September 19, 2011
INVITED SPEAKERS:
Nikolaj Bjorner, Microsoft Research Redmond
Ranjit Jhala, UC San Diego
Peter O'Hearn, Queen Mary U. London
Sriram Rajamani, Microsoft Research India
SUBMISSION INFORMATION:
We solicit submissions in two categories:
Regular research papers, describing original research results,
including tool development and case studies, from a perspective of
scientific research. Regular research papers should not exceed 16
pages in the Springer LNCS format, including bibliography and
figures. They should clearly identify what has been accomplished and
why it is significant. Submissions will be judged on the basis of
significance, relevance, correctness, originality, and clarity. In
case of lack of space, proofs, experimental results, or any
information supporting the technical results of the paper could be
provided as Appendix or a link to a web page.
System and Tool presentations, describing systems or tools that
support theory, program construction, reasoning, and/or program
execution in the scope of APLAS. Unlike presentations of regular
research papers, presentation of accepted papers in this category is
expected to be centered around a demonstration. The paper and the
demonstration should identify the novelties of the tools and use
motivating examples. System and Tool papers should not
exceed 8 pages in the Springer LNCS format, including bibliography and
figures. Submissions will be judged based on both the papers and the
systems or tools as described in the papers. It is highly desirable
that the tools are available on the web.
Papers should be submitted electronically via the submission web page
at http://www.easychair.org/conferences/?conf=aplas2011. Acceptable
formats are PostScript or PDF, viewable by Ghostview or Acrobat
Reader. Submitted papers must be unpublished and not submitted for
publication elsewhere. Papers must be written in English. The
proceedings are planned to be published as a volume in
Springer-Verlag's Lecture Notes in Computer Science series. Accepted
papers must be presented at the conference.
GENERAL CHAIR:
Tyng-Ruey Chuang, Academia Sinica, Taiwan
PROGRAM CHAIR:
Hongseok Yang, Queen Mary U. London
aplas2...@easychair.org
PROGRAM COMMITTEE:
Lars Birkedal (ITU, Denmark)
James Brotherston (Imperial College, UK)
Kung Chen (National Chengchi U., Taiwan)
Wenguang Chen (Tsinghua U., China)
Wei-Ngan Chin (NUS, Singapore)
Javier Esparza (TUM, Germany)
Xinyu Feng (USTC, China)
Jerome Feret (INRIA, France)
Matthew Fluet (RIT, USA)
Rajiv Gupta (UC Riverside, USA)
Masahito Hasegawa (Kyoto U., Japan)
[Haskell-cafe] already installed packages alerted as not being installed
Hello cafe-readers, does anyone of you observe similar problems e. g. on a Windows with ghc-7.0.2 setup: When I'm trying cabal install threadscope (as an example package depending on gtk2hs, latter which I've installed using the stepwise approach of cabal unpack first, then cabal configure --user etc.) it complains about cairo etc. not being installed and tries to re-install it on-the-fly, failing due to whats described her: http://hackage.haskell.org/trac/gtk2hs/ticket/1203! When I install cabal-dev and cab first and then re-install everything with cab instead of cabal the issue with re-installing already installed packages described above disappears and only an unknown symbol message related to the correctly found installed cairo package remains. So is there an error in package database handling somewhere or changed semantics in cabal | ghc-pkg | (even) pkg-config flags I missed? Cheers Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] already installed packages alerted as not being installed
Hello, When I install cabal-dev and cab first and then re-install everything with cab instead of cabal the issue with re-installing already installed packages described above disappears and only an unknown symbol message related to the correctly found installed cairo package remains. So is there an error in package database handling somewhere or changed semantics in cabal | ghc-pkg | (even) pkg-config flags I missed? cab is just a wrapper for cabal and cabal-dev for installation. So, I have no idea about what's going on. Please try cab install package -n to see what will happen before typing cab install package. If you find the word reinstall, you should not install the package because the installation operation will break your package environment. You can analyze package dependency with: cab deps package -r cab revdeps package -r cab list -r Adding the -a option displays global packages also. I recommend to use a sandbox when you try to resolve a dependency problem. --Kazu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] already installed packages alerted as not being installed
Kazu, thanks I wanted to mention that the unknown symbol error is very likely not related to the cab tool as the same error appears, when using the cabal - tool. I guess we can ignore it even in the context of my main question, sorry for being to verbose. What I found more interesting is, that cab doesn't try to re-install an installed package - already in the database too, as ghc-pkg output pretends - which is expected behaviour. The cabal system frontend obviously does trying to reinstall the package though. This seems like different model of reality... Cheers Daniel 2011/4/11 Kazu Yamamoto k...@iij.ad.jp: Hello, When I install cabal-dev and cab first and then re-install everything with cab instead of cabal the issue with re-installing already installed packages described above disappears and only an unknown symbol message related to the correctly found installed cairo package remains. So is there an error in package database handling somewhere or changed semantics in cabal | ghc-pkg | (even) pkg-config flags I missed? cab is just a wrapper for cabal and cabal-dev for installation. So, I have no idea about what's going on. Please try cab install package -n to see what will happen before typing cab install package. If you find the word reinstall, you should not install the package because the installation operation will break your package environment. You can analyze package dependency with: cab deps package -r cab revdeps package -r cab list -r Adding the -a option displays global packages also. I recommend to use a sandbox when you try to resolve a dependency problem. --Kazu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fucntion composing
Hello, as I am newbie to Haskell and my introductory question is: given functions say f and g with type signatures f :: (Num a) = [a] - [a] - [(a,a)] // f takes two lists and zips them into one in some special way g :: (Num a) = a - [(a,a)] - [a] // g using some Num value calculates list of singletons from list of pairs of course g 0 :: (Num a) = [(a,a)] -[a] now I want to create function h :: (Num a) = [a] - [a] - [a] in such way that (g 0) consumes output of f. But when I try Prelude :t (g 0).f I get an error: interactive:1:9: Couldn't match expected type `[(a0, a0)]' with actual type `[a1] - [(a1, a1)]' Expected type: [a1] - [(a0, a0)] Actual type: [a1] - [a1] - [(a1, a1)] In the second argument of `(.)', namely `f' In the expression: (g 0) . f In pointfull representation it works well Prelude let h x y = (g 0 (f x y)) How to do pointfree definition of h? Ajschylos. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] already installed packages alerted as not being installed
Hello, thanks I wanted to mention that the unknown symbol error is very likely not related to the cab tool as the same error appears, when using the cabal - tool. I guess we can ignore it even in the context of my main question, sorry for being to verbose. What I found more interesting is, that cab doesn't try to re-install an installed package - already in the database too, as ghc-pkg output pretends - which is expected behaviour. The cabal system frontend obviously does trying to reinstall the package though. This seems like different model of reality... This is not true. cab install re-installs some packages if necessary, unfortunately. That's why I recommend to use cab install -n. --Kazu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fucntion composing
Prelude let h x y = (g 0 (f x y)) How to do pointfree definition of h? See the thread http://thread.gmane.org/gmane.comp.lang.haskell.cafe/70488for related material. Regards, Sean ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Generating random graph
Hi! On Mon, Apr 11, 2011 at 7:36 AM, Steffen Schuldenzucker sschuldenzuc...@uni-bonn.de wrote: So when using randomRs, the state of the global random number generator is not updated, but it is used again in the next iteration of the toplevel forM [1..graphSize] loop. I thought it would be interleaved. Thanks. Mitar ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fucntion composing
On Monday 11 April 2011 11:22:51, Adam Krauze wrote: Hello, as I am newbie to Haskell and my introductory question is: given functions say f and g with type signatures f :: (Num a) = [a] - [a] - [(a,a)] // f takes two lists and zips them into one in some special way g :: (Num a) = a - [(a,a)] - [a] // g using some Num value calculates list of singletons from list of pairs of course g 0 :: (Num a) = [(a,a)] -[a] now I want to create function h :: (Num a) = [a] - [a] - [a] in such way that (g 0) consumes output of f. But when I try Prelude :t (g 0).f I get an error: interactive:1:9: Couldn't match expected type `[(a0, a0)]' with actual type `[a1] - [(a1, a1)]' Expected type: [a1] - [(a0, a0)] Actual type: [a1] - [a1] - [(a1, a1)] In the second argument of `(.)', namely `f' In the expression: (g 0) . f In pointfull representation it works well Prelude let h x y = (g 0 (f x y)) How to do pointfree definition of h? Composition treats one argument, so h x y = g 0 (f x y) = (g 0) (f x y) ~ h x = (g 0) . (f x) ~ h = ((g 0) .) . f for each argument of the function to be applied first, you need one composition operator. But (((foo .) .) .) . bar and such quickly become unreadable, so know when to stop point-freeing such multi-compositions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Parsing HTML tables with HXT
Thanks! I was also able to extract the needed value with the code below: testArrow :: IOSArrow XmlTree XmlTree testArrow = deep (isElem hasName table ) deep (isElem hasName tr) (deep isText hasText (==a)) `guards` (getChildren getChildren isText) 2011/4/11 Albert Y. C. Lai tre...@vex.net On 11-04-08 06:29 AM, Dmitry Simonchik wrote: Can someone please help me with getting the value of the table cell with HXT in the following html: table class=tblc tr td class=tdcx/td tdy/td /tr tr td class=tdca/td tdb/td /tr /table I need the value of the second cell in a row that has first cell with some predefined value (in the example above it can be x or a) I need the arrow of the type (IOSArrow XmlTree String) How to write it? import Text.XML.HXT.Core main = do rs - runX (readDocument [] example.xml example x) mapM_ putStrLn rs -- example blah reports those 2nd columns such that -- their 1st columns equal blah example :: String - IOSArrow XmlTree String example s = deep (is table / is tr listA (getChildren is td / getText) arrL get2nd ) where get2nd (one:two:_) | one==s = [two] get2nd _ = [] is x = isElem hasName x The important part is using listA at the right point to extract the list of cells (belonging to the same row) so that with a list in your hand you can test the 1st item and find the 2nd item. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Foreign function performance: monadic vs pure
Consider two versions of sin wrapped: foreign import ccall math.h sin c_sin_m :: CDouble - IO CDouble and foreign import ccall math.h sin c_sin :: CDouble - CDouble One can invoke them so: mapM c_sin_m [1..n] mapM (return . c_sin) [1..n] On my computer with n = 10^7 the first version never finishes, whereas the second one calculates the result within seconds. To give you my context, I need to call a random variable generator multiple times, so that it must return IO a. Any explanation for this behavior? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fucntion composing
Thanks all! You helped me a lot. Adam. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to optmize this code?
Hi Guys,
Thanks all for the suggestions, I have certainly improved my knowledge.
I made a blog post to show all the possible solution a problem can
have. you can check it out at katacoder.blogspot.com
Giba
On Sun, Apr 10, 2011 at 3:35 AM, Johan Tibell johan.tib...@gmail.com wrote:
Hi Gilberto,
On Wed, Mar 30, 2011 at 4:39 PM, Gilberto Garcia giba@gmail.com wrote:
fkSum :: Int - [Int] - Int
fkSum a [] = 0
fkSum a (b) = foldl (+) 0 (filter (\x - isMultiple x b) [1..a])
isMultiple :: Int - [Int] - Bool
isMultiple a [] = False
isMultiple a (x:xs) = if (mod a x == 0) then True else isMultiple a xs
You can make both these functions a little bit more efficient by
making them strict in the first argument, like so:
{-# LANGUAGE BangPatterns #-}
fkSum :: Int - [Int] - Int
fkSum !a [] = 0
fkSum a (b) = foldl (+) 0 (filter (\x - isMultiple x b) [1..a])
isMultiple :: Int - [Int] - Bool
isMultiple !a [] = False
isMultiple a (x:xs) = if (mod a x == 0) then True else isMultiple a xs
This change ensures that the first argument is always evaluated.
Before `fkSum undefined []` would return 0, now it results in an
error. The upside is that when a function is strict in an argument,
GHC can use a more efficient calling convention for the function. In
this case it means that instead of passing the first argument as a
pointer to a machine integer, it can pass the machine integer directly
(in a register).
This optimization is particularly worthwhile for accumulator parameters.
Johan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fucntion composing
On Mon, 2011-04-11 at 11:22 +0200, Adam Krauze wrote: f :: (Num a) = [a] - [a] - [(a,a)] // f takes two lists and zips them into one in some special way g :: (Num a) = a - [(a,a)] - [a] // g using some Num value calculates list of singletons from list of pairs Prelude let h x y = (g 0 (f x y)) How to do pointfree definition of h? You can eliminate the second point, y, pretty easily by just using function composition: let h x = g 0 . f x To eliminate x, we can first rewrite this expression using a section of the (.) operator. let h x = (g 0 .) (f x) and then introduce another function composition: let h = (g 0 .) . f Whether that's clearer than the pointed definition is up for debate, but there it is. Just keep in mind that sections of (.) are very confusing to some people. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Emscripten: compiling LLVM to JavaScript
Hi all! I haven't tried the tool myself, but it seems interesting to the Haskell efforts to compile to JavaScript: http://syntensity.blogspot.com/2011/04/emscripten-10.html Cheers, Sönke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
On Mon, 2011-04-11 at 12:09 +, Serguei Son wrote: Consider two versions of sin wrapped: foreign import ccall math.h sin c_sin_m :: CDouble - IO CDouble and foreign import ccall math.h sin c_sin :: CDouble - CDouble One can invoke them so: mapM c_sin_m [1..n] mapM (return . c_sin) [1..n] On my computer with n = 10^7 the first version never finishes, whereas the second one calculates the result within seconds. To give you my context, I need to call a random variable generator multiple times, so that it must return IO a. Any explanation for this behavior? Simple (but possibly wrong) - the first one is always evaluated (as it might have side-effects) while the second one is left in unevaluated form (return does not force effects): (values for 2^14) mapM c_sin_m [1..n] 1.087 s mapM (return . c_sin) [1..n] 0.021 s mapM (\x - return $! c_sin x) [1..n] 1.160 s return $ map c_sin [1..n] 0.006 s mapM (const (return undefined)) [1..n] 0.011 s I.e. - c_sin_m have forced evaluation so you do 10^7 times save of Haskell context (it is not marked as unsafe) and call of function - return . c_sin have not forced evaluation so you do 10^7 times wrap unevaluated value into IO To compare: foreign import ccall unsafe math.h sin c_sin_um :: CDouble - IO CDouble foreign import ccall unsafe math.h sin c_sin_u :: CDouble - CDouble main = mapM c_sin_um [1..n] 0.028 s main = mapM (\x - return $! c_sin_u) [1..n] 0.012 s main = mapM (return . c_sin_u) [1..n] 0.023 s I.e. it is difference in laziness of Haskell and the making sure that function may safely call back to Haskell (which sin does not). Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
On Mon, Apr 11, 2011 at 10:14 AM, Maciej Marcin Piechotka uzytkown...@gmail.com wrote: main = mapM (\x - return $! c_sin_u) [1..n] 0.012 s This should be main = mapM (\x - return $! c_sin_u x) [1..n] -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
Felipe Almeida Lessa felipe.lessa at gmail.com writes: On Mon, Apr 11, 2011 at 10:14 AM, Maciej Marcin Piechotka uzytkownik2 at gmail.com wrote: main = mapM (\x - return $! c_sin_u) [1..n] 0.012 s This should be main = mapM (\x - return $! c_sin_u x) [1..n] So if I must use a safe function returning IO a, there is no way to improve its performance? To give you a benchmark, calling gsl_ran_ugaussian a million times in pure C takes only a second or two on my system. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
Serguei Son serguei.son at gmail.com writes: Felipe Almeida Lessa felipe.lessa at gmail.com writes: On Mon, Apr 11, 2011 at 10:14 AM, Maciej Marcin Piechotka uzytkownik2 at gmail.com wrote: main = mapM (\x - return $! c_sin_u) [1..n] 0.012 s This should be main = mapM (\x - return $! c_sin_u x) [1..n] So if I must use a safe function returning IO a, there is no way to improve its performance? To give you a benchmark, calling gsl_ran_ugaussian a million times in pure C takes only a second or two on my system. Also, please note that I can force the evaluation of c_sin, e.g. mapM (return . c_sin) [1..n] = (print $ foldl' (+) 0) And it will still execute reasonably fast. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
Serguei Son serguei.son at gmail.com writes: Also, please note that I can force the evaluation of c_sin, e.g. mapM (return . c_sin) [1..n] = (print $ foldl' (+) 0) And it will still execute reasonably fast. Pls disregard the my previous post. I actually meant let lst = map c_sin [1..n] print $ foldl' (+) 0 lst This executes in 0.2 s for n = 10^7. c_sin is safe, as well as c_sin_m. The only difference is CDouble - CDouble vs CDouble - IO CDouble. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] already installed packages alerted as not being installed
Ingenious, finally it is possible at least with the help of those two tools cabal-dev and cab to build the threadscope executable on Windows linked against gtk+-bundle_2.22.1-20101227_win32 version, thanks again to their developers. [Note to myself] How I did, 1) as described in http://hackage.haskell.org/trac/gtk2hs/ticket/1203#comment:2 edited each Gtk2HsSetup.hs file 2) In a mingw+msys shell (tar is needed, how to install - I strongly recommend using mingw-get-inst: http://sourceforge.net/projects/mingw/files/Automated%20MinGW%20Installer/mingw-get-inst/ to mention at a first place, you can easily add things then with the bundled mingw-get command) did pushd /h/.homedir cabal-dev add-source /h/.homedir/gtk2hs-buildtools-0.12.0/ /h/.homedir/glib-0.12.0/ /h/.homedir/cairo-0.12.0/ /h/.homedir/gio-0.12.0/ /h/.homedir/glade-0.12.0/ /h/.homedir/pango-0.12.0/ /h/.homedir/gtk-0.12.0/ cab install threadscope --sandbox=/h/.homedir/cabal-dev To be honest the last command I even run at the Windows cmd.exe prompt. This all means h:/.homedir/cabal-dev contains the formerly broken dependencies sources patched by my edits in the .cabal files. It is used (--sandbox parameter) as a first repository for building threadscope later on, the other dependencies are loaded remotely by demand. The reason for breaking with cabal I could see as mentioned above by Kazu, with: cab install threadscope -n threadscope needed different versions than the dependencies pre-installed with my former gtk2hs installation trial had. Cheers Daniel 2011/4/11 Kazu Yamamoto k...@iij.ad.jp: Hello, thanks I wanted to mention that the unknown symbol error is very likely not related to the cab tool as the same error appears, when using the cabal - tool. I guess we can ignore it even in the context of my main question, sorry for being to verbose. What I found more interesting is, that cab doesn't try to re-install an installed package - already in the database too, as ghc-pkg output pretends - which is expected behaviour. The cabal system frontend obviously does trying to reinstall the package though. This seems like different model of reality... This is not true. cab install re-installs some packages if necessary, unfortunately. That's why I recommend to use cab install -n. --Kazu ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
On Mon, Apr 11, 2011 at 8:09 AM, Serguei Son serguei@gmail.com wrote: Consider two versions of sin wrapped: foreign import ccall math.h sin c_sin_m :: CDouble - IO CDouble Marking this call as unsafe (i.e. foreign import ccall unsafe math.h sin) can improve performance dramatically. If the FFI call is quick, then I believe this is the recommended approach. If you really need the imported function to be thread safe, then perhaps you should move more of the calculation into C to decrease the granularity of FFI calls. It is remarkably easy to get the meanings of safe and unsafe confused, and I can't even see the word unsafe in the current FFI user's guide! http://www.haskell.org/ghc/docs/7.0.3/html/users_guide/ffi-ghc.html Anthony and foreign import ccall math.h sin c_sin :: CDouble - CDouble One can invoke them so: mapM c_sin_m [1..n] mapM (return . c_sin) [1..n] On my computer with n = 10^7 the first version never finishes, whereas the second one calculates the result within seconds. To give you my context, I need to call a random variable generator multiple times, so that it must return IO a. Any explanation for this behavior? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Emscripten: compiling LLVM to JavaScript
On 11 April 2011 14:54, Sönke Hahn sh...@cs.tu-berlin.de wrote: I haven't tried the tool myself, but it seems interesting to the Haskell efforts to compile to JavaScript: http://syntensity.blogspot.com/2011/04/emscripten-10.html Good grief, that sounds incredibly awesome. GHC → LLVM → JS. Get all GHC's goodies *and* not have to write JS for targeting browsers. Very interested. I will mess with it tonight. Cheers! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Emscripten: compiling LLVM to JavaScript
Can JS in a browser call out to heavy computational routines in Haskell? I suppose JS run as a scripting language outside the browser can call out to Haskell. Can Haskell open and interact with a browser window without going through a server like component? On Mon, Apr 11, 2011 at 9:02 AM, Christopher Done chrisd...@googlemail.com wrote: On 11 April 2011 14:54, Sönke Hahn sh...@cs.tu-berlin.de wrote: I haven't tried the tool myself, but it seems interesting to the Haskell efforts to compile to JavaScript: http://syntensity.blogspot.com/2011/04/emscripten-10.html Good grief, that sounds incredibly awesome. GHC → LLVM → JS. Get all GHC's goodies *and* not have to write JS for targeting browsers. Very interested. I will mess with it tonight. Cheers! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- -- Regards, KC ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Emscripten: compiling LLVM to JavaScript
On Mon, Apr 11, 2011 at 3:54 PM, Sönke Hahn sh...@cs.tu-berlin.de wrote: Hi all! I haven't tried the tool myself, but it seems interesting to the Haskell efforts to compile to JavaScript: http://syntensity.blogspot.com/2011/04/emscripten-10.html I saw this same article this morning. I personally am not so interested in compiling Haskell to run as Javascript, though it definitely sounds like a nice idea. I was wondering if we can somehow build Haskell/LLVM bytecode bundles, similar to how Java code gets distributed as JARs. Imagine being able to do any/all of these: * Build a bundle from any package on Hackage. * Have a utility that can convert this to Javascript via emscripten * Create a Haskell runtime for different OSes that can run these bundles, and comes complete with GTK/Qt and a few other basic libraries. * Convert a bundle into something that can run natively on the JVM or CLR. * Create a Haskell Web Start where Haskell bundles can be run with a single click from the browser. This is far from my area of expertise, but I know that I could put such a system to good use. A lot of this stuff (running on JVM/CLR for instance) already has a good head start from efforts in the LLVM world. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Emscripten: compiling LLVM to JavaScript
I do wonder how Emscripten handles the GHC calling convention that is part of LLVM. In particular, global register declarations in the RTS scare me from a side line view, and LLVM's calling convention support is what makes the combination work at all in a registered environment. It's currently not even possible to compile code using global register variables to LLVM bitcode - it requires support everywhere from the frontend all the way to code generation. This is why LLVM uses a custom calling convention for GHC. The custom CC is also needed to make sure things like GC etc can work accurately - GC roots for example are always in predictable physical registers or somesuch. The RTS will probably need to be heavily modified or flat-out re-implemented in JS for this to work, I'd think (similar to ghcjs.) It's possible to get GHC to generate code that does not use global register variables (normally used when compiling via C, use ack and search for 'NO_REGS' in the source. It's primarily for unregisterized builds.) The result is fairly POSIX-compliant code that could be compiled with, say, clang to produce bitcode. However, forcing NO_REGS across GHC will mean that certain STG 'registers' are instead mapped to stack locations, not real physical registers. So it changes the calling convention. The LLVM calling convention is currently only built to handle a registerized GHC from what I've seen, and upon entry to STG-land, it's going to expect that certain STG registers are pinned to physical machine registers. Result: disasterous CC mismatch. Of course, perhaps re-implementing the RTS in JS isn't a terrible, terrible idea. You could for example, swap out GHC's lightweight threading to use webworkers or somesuch. This would probably be a hell of a lot more difficult if you were compiling the real C RTS code into JS indirectly via LLVM. I don't know if Emscripten is the way to go for compiling Haskell to JS, but it does open up more possibilities. It's going to be a lot of work no matter how you approach it though - perhaps we need some interested team of people willing to do the research. (NB: I could be wrong on the LLVM note; David T. or one of the Simons would probably know more and be more qualified to answer.) On Mon, Apr 11, 2011 at 7:54 AM, Sönke Hahn sh...@cs.tu-berlin.de wrote: Hi all! I haven't tried the tool myself, but it seems interesting to the Haskell efforts to compile to JavaScript: http://syntensity.blogspot.com/2011/04/emscripten-10.html Cheers, Sönke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Regards, Austin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Emscripten: compiling LLVM to JavaScript
Time ago YHC compiler (not longer active) got additional backend that generated JS from Yhc.Core. It was working quite ok. You can still find demos online. Generating JS (high level code) from Ghc.Core feels better than from low level code of LLVM. Is GHC.core very different from YHC.core? Sz. On Mon, Apr 11, 2011 at 6:02 PM, Christopher Done chrisd...@googlemail.comwrote: On 11 April 2011 14:54, Sönke Hahn sh...@cs.tu-berlin.de wrote: I haven't tried the tool myself, but it seems interesting to the Haskell efforts to compile to JavaScript: http://syntensity.blogspot.com/2011/04/emscripten-10.html Good grief, that sounds incredibly awesome. GHC → LLVM → JS. Get all GHC's goodies *and* not have to write JS for targeting browsers. Very interested. I will mess with it tonight. Cheers! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Tuple
Anwar Bari schrieb: I have to make a function to check that I have one occurrence of the last element (z) of the same list [a,b] in the tuple How about using Data.Map? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Foreign function performance: monadic vs pure
On Mon, Apr 11, 2011 at 3:55 PM, Serguei Son serguei@gmail.com wrote: So if I must use a safe function returning IO a, there is no way to improve its performance? To give you a benchmark, calling gsl_ran_ugaussian a million times in pure C takes only a second or two on my system. In the C version, are you also producing a linked list containing all of the values? Because that's what mapM does. Your test is mostly measuring the cost of allocating and filling ~3 million machine words on the heap. Try mapM_ instead. G -- Gregory Collins g...@gregorycollins.net ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Stacking data types
Yep you probably don't need the fundep, you just might need to provide more
signatures. It does imply one 'b' for an 'a' which probably isn't what you
want.
On Wed, Apr 6, 2011 at 6:13 PM, Yves Parès limestr...@gmail.com wrote:
Thank you all,
In fact, Brandon, I knew about Datatypes a la carte, I just found it overly
complicated.
Thanks for you solution, Job. However (and even if it doesn't work without
it) I fail to see why you need the functional dependency on Has...
Doesn't it implies here that for one 'a' there can only be one 'b' such as
'Has b a'?
2011/4/6 Job Vranish job.vran...@gmail.com
I think you want something like this:
{-# Language MultiParamTypeClasses
, FlexibleInstances
, FunctionalDependencies
, UndecidableInstances
, FlexibleContexts
, OverlappingInstances
#-}
data Character a = Character { life :: Int,
charaInner :: a }
deriving (Show)
data Gun a = Gun { firepower :: Int,
gunInner :: a }
deriving (Show)
data Armor a = Armor { resistance :: Int,
armorInner :: a }
deriving (Show)
class HasInner f where
getInner :: f a - a
instance HasInner Character where
getInner = charaInner
instance HasInner Gun where
getInner = gunInner
instance HasInner Armor where
getInner = armorInner
class Has b a | a - b where
content :: a - b
instance (Has b a, HasInner f) = Has b (f a) where
content a = content $ getInner a
instance (HasInner f) = Has a (f a) where
content a = getInner a
chara = Character 100 $ Armor 40 $ Gun 12 ()
itsGun :: (Has (Gun b) a) = a - Gun b
itsGun = content
You were missing a mechanism to extract the inner value from your
datatypes.
- Job
On Wed, Apr 6, 2011 at 2:57 PM, Yves Parès limestr...@gmail.com wrote:
Hello Café,
I'm trying to get some modular data types.
The idea that came to me is that I could stack them, for instance :
data Character a = Character { life :: Int,
charaInner :: a }
data Gun a = Gun { firepower :: Int,
gunInner :: a }
data Armor a = Armor { resistance :: Int,
armorInner :: a }
Then a character with a gun and an armor can be build this way:
chara = Character 100 $ Armor 40 $ Gun 12
The idea now is to be able to get some part of the character:
itsGun :: Character ?? - Gun ??
itsGun = content
Then content would be a class method:
class Has b a where
content :: a - b
And it would be recursively defined so that:
instance (Has c b, Has b a) = Has c a where
content = (content :: b - c) . (content :: a - b)
Then itsGun would be more like:
itsGun :: (Has Gun a) = a - Gun ??
itsGun = content
But after some juggling with extensions (ScopedTypeVariables,
UndecidableInstances, IncoherentInstances...) I can't get it working.
Has someone a simpler way to achieve modular types?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fucntion composing
In addition to what others have said, you could use pointfree[1] to do this automagically! pointfree h x y = (g 0 (f x y)) h = (g 0 .) . f [1] http://hackage.haskell.org/package/pointfree On 11 April 2011 10:22, Adam Krauze ajschy...@mac.com wrote: Hello, as I am newbie to Haskell and my introductory question is: given functions say f and g with type signatures f :: (Num a) = [a] - [a] - [(a,a)] // f takes two lists and zips them into one in some special way g :: (Num a) = a - [(a,a)] - [a] // g using some Num value calculates list of singletons from list of pairs of course g 0 :: (Num a) = [(a,a)] -[a] now I want to create function h :: (Num a) = [a] - [a] - [a] in such way that (g 0) consumes output of f. But when I try Prelude :t (g 0).f I get an error: interactive:1:9: Couldn't match expected type `[(a0, a0)]' with actual type `[a1] - [(a1, a1)]' Expected type: [a1] - [(a0, a0)] Actual type: [a1] - [a1] - [(a1, a1)] In the second argument of `(.)', namely `f' In the expression: (g 0) . f In pointfull representation it works well Prelude let h x y = (g 0 (f x y)) How to do pointfree definition of h? Ajschylos. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ozgur Akgun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Higher-kinded Quantification
I have a type constructor (Iterator i o m a) of kind (* - * - (* -
*) - *), which is a monad transformer, and I'd like to use the type
system to express the fact that some computations must be pure, by
writing the impredicative type (Iterator i o (forall m. m) a).
However I've run into a bit of difficulty expressing this, due to the
kind of m. I've attached a minimal-ish example. Is there a way to
express this in GHC?
{-# LANGUAGE ImpredicativeTypes #-}
{-# LANGUAGE KindSignatures #-}
data Iterator i o m a
= NeedInput (i - Iterator i o m a)
| HasOutput o (Iterator i o m a)
| NeedAction (m (Iterator i o m a))
| IsDone a
feedPure :: [i] - Iterator i o (forall m . m) a - Iterator i o (forall m . m) a
feedPure = loop
where
loop [] iter = iter
loop (i:is) (NeedInput k)= loop is (k i)
loop is (HasOutput o k0) = HasOutput o (loop is k0)
loop _ (NeedAction _) = undefined -- shouldn't happen, due to type
loop _ (IsDone a) = IsDone a
{-
impredicative.hs:10:34:
Kind mis-match
The third argument of `Iterator' should have kind `* - *',
but `m' has kind `*'
In the type signature for `feedPure':
feedPure :: [i]
- Iterator i o (forall m. m) a - Iterator i o (forall m. m) -}
feedPure' :: [i] - Iterator i o (forall m . (m :: * - *)) a - Iterator i o (forall m . (m :: * - *)) a
feedPure' = loop
where
loop [] iter = iter
loop (i:is) (NeedInput k)= loop is (k i)
loop is (HasOutput o k0) = HasOutput o (loop is k0)
loop _ (NeedAction _) = undefined
loop _ (IsDone a) = IsDone a
{-
impredicative.hs:28:46:
`(m :: * - *)' is not applied to enough type arguments
Expected kind `*', but `(m :: * - *)' has kind `* - *'
In the type signature for `feedPure'':
feedPure' :: [i]
- Iterator i o (forall m. (m :: * - *)) a
- Iterator i o (forall m. (m :: * - *)) a
-}
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Assimp FFI Library
Hello, I've been working on an ffi library for the Assimp asset import library( http://assimp.sourceforge.net). It should be useful for people doing graphics in Haskell. I've been working on it so I can import models into a ray-tracer I've been working on. My current progress is here: https://github.com/joelburget/assimp. A couple weeks ago I managed to import models and do some simple (and slightly buggy) renders, but since then I've been redoing a lot of the guts of the library. At this moment it doesn't build because of the changes I'm in the middle of. Hopefully I'll be able to release the first version in the next week or so. I've run into a few roadblocks that I would be thankful for help with. 1. In Graphics.Formats.Assimp.Vec I'm trying to get the fastest and smallest possible vector types since a program could easily have millions of vectors in memory and operations on them take a huge fraction of the time in an average program. One problem I ran into is how to make the vectors type-safe. The assimp library has separate data types for colors and vectors, but represented the same in memory. I have a few ideas about how to represent these: a. The way I've been doing it: data N2 data N3 data N4 data Color class Num a = Vector n a where data Vec n a :: * - * ... rest of class -- A 3-dimensional vector of doubles. t is the (phantom) tag type, like Color, Direction, etc -- This is meant to improve type safety instance Vector N3 Double where data Vec N3 Double t = Vec3D !Double !Double !Double deriving (Show, Eq) ... rest of instance This seems very close to what I want, but it presents a few problems. First, I create matrices from vectors, so the matrix must have an implicit type, the type of the tags from the vectors it is made of. I made this () by convention but then to multiply a vector by this matrix I have to use the dot product and other vector operations, but then the tag type from the matrix is different from that of the matrix I am multiplying. This leads to the type `dot :: Vec n a t1 - Vec n a t2 - a`. Notice how there are two different tag types, reducing type safety. Another problem is importing vectors from the library. I would like to have different tags for distance and direction, again to increase type safety, but they are both represented the same way in the library, so the Storable instance can't always know what type to create. I would probably always have to return a vector with tag type (). b. Just create separate Vec and Color datatypes. I would be mirroring the library directly. Both would be instances of Vector. c. Use newtype wrappers around Vec to represent the different types. I don't really like this solution because the newtypes are too painful to use. d. I've thought about some other solutions that I've forgotten now. Maybe you have something better! Remember, I would like to have a high degree of type safety if possible, but the top consideration is performance. Another thing I've been wondering about: could I use overlapping instances to allow the vectors to be of any numeric type, but specialize and unbox them for the common ones? I'm assuming unboxing can't be done unless we have a specific type because the compiler won't know how large the type is. 2. How do people feel about the vector and matrix operators (eg |*|, |*||, ||*)? I like them a lot but I would like to see how other people feel about them. 3. Do I have to worry about marshalling float, double, and int straight to Haskell? The report says Float and Double should conform to the IEEE standard. I'm more interested in Int since the report only requires a 30 bit Int. On my computer they appear to be 64 bits. Does this vary on 32 bit computers? 4. There are several places the original library uses unsigned ints. Obviously they can't be negative so I used CUInt in the Haskell code. I never see CUInt instead of Int in real code. Should I change these? 5. I've reduced a lot of boilerplate in Vec.hs by using the CPP preprocessor extension. I could reduce the boilerplate by another factor of 3 if I could recursively call templates but that's not allowed. I would like to have one template to generate both of these lines: data Vec N2 Double t = Vec2D !Double !Double deriving (Show, Eq) data Vec N3 Double t = Vec3D !Double !Double !Double deriving (Show, Eq) Notice there is an extra !Double in the second. Is there an easy way to do this? I don't know much about Template Haskell, would that work? Would it be easy? I should mention that I'm going to convert all the Storable instances from something like this: peek p = do w - (#peek aiQuaternion, w) p x - (#peek aiQuaternion, x) p y - (#peek aiQuaternion, y) p z - (#peek aiQuaternion, z) p return $ Quaternion w x y z to something like this: peek p = Quaternion $ (#peek aiQuaternion, w) p * (#peek aiQuaternion, w) p * (#peek aiQuaternion, w) p * (#peek
Re: [Haskell-cafe] Assimp FFI Library
On Mon, Apr 11, 2011 at 8:38 PM, Joel Burget joelbur...@gmail.com wrote:
Hello,
I've been working on an ffi library for the Assimp asset import library(
http://assimp.sourceforge.net). It should be useful for people doing
graphics in Haskell. I've been working on it so I can import models into a
ray-tracer I've been working on. My current progress is here:
https://github.com/joelburget/assimp. A couple weeks ago I managed to
import models and do some simple (and slightly buggy) renders, but since
then I've been redoing a lot of the guts of the library. At this moment it
doesn't build because of the changes I'm in the middle of. Hopefully I'll be
able to release the first version in the next week or so.
That's very cool!
I've run into a few roadblocks that I would be thankful for help with.
1. In Graphics.Formats.Assimp.Vec I'm trying to get the fastest and
smallest possible vector types since a program could easily have millions of
vectors in memory and operations on them take a huge fraction of the time in
an average program. One problem I ran into is how to make the vectors
type-safe. The assimp library has separate data types for colors and
vectors, but represented the same in memory. I have a few ideas about how to
represent these:
a. The way I've been doing it:
data N2
data N3
data N4
data Color
class Num a = Vector n a where
data Vec n a :: * - *
... rest of class
-- A 3-dimensional vector of doubles. t is the (phantom) tag type, like
Color, Direction, etc
-- This is meant to improve type safety
instance Vector N3 Double where
data Vec N3 Double t = Vec3D !Double !Double !Double deriving (Show, Eq)
I think you'll want to add {-# UNPACK #-} pragmas in there. You can use
vacuum to figure out the size of the representation:
http://hackage.haskell.org/package/vacuum-1.0.0
http://hackage.haskell.org/package/vacuum-1.0.0
... rest of instance
This seems very close to what I want, but it presents a few problems.
First, I create matrices from vectors, so the matrix must have an implicit
type, the type of the tags from the vectors it is made of. I made this () by
convention but then to multiply a vector by this matrix I have to use the
dot product and other vector operations, but then the tag type from the
matrix is different from that of the matrix I am multiplying. This leads to
the type `dot :: Vec n a t1 - Vec n a t2 - a`. Notice how there are two
different tag types, reducing type safety. Another problem is importing
vectors from the library. I would like to have different tags for distance
and direction, again to increase type safety, but they are both represented
the same way in the library, so the Storable instance can't always know what
type to create. I would probably always have to return a vector with tag
type ().
b. Just create separate Vec and Color datatypes. I would be mirroring the
library directly. Both would be instances of Vector.
c. Use newtype wrappers around Vec to represent the different types. I
don't really like this solution because the newtypes are too painful to use.
d. I've thought about some other solutions that I've forgotten now. Maybe
you have something better!
If you have the time to spare, I would try it multiple ways and write some
code using each. See what feels natural, see what stops errors in your
programs, and see what is just cumbersome.
Is it actually important to keep color vectors and direction vectors
separate? If so, you might consider that at a higher level than the
representation level. For example, what if I want to render vectors of
colors as directional vectors or vice versa as part of a scientific
visualization? I would have to either pick the wrong representation
initially or use the right one and convert them at the end? What bugs are
you preventing by not allowing me to multiply colors and directions?
Remember, I would like to have a high degree of type safety if possible,
but the top consideration is performance. Another thing I've been wondering
about: could I use overlapping instances to allow the vectors to be of any
numeric type, but specialize and unbox them for the common ones? I'm
assuming unboxing can't be done unless we have a specific type because the
compiler won't know how large the type is.
2. How do people feel about the vector and matrix operators (eg |*|, |*||,
||*)? I like them a lot but I would like to see how other people feel about
them.
I would assume that's matrix |*| matrix, matrix |*|| vector, and vector ||*|
matrix. Is that right?
3. Do I have to worry about marshalling float, double, and int straight to
Haskell? The report says Float and Double should conform to the IEEE
standard. I'm more interested in Int since the report only requires a 30 bit
Int. On my computer they appear to be 64 bits. Does this vary on 32 bit
computers?
There are size specific types in Data.Int, such as Int16 and Int32.
Similarly we have
Re: [Haskell-cafe] Tuple
On 11/04/2011, at 4:49 AM, Anwar Bari wrote: HI Cafe I have to make a function to check that I have one occurrence of the last element (z) of the same list [a,b] in the tuple [([a,b],z)] For example [([1,2],3),([1,1],5),([1,3],6)...] this is true because there is one single z for each single list. while this one is false [([1,2],3),([1,2],5),([1,3],6)...] because 35 were found for the same list [1,2] any Idea how to code this Fn. Let m = length xs has_duplicate_key [] = False has_duplicate_key ((k,v):xs) = if null [v' | (k',v') - xs, k' == k] then has_duplicate_key xs else True is perhaps the obvious code, but it's O(n**2). Sorting on the first element of the pairs takes O(n.lg n) time, and then checking for two adjacent (k,v),(k,v') pairs takes O(n). You can also use Data.Map in a fairly obvious way. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
