- Haskell - Haskell.org

How to define tail function for Even/Odd GADT lists?
by Ahn, Ki Yung 05 May '08

05 May '08

Using GADTs and functional dependencies, we can define GADT lists that statically distinguishes even length lists from odd length lists. > data Even > data Odd > > class Flip b c | b -> c, c -> b where > > instance Flip Even Odd where > instance Flip Odd Even where > > data List a b where > Nil :: List a Even > Cons :: Flip b c => a -> List a b -> List a c For example, Nil :: forall a. List a Even Cons True Nil :: List Bool Odd Cons False (Cons True Nil) :: List Bool Even We were able to define the function that returns the head. > headList :: List a b -> a > headList (Cons x _) = x However, we were not able to write a function that returns the tail. > tailList :: Flip b c => List a b -> List a c > tailList (Cons _ xs) = xs Is there a way to define the tailList function within the current GHC type system implementation (maybe using some other language extensions), or do we need to improve the type system regarding GADTs and functional dependencies? $ ghci -fglasgow-exts EOlist.hs GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling Main ( EOlist.lhs, interpreted ) EOlist.lhs:30:25: Couldn't match expected type `c' against inferred type `b1' `c' is a rigid type variable bound by the type signature for `tailList' at EOlist.lhs:29:21 `b1' is a rigid type variable bound by the constructor `Cons' at EOlist.lhs:30:12 Expected type: List a c Inferred type: List a b1 In the expression: xs In the definition of `tailList': tailList (Cons _ xs) = xs Failed, modules loaded: none. Prelude> Note: You can save this message content as EOList.lhs and load the script with ghci to observe the type error message above.

3 2

Re: [Haskell] Matrix multiplication
by Tillmann Vogt 04 May '08

04 May '08

Hi, Thanks for all your nice replies. I did this matrix-multiplication experiment for a seminar on multithreading where I have to give a talk on Unified Parallel C. At first I thought I should not mention haskell as an alternative because of the speed. But now I might do some slides about the advantages/(disadvantages?) of side-effekt free languages, maybe ndp. In my opinion these C extension are not a nice solution. Unified Parallel C parallelizes only for-loops and distributes the workload by uniformly cutting an array in pieces and then setting an "affinity" so that a CPU works on that data. The trick they are really proud of is that the compiler knows in this way where to put the data in a NUMA-system (Non-Uniform Memory Architecture). I am not really sure if this language extension can cope with programs where pieces need considerably different calulation times. I forgot to mention that I used ghc 6.8.2 and sorry for that stupid example (a had to take something that fits on a presentation-slide). Cheers, Tillmann Don Stewart schrieb: > The other thing here is that he's using unboxed, nested arrays in C, > while using naive lists in Haskell. > > To actually compare them, you'd need to use nested STUArrays. > > Hopefully we'll have a library for these soon (as a result of the ndp > lib). Otherwise, use on one of the matrix libraries (hmatrix/ > gslhaskell) > > For non-nested arrays, we can do rather well with: > > import Data.Array.Vector > > n :: Int > n = 4000 > > main = print (sumU (zipWithU (*) a b)) > where > a = replicateU n (2::Double) > b = mapU realToFrac $ enumFromToU 0 (n-1) > > Which compiles to some nicely fused unboxed loops. > > The trick is to get this working with nested arrays. > The ndp library looks like our best bet here: > > darcs.haskell.org/packages/ndp > > > -- Don > > tim: >> On Thu, 24 Apr 2008 04:01:50 Tillmann Vogt wrote: >>> Hi, >>> >>> I am currently experimenting with parallelizing C-programs. I have >>> therefore written a matrix vector multiplication example that needs 13 >>> seconds to run (5 seconds with OpenMP). Because I like Haskell I did the >>> same in this language, but it takes about 134 seconds. Why is it so >>> slow? Does someone have an idea? >>> >>> >>> module Main where >>> >>> main = do putStrLn (show (stupid_mul 100)) >>> putStrLn "100 multiplications done" >>> >>> stupid_mul 0 = [] >>> stupid_mul it = (s_mul it) : stupid_mul (it-1) -- without "it" after >>> s_mul only one multiplication is executed >>> >>> s_mul it = mul (replicate 4000 [0..3999]) (replicate 4000 2) >>> >>> mul :: [[Double]] -> [Double] -> [Double] >>> mul [] _ = [] >>> mul (b:bs) c | sp==0 = sp : (mul bs c) -- always false, force evaluation >>> >>> | otherwise = (mul bs c) >>> >>> where sp = (scalar b c) >>> >>> scalar :: [Double] -> [Double] -> Double >>> scalar _ [] = 0 >>> scalar [] _ = 0 >>> scalar (v:vs) (w:ws) = (v*w) + (skalar vs ws) >>> >>> >>> >>> and here the C-program >>> >>> #include <stdio.h> >>> #include <stdlib.h> >>> #include <time.h> >>> >>> #define M 4000 >>> #define N 4000 >>> #define IT 100 >>> >>> double a[M], b[M][N], c[N]; >>> >>> int main(int argc, char *argv[]) >>> { >>> double d; >>> int i, j, l; >>> time_t start,end; >>> >>> printf("Initializing matrix B and vector C\n"); >>> for(j=0; j<N; j++) c[j] = 2.0; >>> for(i=0; i<M; i++) for(j=0; j<N; j++) b[i][j] = j; >>> >>> printf("Executing %d matrix mult. for M = %d N = %d\n",IT,M,N); >>> time (&start); >>> >>> for(l=0; l<IT; l++) >>> >>> #pragma omp parallel for default(none) \ >>> shared(a,b,c) private(i,j,l) >>> >>> for(i=0; i<M; i++) >>> { >>> a[i] = 0.0; >>> for (j=0; j<N; j++) a[i] += b[i][j]*c[j]; >>> } >>> time (&end); >>> >>> d = difftime (end,start); >>> printf ("calculation time: %.2lf seconds\n", d ); >>> return 0; >>> } >>> _______________________________________________ >>> Haskell mailing list >>> Haskell(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/haskell >> You haven't even told us which compilers you're using so it's pretty difficult >> to do. I can't even get your code to compile - there are typos in it so >> you've obviously altered it since compiling yourself. >> >> While this program may be wrong, I've dashed off this attempt that takes about >> 1.3 seconds on my not-too-powerful machine: >> >> module Main >> where >> >> import Control.Monad >> >> rows = 4000 >> cols = 4000 >> iterations = 100 >> >> main = do >> let >> vector :: [Double] >> vector = replicate cols 2.0 >> matrix :: [[Double]] >> matrix = replicate rows (map fromIntegral [0..cols-1]) >> a = map (sum . (zipWith (*) vector)) matrix >> replicateM_ iterations (putStrLn (show a)) >> >> Those who understand how Haskell programs are executed will now be >> screaming "cheating!". This program when optimised by GHC (which I use) will >> only actually do the calculation once and print it 100 times. That is, after >> all, the same output you asked for. It may even be taking more shortcuts >> using identities around map and replicate but I'm not sure. >> >> When mapping imperative languages to functional ones a little understanding of >> how it is executed goes a long way. Performance of your programs will benefit >> immensely if you know how your program will be run. I'm new to Haskell but >> have already realised that performance can be altered by orders of magnitude >> by making possible optimisations more visible to the compiler with how things >> are set out. >> >> P.S. I would really recommend increasing use of higher level functions such as >> map. They make code much more readable and the most common also receive >> special optimisations from many compilers. >> >> Cheers, >> >> Tim >> _______________________________________________ >> Haskell mailing list >> Haskell(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell

2 1

www.haskell.org Problem?
by Dominic Steinitz 04 May '08

04 May '08

I'm doing darcs get http://www.haskell.org/crypto at the moment but it's just hanging. Is there a problem on the server? Thanks, Dominic.

2 1

ANN: Haddock version 2.1.0
by David Waern 02 May '08

02 May '08

Hi everyone, I'm pleased to announce Haddock 2.1.0. Hackage page: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/haddock-2.1.0 Changes since last version: * Fix a bug that made links point to the defining module instead of the "best" one (e.g Int pointing to GHC.Base instead of Data.Int) * Fix a couple of smaller bugs * The representation of DocName was changed in the library * Add a flag --no-warnings for turning off warnings David

2 2

Matrix multiplication
by Tillmann Vogt 30 Apr '08

30 Apr '08

Hi, I am currently experimenting with parallelizing C-programs. I have therefore written a matrix vector multiplication example that needs 13 seconds to run (5 seconds with OpenMP). Because I like Haskell I did the same in this language, but it takes about 134 seconds. Why is it so slow? Does someone have an idea? module Main where main = do putStrLn (show (stupid_mul 100)) putStrLn "100 multiplications done" stupid_mul 0 = [] stupid_mul it = (s_mul it) : stupid_mul (it-1) -- without "it" after s_mul only one multiplication is executed s_mul it = mul (replicate 4000 [0..3999]) (replicate 4000 2) mul :: [[Double]] -> [Double] -> [Double] mul [] _ = [] mul (b:bs) c | sp==0 = sp : (mul bs c) -- always false, force evaluation | otherwise = (mul bs c) where sp = (scalar b c) scalar :: [Double] -> [Double] -> Double scalar _ [] = 0 scalar [] _ = 0 scalar (v:vs) (w:ws) = (v*w) + (skalar vs ws) and here the C-program #include <stdio.h> #include <stdlib.h> #include <time.h> #define M 4000 #define N 4000 #define IT 100 double a[M], b[M][N], c[N]; int main(int argc, char *argv[]) { double d; int i, j, l; time_t start,end; printf("Initializing matrix B and vector C\n"); for(j=0; j<N; j++) c[j] = 2.0; for(i=0; i<M; i++) for(j=0; j<N; j++) b[i][j] = j; printf("Executing %d matrix mult. for M = %d N = %d\n",IT,M,N); time (&start); for(l=0; l<IT; l++) #pragma omp parallel for default(none) \ shared(a,b,c) private(i,j,l) for(i=0; i<M; i++) { a[i] = 0.0; for (j=0; j<N; j++) a[i] += b[i][j]*c[j]; } time (&end); d = difftime (end,start); printf ("calculation time: %.2lf seconds\n", d ); return 0; }

4 3

ANNOUNCE: category-extras 0.2
by Dan Doel 28 Apr '08

28 Apr '08

Hello, all. After quite a bit of collaboration with Edward Kmett over the past few days, I've rolled up a new release of category-extras. Perhaps the most significant addition is the generalized hylomorphism he first blogged about here: http://comonad.com/reader/2008/generalized-hylomorphisms/ added to Control.Recursion under the name 'refoldWith', as all other combinators in the library turn out to be special cases of it. Other changes include: * Data.BranchingStream moves to Control.Comonad.Cofree, and various functions are renamed accordingly, as it is the cofree comonad of a functor: Cofree F A = nu X. A * FX * Similarly, a new module has been added: Control.Monad.Free, the free monad of a functor. Free F A = mu X. A + FX * Several new recursion combinators have been added to Control.Recursion. The generalized hylomorphism 'refoldWith' was mentioned above, but we now also have: - Futumorphisms (futu, g_futu) - Chronomorphisms (chrono, g_chrono; name coined by edwardk; they're a combination of a histomorphism and a futumorphism). - Dynamorphisms (dyna, g_dyna; formalize dynamic programming) - Codynamorphisms (codyna, g_codyna; these apparently don't appear in any literature (like chronomorphisms), and we didn't attempt to give them a name, but once one sees dynamorphisms in terms of chronomorphisms/ g_hylomorphisms, this becomes fairly obvious). As can be seen, there's quite a glut of these combinators, and they all correspond to choices of distributive laws for refoldWith, so in the future, it may be better to talk about those directly. For now, though, we have lots of functions with fancy-sounding names. I believe those are the significant updates for this release. Enjoy. hackage: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/category-extras-… darcs: darcs get http://code.haskell.org/~dolio/category-extras/ -- Dan

1 0

Call for Contributions - Haskell Communities and Activities Report, May 2008 edition
by Janis Voigtlaender 25 Apr '08

25 Apr '08

Dear Haskellers, so much has happened in the Haskell world in the past months. Therefore, we would very much like to collect contributions for the 14th edition of the ================================================================ Haskell Communities & Activities Report http://www.haskell.org/communities/ Submission deadline: 10 May 2008 (please send your contributions to hcar at haskell.org, in plain text or LaTeX format) ================================================================ This is the short story: * If you are working on any project that is in some way related to Haskell, please write a short entry and submit it to the us. Even if the project is very small or unfinished or you think it is not important enough -- please reconsider and submit an entry anyway! * If you are interested in any project related to Haskell that has not previously been mentioned in the HC&A Report, please tell us, so that we can contact the project leaders and ask them to submit an entry. * Feel free to pass on this call for contributions to others that might be interested. More detailed information: The Haskell Communities & Activities Report is a bi-annual overview of the state of Haskell as well as Haskell-related projects over the last, and possibly the upcoming 6 months. If you have only recently been exposed to Haskell, it might be a good idea to browse the December 2007 edition -- you will find interesting topics described as well as several starting points and links that may provide answers to many questions. Contributions will be collected until the submission deadline. They will then be compiled into a coherent report that is published online as soon as it is ready. As always, this is a great opportunity to update your webpages, make new releases, announce or even start new projects, or to talk about developments you want every Haskeller to know about! As the purpose of the report is to collect recent or current activities, we encourage you to update all existing summaries and reports. We will probably drop any topics that have not had any activity for the past year, i.e., since May 2007, but we would very much prefer you to present an updated description of the topic. Of course, new entries are more than welcome. Reports should generally be kept brief and informative, ranging from a few sentences to a few hundred words, to keep the whole report reasonably sized. Looking forward to your contributions, Andres and Janis (current editors) FAQ: Q: Which topics are relevant? A: *All* topics which are related to Haskell in some way are relevant. We usually had reports from users of Haskell (private, academic, or commercial), from authors or contributors to projects related to Haskell, from people working on the Haskell language, libraries, on language extensions or variants. We also like reports over distributions of Haskell software, Haskell infrastructure, books and tutorials on Haskell. Reports on past and upcoming events related to Haskell are also relevant. Finally, there might be new topics we don't even think about. As a rule of thumb: if in doubt, then it probably is relevant and has a place in the HCAR. You can also ask the editors. Q: Is unfinished work relevant? Are ideas for projects relevant? A: Yes! You can use the HCAR to talk about projects you are currently working on. You can use it to look for other developers that might help you. You can use it to write ``wishlist'' items for libraries and language features you would like to see implemented. Q: How much should I write? A: There's no formal limit. But generally, entries should be short and to the point. A general introduction is helpful. Apart from that, you should focus on recent or upcoming developments. There also is no minimum length of an entry! The report aims at being as complete as possible, so please consider writing an entry, even if it's only a few lines long. Q: If I don't update my entry, but want to keep it in the report, what should I do? A: Tell us that there are no changes. We will reuse the old entry in this case, but we might drop it if it's older than a year, to give more room and more attention to projects that change a lot. Don't resent complete entries if you haven't changed them. Q: What format should I write in? A: The best format is a LaTeX source file, adhering to the template that's available at: http://haskell.org/communities/05-2008/template.tex There's also a LaTeX style file at http://haskell.org/communities/05-2008/hcar.sty that you can use to preview your entry. If you don't know LaTeX, then use plain text. If you modify an old entry, we will send you your old entry as a template within the next hours (provided we have your valid email address). Please modify that template, rather than using your own version of the old entry as a template. Don't worry about writing correct LaTeX, we will be able to handle your file. Please don't use HTML or even DOC. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de

2 1

making inits less strict
by John Tromp 24 Apr '08

24 Apr '08

The standard definition of inits: inits [] = [[]] inits (x:xs) = [[]] ++ map (x:) (inits xs) is unnecessarily strict, evaluating its argument before yielding the initial [] of the result. An improved version is: inits l = [] : case l of [] -> [] (x:xs) -> map (x:) inits xs This allows one to define for instance nats = map length (inits nats) which loops for the standard definition. regards, -John

2 1

Matrix multiplication
by Rishiyur Nikhil 24 Apr '08

24 Apr '08

You may be interested in also looking at the winning entry in the design competition of the "5th ACM-IEEE Intl. Conf. on Formal Methods and Models for Codesign (MEMOCODE'2007)" http://www.ece.cmu.edu/~jhoe/distribution/mc07contest/ The design problem was a fast matrix multiplier using a combination of SW and HW (FPGA). The winning design was implemented using BSV (Bluespec SystemVerilog, www.bluespec.com) which takes its major ideas from Haskell and Term Rewriting Systems. [ For even more spectacular results, take a look at this year's MEMOCODE design contest winner. http://rijndael.ece.vt.edu/memocontest08/ The problem was to decrypt, sort and re-encrypt a file of records. Out of 27 entrants, 9 finished the contest. The winning entry was written entirely using BSV, and beat the second-place finisher by a factor of 11x (yes, 11x, not 11%), and beat the reference software implementation by 1100x. ] Regards, Nikhil

1 0

Matrix multiplication
by Tillmann Vogt 24 Apr '08

24 Apr '08

ups, wrong newsgroup, sorry

1 0